백준 파이썬3 [알고리즘] 백준 1477 백준 1477이 문제를 처음 생각했을 때는 최대 힙을 사용하여 가장 큰 구간을 계속 선택하고, 이를 절반으로 나누면 되겠다고 판단했습니다. 하지만 반례를 확인하면서 구간을 절반으로만 나눌 수 있는 것이 아니라, 하나의 구간 사이에 3개 이상의 휴게소를 세울 수도 있겠구나라는 점을 깨달았습니다. 이를 인지한 후 다시 고민해봤습니다.처음에는 그리디 알고리즘으로 접근했지만, 앞선 휴게소 설치 개수가 뒤의 구간 길이에 영향을 주기 때문에 그리디로 해결할 수 없겠다는 결론을 내렸습니다. 그런데 문제의 입력 범위를 확인해 보니, 완전 탐색으로도 충분히 해결할 수 있을 것 같다는 생각이 들었습니다.알고리즘 문제를 풀 때 가장 먼저 해야 할 생각은 "이 문제를 완전 탐색으로 해결할 수 있을까?"입니다. 이 문제에서 구.. 2025. 2. 1. [알고리즘] 백준 1976 여행 가자 백준 1976 여행 가자 이 문제를 처음 보자마자 든 생각은 "경로 문제니깐 경로 알고리즘을 생각해야겠다." 입니다.그래서 문제 조건을 파악을 하고 # N은 200이하 M은 1000이하# 어떠한 경로가 더 큰 범주다. 내가 여행 하려고 하는 루트는 작은 범주# N이 200인데 그냥 플로이드 와샬로 모든 경로 훑으면 되지 않나? 이러한 조건을 생각을 하고 플로이드 와샬로 풀었습니다.그렇지만 다른 사람들의 풀이를 봤을 때, 내가 방향성이 잘못됐구나. 라고 깨달았습니다. 기존의 풀이import sys# N은 200이하 M은 1000이하# 어떠한 경로가 더 큰 범주다. 내가 여행 하려고 하는 루트는 작은 범주# N이 200인데 그냥 플로이드 와샬로 모든 경로 훑으면 되지 않나?inf = 2147000000N .. 2025. 1. 13. [알고리즘] 백준 13913 숨바꼭질 4 백준 13913 숨바꼭질 4 오답❌ BFS로 몇 번만에 k에게 도달할 지 구한 뒤 DFS를 구현해서 해당하는 횟수에 해당하는 순간 k값과 같다면 프로그램을 종료하는 로직을 구현했다. 하지만 예상대로 메모리를 너무 차지한다.import sysimport collectionsfrom collections import dequesys.setrecursionlimit(1000000)def DFS(N,x): if x == anw: if N == k: print(anw) for t in fin: print(t,end=' ') sys.exit(0) return for i in (N*2,N+1,N.. 2024. 10. 14. 이전 1 다음