본문 바로가기

전체 글117

[백준 1456] 거의 소수 Python 풀이 [백준 1456] 거의 소수 Python 풀이📌 문제 분석이 문제는 주어진 범위 내에서 소수의 거듭제곱의 개수를 구하는 문제입니다. 주어진 범위 [left, right]에서 소수의 거듭제곱으로 나타낼 수 있는 숫자들이 몇 개인지 구해야 합니다.핵심 포인트소수의 거듭제곱이란, 소수를 n번 곱한 수들을 의미합니다. 예를 들어, 2^1, 2^2, 3^2, 3^3 등이 해당됩니다.이 문제는 범위가 10^7까지 주어지기 때문에 효율적으로 소수를 구하는 방법이 필요합니다.🚨 시행착오처음에는 소수를 구하는 방식과 거듭제곱을 구하는 방식에서 몇 가지 문제에 직면했습니다.처음 코드의 문제점초기에는 소수 구하는 방법이 효율적이지 않았고, 범위가 커서 실행 시간이 오래 걸렸습니다.거듭제곱을 구할 때 한 번에 범위 내에 .. 2025. 3. 7.
[Python] 에라토스테네스의 체 (소수 구하기) 에라토스테네스의 체 (Sieve of Eratosthenes)📌 개요에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 소수를 빠르고 효율적으로 찾는 알고리즘입니다!특정 범위 내의 모든 소수를 한 번에 구할 수 있어 수학 및 알고리즘 문제 해결에서 널리 사용됩니다.🎯 원리에라토스테네스의 체는 다음과 같은 절차로 동작합니다:1️⃣ 초기화 → 2부터 원하는 범위까지 모든 정수를 나열2️⃣ 첫 소수 선택 → 가장 작은 소수 2부터 시작3️⃣ 배수 제거 → 2의 배수를 제거 (자기 자신 제외)4️⃣ 다음 소수 선택 → 남아있는 수 중 다음 소수 선택 & 배수 제거5️⃣ 반복 → 위 과정을 모든 수에 대해 반복!💡 이 과정을 거치면 남아있는 수들이 소수!🔎 예시예를 들어, 1부터 25까지의 소.. 2025. 3. 7.
[백준 11505] 구간 곱 구하기 Python 풀이 [백준 11505] 구간 곱 구하기 Python 풀이📌 문제 분석이 문제는 구간 곱을 구하는 문제로, 주어진 구간에 대한 곱을 빠르게 구하고 특정 인덱스의 값을 업데이트하는 작업을 요구합니다.구간 곱을 효율적으로 계산하고 업데이트할 수 있는 방법으로 세그먼트 트리를 사용할 수 있습니다.또한 결과를 구할 때마다 1000000007로 나눈 나머지를 출력해야 하므로, 이를 고려한 구현이 필요합니다.🚨 시행착오처음에는 구간 곱을 구하는 방식을 잘못 이해하고, 구간 곱을 구할 때마다 나머지 연산을 제대로 하지 않아서 틀린 결과를 얻었습니다.세그먼트 트리를 사용하면서 구간 곱을 계산하고, 값이 갱신될 때마다 나머지 연산을 정확하게 적용하는 방식으로 수정했습니다.처음 코드의 문제점구간 곱을 계산할 때, 나머지 연.. 2025. 3. 6.
[백준 2042] 구간 합 구하기 Python 풀이 [백준 2042] 구간 합 구하기 Python 풀이📌 문제 분석이 문제는 구간 합을 구하는 문제로, 주어진 구간에 대한 합을 빠르게 구하고 특정 인덱스의 값을 업데이트하는 작업을 요구합니다.문제에서 제시된 대로, 구간 합을 빠르게 구할 수 있는 방법을 찾아야 하며, 세그먼트 트리를 활용하여 효율적으로 해결할 수 있습니다.🚨 시행착오처음에는 단순히 구간 합을 구하려고 했지만, 모든 구간을 매번 순차적으로 더하는 방식으로 접근했을 때 시간이 너무 오래 걸린다는 문제에 봉착했습니다.이 문제를 해결하려면, 세그먼트 트리를 사용하여 구간 합을 효율적으로 구하고 업데이트할 수 있어야 한다는 것을 깨달았습니다.처음 코드의 문제점구간 합을 계산하는 부분에서 중복 계산이 많아 비효율적이었습니다.세그먼트 트리의 구조를.. 2025. 3. 6.
[백준 10868] 구간 최소값 구하기 (Python) [백준 10868] 구간 최소값 구하기 (Python)📌 문제 분석주어진 수열에서 특정 구간의 최소값을 빠르게 구해야 하는 문제입니다.단순히 탐색하면 O(n)이지만, 세그먼트 트리를 사용하면 O(log n)으로 해결할 수 있습니다.🚨 시행착오처음 코드의 문제점start_idx = 2**n으로 설정되어 있는데, 이는 올바른 트리 크기를 보장하지 못합니다.세그먼트 트리의 크기는 2^k >= n을 만족하는 최소 k를 찾아야 하므로 start_idx = 2**math.ceil(math.log2(n))로 수정해야 합니다.set_tree_min 함수에서 부모 노드를 갱신할 때, min(tree[i//2], tree[i])가 아니라 tree[i//2] = min(tree[i], tree[i^1]) 방식으로 수정해.. 2025. 3. 6.
[Python] 세그먼트 트리 segment tree [세그먼트 트리] 세그먼트 트리 알고리즘 정리📌 세그먼트 트리란?세그먼트 트리는 배열의 구간 정보를 저장하여 구간 쿼리와 업데이트를 효율적으로 처리하는 자료구조입니다. 주로 구간 합, 최소값, 최대값 등을 O(log n) 시간 안에 계산할 수 있도록 도와줍니다.🚨 세그먼트 트리의 구조완전 이진 트리: 배열을 기반으로 한 완전 이진 트리 구조로 구현됩니다.노드 역할:리프 노드: 배열의 개별 원소를 저장합니다.내부 노드: 자식 노드의 값을 이용해 해당 구간의 정보를(예, 최소값 또는 합) 계산해 저장합니다.💡 주요 연산구간 쿼리: 특정 구간(예, [L, R])의 합 또는 최소/최대값을 O(log n) 시간 내에 계산할 수 있습니다.업데이트: 배열의 한 원소가 변경되었을 때, O(log n) 시간 안에 .. 2025. 3. 6.
[백준 2011] 암호코드 Python 풀이 [백준 2011] 암호코드 Python 풀이📌 문제 분석알파벳을 숫자로 암호화한 코드가 주어졌을 때, 가능한 해석의 경우의 수를 구하는 문제입니다A=1, B=2, ..., Z=26으로 암호화되어 있습니다해석할 수 없는 경우는 0을 출력해야 합니다🚨 시행착오처음에는 단순 재귀로 접근했다가 시간 초과가 발생했습니다중복되는 부분 문제가 많아 DP를 사용하기로 결정했습니다처음 코드의 문제점재귀 호출이 지수적으로 증가하여 시간 복잡도가 O(2^n)이 되었습니다같은 인덱스에 대한 계산이 중복되어 비효율적이었습니다어떻게 고쳤나요?DP 테이블을 활용하여 중복 계산을 제거했습니다bottom-up 방식으로 해결하여 시간 복잡도를 O(n)으로 개선했습니다💡 해결 방안s = input().strip()n = len(s).. 2025. 2. 27.
[백준 2240] 자두나무 Python 풀이 [백준 2240] 자두나무 Python 풀이📌 문제 분석N(시간) 동안 1번 또는 2번 나무에서 자두가 떨어진다.자두를 최대한 많이 먹는 것이 목표이다.최대 W번 이동이 가능하며, 이를 고려해 최적의 이동 전략을 세워야 한다.🚨 시행착오초기 접근 방식단순히 1번 나무에서 계속 기다리거나 번갈아 가며 이동하는 방법을 생각했다.그러나 이동 횟수 제한이 있어 무작정 이동하는 것은 비효율적이었다.문제점Brute-force 방식으로 접근하면 경우의 수가 너무 많아진다.DP로 접근해야 한다는 생각은 들었지만, 상태를 어떻게 정의할지가 어려웠다.해결 과정DP 테이블을 정의하고, 시간을 기준으로 자두를 먹을 수 있는 최대 개수를 갱신하는 방식으로 접근했다.이동 횟수에 따라 자두를 먹을 수 있는 최대 개수를 관리하는.. 2025. 2. 26.
[Python][백준 14719] 빗물 [백준] 빗물 (Python 풀이)📌 문제 분석이 문제는 2차원 세계에서 블록으로 이루어진 지형 위에 비가 내렸을 때 고이는 빗물의 총량을 구하는 문제입니다.주어진 입력으로 각 열의 블록 높이가 주어지며, 이를 바탕으로 빗물이 얼마나 고일 수 있는지를 계산해야 합니다.🚨 시행착오처음에는 높이를 기반으로 2차원 배열을 생성한 후, 각 행에서 빗물이 고일 수 있는 공간을 탐색하는 방식으로 접근했습니다.그러나, 해당 접근 방식은 불필요한 메모리 사용이 많았고, 더 효율적인 해결 방법이 존재한다는 점을 깨달았습니다.어떻게 고쳤나요?2차원 배열을 만들지 않고, 높이를 기준으로 직접 탐색하여 빗물의 양을 계산하는 방식으로 변경했습니다.좌측과 우측에서 현재 높이보다 큰 블록을 찾는 방향으로 개선했습니다.💡 해결.. 2025. 2. 6.
[Python][백준 14503] 로봇 청소기 [백준 14503] 로봇 청소기 Python 풀이📌 문제 분석로봇 청소기가 주어진 방에서 청소할 수 있는 칸의 개수를 구하는 문제입니다.방은 2차원 배열로 표현되며, 각 칸은 벽(1) 또는 빈 칸(0)으로 이루어져 있습니다.로봇은 현재 위치에서 청소를 하고, 주변에 청소되지 않은 빈 칸이 있으면 반시계 방향으로 회전하여 이동합니다. 모든 방향이 벽인 경우 후진합니다.🚨 시행착오처음에는 로봇의 이동과 청소 로직을 단순하게 구현했으나, 인덱스 범위 체크와 방향 전환 로직에서 문제가 발생했습니다.로봇이 청소한 칸을 제대로 표시하지 않거나, 후진 로직이 불완전하여 무한 루프에 빠지는 경우가 있었습니다.처음 코드의 문제점인덱스 범위 체크가 부족하여 배열의 경계를 넘어가는 경우가 발생했습니다.방향 전환 로직이 .. 2025. 1. 20.
[Python][백준 1759] 암호 만들기 [백준 1759] 암호 만들기 Python 풀이📌 문제 분석주어진 알파벳으로 구성된 암호를 생성하는 문제입니다.암호는 서로 다른 L개의 알파벳 소문자로 구성되어야 하며, 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음이 포함되어야 합니다.생성된 암호는 사전식으로 정렬되어 출력되어야 합니다.🚨 시행착오처음에는 모든 가능한 조합을 생성하기 위해 itertools의 permutations를 사용하려고 했습니다.그러나 이 방법은 중복된 조합을 생성하고, 조건을 체크하는 데 비효율적이라는 문제가 있었습니다.처음 코드의 문제점itertools를 사용하여 모든 순열을 생성하면, 조건을 만족하지 않는 조합도 포함되어 결과가 비효율적이었습니다.또한, 모음과 자음의 개수를 체크하는 로직이 복잡해져 .. 2025. 1. 14.
[Python][BOJ 1239] 중심선 개수 세기 [BOJ 1239] 중심선 개수 세기 Python 풀이📌 문제 분석주어진 N개의 숫자에서 중심을 가로지르는 선의 개수를 구하는 문제입니다.중심을 가로지른다는 것은 특정 조합의 합이 50이 되는 경우를 의미합니다.모든 가능한 조합을 고려하여 최대 중심선 개수를 찾아야 합니다.🚨 시행착오처음에는 단순히 50을 만드는 조합의 개수를 세는 방식으로 접근했습니다.하지만 문제의 의도는 중심선을 관통하는 선의 개수를 세는 것이었습니다.이로 인해 잘못된 결과가 나왔고, 문제를 다시 분석하게 되었습니다.처음 코드의 문제점중심선을 세는 로직이 아닌, 단순히 50을 만드는 조합의 개수를 세고 있었습니다.원형으로 배치된 숫자들을 고려하지 않았습니다.어떻게 고쳤나요?누적합을 사용하여 각 조합에서 중심선을 세는 방식으로 변경.. 2025. 1. 9.

티스토리툴바