백준56 [백준 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. [백준 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][백준 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][백준 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. [Python][백준 5972] 택배 배송 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 양방향 가중치 2. 1개 이상의 경로 존재 3. 다익스트라로 접근 */ import heapq def dijkstra(start): distances = {node: float('inf') for node in graph} distances[start] = 0 priority_queue = [(0, start)] while priority_queue: current_.. 2024. 4. 1. [Python][백준 1719] 등산 https://www.acmicpc.net/problem/1486 1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 입력된 알파벳을 숫자로 변환 (ASCII 코드 응용) 2. 변환한 높이정보를 활용해 상하좌우 오버플로 체크 후 해당 위치까지 가는데 걸리는 시간 계산 2.1 높이가 출발 위치보다 높으면 둘의 차의 제곱 2.2 출발 위치보다 낮으면 1 2.3 행렬 형태로 저장된 값을 리스트 형태로 변형 i*(가로열 길이) + j 3. 얻은 값으로 플로이드 워셜.. 2024. 3. 28. [Python][백준 1719] 택배 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 플로이드 워셜을 통해 최단거리를 계산한다 2. 최단거리 계산을 위해 비교하며 가장 먼저 거쳐간 집하장을 저장한다. 3. 저장된 집하장 정보가 없다면 현재의 k값을 있다면 원래의 집하장 정보를 저장한다. */ import sys input = sys.stdin.readline INF = float('inf') def floyd_warshall(graph): n = le.. 2024. 3. 26. [Python][백준 1956] 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 일방통행 (양방통행 X) 2. 거리의 합이 가장 작은 사이클을 찾아야 하며, 없으면 -1 출력 3. 플로이드 워셜을 통해 최단 거리를 계산할때 사이클이 있어야 하므로 스스로를 0으로 초기화 하지 않음 4. 나온 결과물 중 INF가 아닌 가장 작은 값을 출력 사이클 만드는 접근법만 생각해내면 간단한 응용이었다. */ impor.. 2024. 3. 26. 이전 1 2 3 4 5 다음