Python14 [백준 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. [백준 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][백준 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. [Python][백준 21278] 호석이 두 마리 치킨 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 플로이드 워셜을 통해 각 건물간의 거리를 구한다. 2. 치킨집은 총 두개이고 각 치킨집에서 다른 건물까지 걸리는 시간을 비교한다 3. 더 작은 값의 2를 곱한뒤 저장한다 (왕복 소요 시간) 4. 각 치킨집의 위치를 완전탐색으로 돌리며 위의 방법으로 구한 값을 비교한다. 5. 더 작은 값의 치킨집 위치를 같이 저장한다. 플로이드 .. 2024. 3. 23. [Python][백준 2660] 회장뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 입력된 사람들의 친구 관계를 행렬 형태로 저장 2. 최대 회원 수가 50명이므로 시간적 압박은 크지 않다 따라서 플로이드 워셜을 사용했다. 3. 각 사람의 가장 먼 사람을 기준으로 잡고 회원들 중 가장 적은 거리를 구한다 4. 그 거리와 그 거리를 가진 회원의 수 를 구하고 5. 회원들의 리스트를 뽑은 후 정렬 후 출력한다. 플로이드 워셜만 사용할 줄 알면 .. 2024. 3. 22. [Python][백준 1897] 토달기 https://www.acmicpc.net/problem/1897 1897번: 토달기 첫 줄에 사전에 등재된 단어의 수 d와, 원장님이 처음 말씀하신 단어가 주어진다. (1 ≤ d ≤ 1,000) 원장님이 처음 말씀하신 단어의 길이는 세 글자이며, 사전에 있는 단어를 말씀하셨다. 다음 d개 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 토달기 가능한 단어가 없을 시 시작한 단어가 정답 2. bfs 로 탐색하며 확인해야 하는 조건들 : - 토달기 단어보다 한글자 많아야 한다. - 토달기 단어를 포함하는 단어 - 중간에 다른 글자 하나를 포함한 토달기 단어 - 투 포인터로 문자열 탐색 - 방문 처리를 통해 방문한 단어 재방문 방지 어려워 보이지만 방법 자체만 알면 그리 어렵진 않다 */.. 2024. 3. 21. [Python][백준 1595] 북쪽나라의 도로 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 데이터 입력 try catch 문 활용해서 입력없음으로 오류 발생 방지 2. 최대 10000개 노드를 DFS 돌릴 시 시간초과 발생 3. 따라서 가장 긴 거리를 찾는거니 가장 긴 거리를 가질 두 노드 중 하나를 구하고 해당 노드로 탐색을 돌리면 총 두번의 탐색만으로 가장 긴 도로를 찾을 수 있다. */ import sys input = sys.stdin.rea.. 2024. 3. 20. 이전 1 2 다음