룰루랄라 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 수행 다만 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지는 않음 2차원 테이블에 최단 거리 정보를 저장 다이나믹 프로그래밍 유형에 속함 각 단계마다 특정한 노드 K를 거쳐가는 경우를 확인 A에서 B로 가는 최단 거리보다 A에서 K를 거쳐 B로 가는 거리가 더 짧은지 검사 점화식 D ab = min(D ab, D ak + D kb) 시간 복잡도가 O(N*2)이기 때문에 N의 크기가 500이하 일때 사용 노드를 거쳐가는 문제일 때 사용 ex) 백준 11404번 11403번

다익스트라 최단 경로 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작 매 상황에서 가장 비용이 적은 노드를 선택해 과정을 반복 동작과정 1. 출발노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5. 3,4을 반복 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음

*동적 계획법 다음과 같은 조건을 만족해야 한다. 1.최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 2.중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다 *메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다 값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다 *탑다운(하향식) VS 보텀업(상향식) 상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고, 하향식은 ..

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 1. 알고리즘은 간단한데 코드가 길어지는 문제 2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 3. 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 4. 적절한 라이브러리를 찾아서 사용해야 하는 문제 열 NxM = 행x열 (0,0) (0,1) 행 (1,0) (1.1)

DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다 1.탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 2.스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 3.더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다 ex)백준 2667 - 단지번호붙이기 (연결 요소를 이루는 노드 수를 계산) 실행결과 1 2 7 6 8 3 4 5

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다 BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다 1.탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다 2.큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다 3.더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다 보통 최단경로를 찾는 문제에서 많이 사용한다. ex)백준2178 - 미로 최단거리 찾기 백준 7576 - 가중치가 없는 그래프에서 다중 시작점에서 모든 칸 까지 최단거리 찾기 시작점 A 에서 F 까지의 최단 경로를 알고 싶다고 하자. BFS를 진행하면서 F 를 처음 딱 방문하는 순간이 있을 것이다. 그 순간에 거리가..