본문 바로가기

백준38

[Algorithm] 백준 14620 꽃길 | 파이썬 (브루트포스) ※ 14620 꽃길https://www.acmicpc.net/problem/14620 문제 해결 TIP메인 로직은 backtrack안의 for문이다. 우선 첫번째 꽃을 심는다. 이후 두번째 꽃은 가능한 모든 위치에 심으면서 최소 비용이 나오는지 확인한다. 세번째 꽃도 가능한 모든 위치에 심으면서 최소 비용이 나오는지 확인한다. 이후, 꽃을 다시 뽑고, 첫 번째 꽃은 다른 위치에 심고 다시 반복 진행한다. 전체 코드N = int(input())money_graph = [list(map(int, input().split())) for _ in range(N)]visited = [[False] * N for _ in range(N)]dx = [0, 0, 1, -1]dy = [1, -1, 0, 0]# 꽃을 심을.. 2024. 9. 21.
[Algorithm] 백준 4485 녹색 옷 입은 애가 젤다지? | 파이썬 (다익스트라) ※ 4485 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485 문제 해결 TIP다익스트라를 2차원 배열 형태에 적용해보자. 전체 코드import heapq# 방향 설정: 상, 하, 좌, 우dx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]def dijkstra(n, graph): # 비용 테이블을 무한대로 초기화 distance = [[float('inf')] * n for _ in range(n)] distance[0][0] = graph[0][0] # 우선순위 큐에 시작점 넣기 (비용, 좌표) queue = [(graph[0][0], 0, 0)] while queue: dist, x, y = heap.. 2024. 9. 11.
[Algorithm] 백준 1261 알고스팟 | 파이썬 BFS ※ 1261 알고스팟https://www.acmicpc.net/problem/1261 문제 해결 TIP이전 미로만들기와 동일한 문제이다. n, m 값의 범위만 재설정해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * m for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + .. 2024. 9. 11.
[Algorithm] 백준 2665 미로만들기 | 파이썬 BFS ※ 2665 미로만들기https://www.acmicpc.net/problem/2665 문제 해결 TIPvisited 배열에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 저장한다. bfs로 탐색하면서, 흰 방인 경우를 먼저 탐색한다.(appendleft) 검은 방일 경우에는 이전 visited값에 1을 추가해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * n for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.p.. 2024. 9. 11.
[Algorithm] 프로그래머스 14938 서강그라운드 | 파이썬 (다익스트라) ※ 14938 서강그라운드https://www.acmicpc.net/problem/14938 문제 해결 TIP최단경로 문제와 동일한 다익스트라 알고리즘으로 구현한다. 이때, 단방향이 아닌 양방향으로 간선 정보를 저장해야 한다. 또한, 수색범위 조건을 추가해준다. 전체 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)def dijkstra(start): q= [] heapq.heappush(q,(0,start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] 2024. 9. 6.
[Algorithm] 프로그래머스 1238 파티 | 파이썬 (다익스트라) ※ 1238 파티https://www.acmicpc.net/problem/1238 문제 해결 TIP최단경로 문제와 동일한 다익스트라 알고리즘으로 구현한다. 이때, 시작 노드가 고정된 오는 길 뿐만 아니라 가는 길도 계산해야 함으로, 추가해준다. 전체 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)def dijkstra(start): q= [] heapq.heappush(q,(0,start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] 2024. 9. 5.
[Algorithm] 프로그래머스 1753 최단경로 | 파이썬 (다익스트라) ※ 1753 최단경로https://www.acmicpc.net/problem/1753 문제 해결 TIP주어진 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는다. 다익스트라 알고리즘으로 구현한다. 우선순위 큐를 초기화하고 큐가 비어있을 때까지 인접 노드를 확인하며 더 짧은 경로를 찾아 해당 거리를 업데이트한다. 전체 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)def dijkstra(start): q= [] heapq.heappush(q,(0,start)) distance[start] = 0 #q = [(0, 1)] while q: dist, now = heapq.heappop(q) .. 2024. 9. 5.
[Algorithm] 백준 2309 일곱 난쟁이 | 파이썬 ※ 2309 일곱 난쟁이https://www.acmicpc.net/problem/2309 문제 해결 TIP반대로 생각했을 때 9개의 난쟁이 키를 모두 합한 후, 2명의 난쟁이 키를 빼준 것이 100일 때를 출력하면 된다.  전체 코드result = []for i in range(9): height = int(input()) result.append(height)result.sort()sum = sum(result)answer = sumfound = Falsewhile True: for i in range(8): for j in range(i+1, 9): answer -= result[i] answer -= result[j] .. 2024. 8. 9.
[Algorithm] 백준 1436 영화감독 숌 | 파이썬 ※ 1436 영화감독 숌https://www.acmicpc.net/problem/1436 문제 해결 TIP5666 다음으로 큰 종말의 수는 6660이다. 가장 작은 종말의 수인 666에서 1씩 증가시키며, count를 쌓아가면 된다. (효율을 따지려고 어렵게 생각하지 말고 컴퓨터는 빠르게 계산할 수 있다는 것을 항상 잊지말것...) 전체 코드N = int(input())answer = 666count = 0while True: if '666' in str(answer): count += 1 if count == N: break answer += 1print(answer) 2024. 8. 7.

티스토리툴바