룰루랄라 알고리즘

Spanning Tree 특징 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. V개의 정점을 (V-1)개의 간선으로 연결되어야 한다. MST(Minimum Spanning Tree) Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 1. Kruskal 알고리즘 2. Prim 알고리즘 시작 정점에서 부터 출발하여 스패닝 트리 집합을 단계적으로 확장 Prim 알고리즘의 동작 과정 시작 정점을 힙에 저장 방문하지 않은 정점중에서 가중치가 가장 낮은 정점을 선택 위 과정을 트리가 (V-1)개의 간선을 가질 때 까지 반복 백준 1922

배낭 문제(Knapsack Problem) 배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 담을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭 문제는 1) 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)와 ex) 설탕, 소금등 2) 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)으로 나뉜다. 1) 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로 그리디 알고리즘으로 해결할 수 있다. 2) 물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법(DP, Dynamic Programming)을 활용해 해결할 수 있다 출처..

2진법 -> 10진법 변환

가중치(비용)이 0 과 1만 있을 떄 최단거리 구하기 비용이 0 과 1로 나뉘어져 있을 때 다익스트라 알고리즘을 deque로 사용할 수 있다 매 노드를 탐색할 떄 마다 갈 수 있는 노드에 대한 비용이 0이면 앞에, 1이면 뒤에 추가 하면서 탐색 다익스트라보다 빠른 속도 ex) 백준 1261번 알고스팟

에라토스테네스의 체 소수의 판별 방법 주어진 숫자 m부터 n까지 숫자 중에서 소수를 판별할 때 2부터 n의 제곱근 까지만 검사해도 소수를 판별 할 수 가 있다 또한 전체 수에서 2의 배수 3의 배수...를 차례로 제거해 나가면 소수만 남는다 백준 1978 백준 1929

유클리드 호제법 최대공약수 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 최소공배수 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다. 백준 2609

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 수행 다만 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지는 않음 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)