Binceline

DFS 깊이 우선 탐색. 말 그대로 현재 위치에서 갈 수 있는 곳 중 짧은 곳으로 최대한 깊게 들어간다. 들어가다가 막히면 다시 뒤로 돌아와서 갈 수 있는 곳으로 감. 하지만 만약 그래프의 깊이가 커질수록 부하도 커진다. BFS 너비 우선 탐색 이건 과거, 그리고 현재에서 갈 수 있던 곳 중 가장 짧은 곳으로 간다. DFS, BFS는 이전 값들을 축적하지 않기 때문에 간선을 이동하는 비용(가중치)이 1이어야 한다. (비용이 같아야 한다는 것) 다익스트라 알고리즘 너비 우선 탐색이다. 다익스트라 알고리즘은 이 (가중치)들을 점점 축적해 나간다. 축적한다는 건 다이나믹 방식을 사용한다는 것이다. 프림 알고리즘 프림 알고리즘은 MST(최소 스패닝 트리) 알고리즘이라고 하는데, 각 정점을 연결하는 간선들을 최소..

크루스칼 알고리즘과 Prim's 알고리즘으로 해결할 수 있다. 이걸 MST (Minimal Spanning Tree) 알고리즘이라고 한다. 난 Prim's 알고리즘으로 해결했다. 다익스트라 알고리즘과 유사하지만 '정점으로 가는 최단거리'를 계속 갱신해 줄 필요가 없다.그리고 다익스트라 알고리즘은 정점을 연결하는 간선의 방향이 존재하는데, MST는 그저 '연결되었는가?' 이다. pq : 현재 위치에서 갈 수 있는, 혹은 지금까지 갈 수 있었던 정점들을 거리순으로 정렬해 놓는 우선순위 큐dist : 스패닝 트리를 만드는 최소비용을 누적해나갈 변수 1. 큐에서 하나 빼고 이미 갔던 곳인지 검사한다. 이미 갔던 곳이라면 반복.2. 이전 위치로부터 현재 위치로 가는 거리를 dist에 추가함.3. 현재 위치에서 갈..

다익스트라 알고리즘 나무위키 시작점으로부터 갈 수 있는 모든 경로에 대한 최단거리를 구한다. 필요했던 것- map : 간선정보를 저장할 map- v : 이미 방문했는지를 위한 visit array- d : 시작점으로부터 정점까지의 거리 정보를 가지고 있는 distance array- pq : 현재 갈 수 있는(그리고 갈 수 있었던) 정점들을 담아 둘 priority queue. 정점과 거리 쌍으로 저장. 코드 가독성을 위해 pq에 첫 번째 위치 (시작점)을 미리 입력해 놓고 했음. 1. pq에서 하나 pop하고 이미 방문했던 곳인지 visit array 검사. 이미 방문했으면 다시 1번 반복.2. 주변 경로 확인 후 map을 보면서 [원래 알고 있던 목적지까지의 거리]와 [현재 지점까지의 거리 + 목적지..

문제 - 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 : 2 예제 출력 1 : 2 예제 입력 2 : 9 예제 출력 2 : 55 (알고리즘 문제 공부를 처음 시작해 보는데, 유튜브로 백준님의 다이나믹 알고리즘 강의를 듣고 공부를 시작했당) - 어떤 경우의 다음 결과가 정해져 있다면 그것까지 포함해서 하나의 경우로 친다. - 세로가 2, 가로가 N이라면, 주어진 직사각형으로 세로 2를 만들 수 있는 최소 단위를 생각해 보자. 직사각형을 채운다고 했을 때, 마지막에 올 수 있는 경우를..