미소를뿌리는감자의 코딩

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, ..

1. 문제https://www.acmicpc.net/problem/14888 2. 접근 방법어떻게 연산자들의 경우의 수를 표현할 수 있을까 고민해 보았다.처음에 잘 생각이 나지 않았지만, 섣불리 접근하다간 오히려 시간을 많이 쓸 것 같아서 더 고민해 보았다. - 요런 태도가 코테에서는 중요한 것 같다. (메모메모~)예를 들어 + : 2개- : 1개* : 1개/ : 1개라면, +가 중복 되기에, 중복 case를 제외시켜 주어야 한다. 따라서, dfs를 이용해서dfs(현재 연산 경우의 리스트, 사용하고 남은 연산자 리스트) 로 문제 풀이를 시작한다.만약, 현재 연산자 경우의 리스트의 len이 연산자 개수라면, 해당 리스트를 total 에 append하고 return 한다. 그 외는 for i in range..