목록2024/09 (49)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/2665 2. 접근 방법미로 만들기는 0-1 BFS를 적용할 수 있는 문제였다.0-1 BFS에 알지 못했기에 이에 대해서 공부할 수 있던 좋은 기회였다. 실상은 BFS 보단 0-1, Dijkstra로 부르는 것이 더... 나을지도..?!라는 생각이 들었다.어떤 블로그에서 보았듯, 99% Dijkstra 에 1% BFS가 들어간 느낌이다.https://velog.io/@vkdldjvkdnj/boj01261 [BOJ 1261] - 알고스팟 (0-1 BFS, Python)BOJ 1261 - 알고스팟 (0-1 BFS, Python)velog.io 0-1 BFS에 대해서 이해할 때, 위 블로그가 도움이 많이 되었다. Dijkstra의 경우, lis..
1. 개요Dijkstra Algorithm과 Floyd Warshall Algorithm을 이용하는 이유가 무엇일까? MST의 kruskal Algo. 와 Prim. Algo 와는 다른 점이 무엇일까?MST의 경우엔, 모든 vertex를 방문할 수 있는 최단 경로를 나타낸다. 반면 Dijkstra는 하나의 vertex에서 다른 vertex까지의 최단 경로를 나타낸다.Floyd Warshll은 한 vertex에서 다른 vertex까지의 모든 최단 경로를 알아내고자 사용하는 알고리즘이다. 따라서, Dijkstra는 O(n^2)의 시간 복잡도를, Floyd Warshall은 O(n^3)의 시간 복잡도를 가진다. 아래 코드에서 Floyd Warshall 알고리즘을 Bellman Ford 알고리즘으로 잘못 적었다..
1. 문제https://www.acmicpc.net/problem/2617 2. 접근 방법특정 구슬보다 작은지 큰지를 구분하여 저장해 주었다.예시를 defaultdict로 저장해 주었는데, 아래와 같이 저장하게 된다.heavier[1] = [2, 5]heavier[2] = [4]heavier[3] = [4]lighter[2] = [1]lighter[4] = [3, 2]lighter[5] = [1] heavier[1] 보다 작은 것은, 2, 5 그리고 2보다 작은 4이다.따라서, 이를 dfs로 순환하여 표현되지 않은 값들도 표현이 되도록 하였다. 구슬의 개수//2 보다 더 큰 값을 해당 노드가 저장하고 있다면, 그 노드는 중간에 있을 수 없다.해당 구슬보다 작은 구슬이 mid개 있는 것 or 해당 구슬보다..
1. 문제https://www.acmicpc.net/problem/2573빙산 정복 기념 그림 호호~ 2. 접근 방법 우선 얼음의 위치에 따른, 바닷물이 맞닿아 있는 개수를 base_sea라는 리스트에 저장해 주었다.따라서, 맞닿아 있는 바다의 개수를 계산하면서, 얼음이 있는 위치를 glacier_loc이라는 deque에 저장해 주었다.이를 통해 glacier_loc을 순환하면서, 값들을 수정할 수 있다.이를 이용하지 않는다면, 2중 for문을 사용하게 되어 시간초과가 날 가능성이 높다.또한 문제에서 제시하였듯, 리스트의 맨 위에 줄, 아래 줄, 그리고 왼쪽, 오른쪽 줄은 0으로 채워져 있으므로 범위를 이용할 경우가 있을 때, 1 glacier[0, 0, 0, 0, 0, 0, 0][0, 2, 4, ..