Problem Solving88 [백준 1456] 거의 소수 Python 풀이 [백준 1456] 거의 소수 Python 풀이📌 문제 분석이 문제는 주어진 범위 내에서 소수의 거듭제곱의 개수를 구하는 문제입니다. 주어진 범위 [left, right]에서 소수의 거듭제곱으로 나타낼 수 있는 숫자들이 몇 개인지 구해야 합니다.핵심 포인트소수의 거듭제곱이란, 소수를 n번 곱한 수들을 의미합니다. 예를 들어, 2^1, 2^2, 3^2, 3^3 등이 해당됩니다.이 문제는 범위가 10^7까지 주어지기 때문에 효율적으로 소수를 구하는 방법이 필요합니다.🚨 시행착오처음에는 소수를 구하는 방식과 거듭제곱을 구하는 방식에서 몇 가지 문제에 직면했습니다.처음 코드의 문제점초기에는 소수 구하는 방법이 효율적이지 않았고, 범위가 커서 실행 시간이 오래 걸렸습니다.거듭제곱을 구할 때 한 번에 범위 내에 .. 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. [백준 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. [Python][BOJ 22352] 항체 인식 [BOJ 22352] 항체 인식 Python 풀이📌 문제 분석N×M 크기의 배열에서 백신 투여 전과 후의 상태가 주어짐백신은 한 번만 투여되며, 투여된 칸과 상하좌우로 연결된 같은 값을 가진 칸들이 모두 동일한 값으로 변경됨주어진 투여 후 상태가 가능한 결과인지 판단해야 함🚨 시행착오처음에는 모든 칸에서 DFS를 시작하고, 가능한 모든 값으로 변경해보는 방식으로 접근시간 복잡도가 O(NM * NM * KNM)로 매우 높았음실제로는 백신이 한 번만 투여된다는 점을 활용하여 최적화 가능했음처음 코드의 문제점불필요하게 모든 칸에서 DFS 시작가능한 모든 값을 시도매번 배열을 원상복구하는 연산 필요어떻게 고쳤나요?투여 전/후가 다른 첫 지점만 찾아서 DFS 실행해당 영역을 투여 후의 값으로 한 번에 변경전체.. 2025. 1. 8. [Python][백준 2668] 숫자고르기 [백준 2668] 숫자고르기 Python 풀이📌 문제 분석이 문제는 결국 사이클을 찾는 문제입니다. 첫째 줄과 둘째 줄에서 고른 수들이 같아야 하는데, 이게 곧 사이클을 이루는 숫자들을 찾는 거랑 같습니다.🚨 시행착오처음에 DFS로 사이클을 찾으려고 했는데, 4%에서 자꾸 틀렸다고 나오더라구요.한참을 고민하다가 사이클 판단하는 부분에 문제가 있다는 걸 발견했습니다!처음 코드의 문제점방문 체크랑 경로 추적을 제대로 안 해서 정확한 사이클을 못 찾고 있었습니다현재 경로에 있는 노드들만 사이클로 봐야 하는데, 이전에 방문한 노드도 사이클로 잘못 판단했었죠그러다 보니 사이클이 아닌 경우도 결과에 들어가는 문제가 생겼습니다어떻게 고쳤나요?visited 집합으로 방문 체크하고path 리스트로 현재 경로를 추적하.. 2025. 1. 7. [Python][백준 1148] 단어 만들기 https://www.acmicpc.net/problem/1148 1148번: 단어 만들기 어떤 신문엔 이러한 퍼즐이 있다. 3x3의 표에 영문자가 하나씩 있으며, 이 영문자들을 사용해서 최대한 많은 영단어를 만드는 것이 목표이다. 예를 들면, 아래의 퍼즐판에서는 'LINT', 'TILL', 'BRILLIAN www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 퍼즐에 있는 모든 글자들에 대해 각 글자마다 가능한 단어의 수 체크 2. 가장 많은 단어와 가장 적은 단어를 기록 및 출력 3. 단어의 수 체크할때 ASCII 코드 값 활용해서 배열 활용 간단한 문자열 문제 */ import sys input_func = sys.stdin.readline input_words = [] while T.. 2024. 4. 2. 이전 1 2 3 4 ··· 8 다음