[백준 파이썬] 4485 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 N*N의 배열에서 [0][0] 에서 [N-1][N-1]까지의 경로중 가장 적은양의 Cost가 필요한 길을 찾는 문제이다. 풀이 가장 작은 Cost를 구하는 BFS문제이므로 다익스트라 알고리즘을 사용하였다. def dijsktra(startCost): q = [] heapq.heappush(q, (startCost, 0, 0)) distance[0][0] = startCost..

• format_list_bulleted 알고리즘
• · 2024. 1. 15.
• textsms

[백준 파이썬] 14502 연구소

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 연구소의 정보가 주어진 후 임의의 벽 3개를 지어 가장 적은 곳에 바이러스가 퍼지게 하는 문제이다. 풀이 임의의 벽3개를 세우는 방법과 바이러스가 퍼지는 방법 2개를 고려해야한다. 먼저 임의의 벽 3개를 세우는 방법은 백트랙킹을 사용하였다. def makeWall(count): if count == 3: bfs() return for i in range(N): for k in range(M): if matrix[i][k] == 0: matrix[i][k] = 1 ma..

• format_list_bulleted 알고리즘
• · 2024. 1. 12.
• textsms

[백준 파이썬] 1240 노드 사이의 거리

1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 문제 노드의 정보를 입력받고 노드 사이의 거리를 구하는 문제이다. 풀이 노드의 거리가 주어지고 특정 노드 사이의 거리를 구하는 문제이므로 깊이 우선탐색으로 해결하였다. N, M = map(int, input().split()) graph = list([0] * (N + 1) for _ in range(N + 1)) 노드와 그 노드의 거리를 입력받아야 하므로 2차원 배열을 생성해 입력받아 주었다. def dfs(s, e, dist): glob..

• format_list_bulleted 알고리즘
• · 2024. 1. 10.
• textsms

[백준 파이썬] 1245 농장 관리

https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제 농장의 높이가 주어지고 산봉우리의 개수를 구하는 문제이다. 풀이 농장에 높이가 주어지므로 산봉오리를 구하는 식을세우면 된다. 산봉오리는 인접 8개의 방향보다 높은 곳이므로 dfs를 이용하여 해결하였다. def dfs(r, c): nowHeight = farm[r][c] stack = [(r, c)] flag = True while stack: r, c = s..

• format_list_bulleted 알고리즘
• · 2024. 1. 5.
• textsms

[백준 파이썬] 2042 구간 합 구하기

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 구간합을 구하는 문제이다. 다만 중간중간 구간에서 값이 변경된다. 풀이 dp를 이용하여 구간합을 계산하면 중간중간 값이 바뀌기 때문에 O(N)의 시간 복잡도를 가지게 되고 시간초과가 난다. 따라서 세그먼트 트리를 이용하여 O(log(n))의 시간복잡도로 문제를 해결해야 한다. tree = [0, 15, 6, 9, 3, 3, 4,..

• format_list_bulleted 알고리즘
• · 2024. 1. 3.
• textsms

[백준 파이썬] 2665 미로만들기

2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 해당 지점으로 이동할 때 가장 적은 수로 방을 바꾸는 문제이다. 아이디어 최단거리를 탐색하는 문제이기 때문에 다익스트라를 이용하였다. 풀이 def dijkstra(): q = [] heapq.heappush(q, (0, 0, 0)) distance[0][0] = 0 while q: cost, x, y = heapq.heappop(q) for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

• format_list_bulleted 알고리즘
• · 2024. 1. 1.
• textsms