알고리즘
-
-
[BFS] 너비 우선 탐색알고리즘 2021. 10. 15. 07:42
DFS (깊이 우선 탐색)과도 엮이는 부분이 많을 수밖에 없습니다. 다만, DFS는 이 글에서 다루지 않으며 BFS에 대해서만 다룹니다. DFS는 나중에 별도의 글로 다루겠습니다. 큐를 배울 때 스택을 같이 배우듯, BFS를 배울 때 DFS를 일반적으로 같이 배워두는 게 좋습니다. 맞은 사람을 기준으로 보면, BFS의 기본 문제는 "[1260] DFS와 BFS"인것 같지만 이글에서는 BFS를 몇가지 형태로 분류하여, 각 분류를 대표하는 형태의 문제를 몇 개 선별해두었습니다. ※ 하나의 스타일에 여러개의 특정한 형태가 포함되도록 유형화했습니다. ※ 최소 한문제 이상의 연관된 문제를 BOJ에서 수록했으며, "[문제번호] 문제이름"의 형태입니다. ※ 주소창에 "boj.kr/문제번호"로 간단히 문제로 넘어갈 수..
-
[냅색] Knapsack Problem알고리즘 2021. 9. 15. 16:33
기본 문제 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 위 문제는 0-1 냅색-개수1로 고정된 문제이다. 위 문제를 보기전에 냅색의 종류부터 보자. 기본적인 냅색은 크게는 두가지 특징으로 분류된다. 1) 물건을 쪼갤 수 있는가 -> 그리디 2) 물건의 개수가 무한대인가, 1개인가 -> dp 물건을 쪼갤 수 있는 냅색(Fractional Knapsack Problem) 문제..
-
[MST] 최소 스패닝 트리알고리즘 2021. 9. 15. 02:15
최소 스패닝 트리는 가중치가 있는 양방향 그래프에서 등장한다. 만약 가중치가 없다면(가중치가 모두 1이라면) 최적해가 무엇이냐가 아니라, 답이 존재하는가 부터 문제가 된다(SCC) 그렇기에 MST는 가중치가 존재하는 그래프에서 논하게 된다. BOJ에서 기본문제를 찾을 수 있다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 대략 다음의 문제를 해결해야한다. - 입력으로는 양방향 그래프가 주어진다...
-
[정수론] 소수판별알고리즘 2021. 9. 13. 22:22
목차 [단일대상 소수판별] 1. 기본 소수판별법 -> O(N) 2. 개선된 소수판별법 -> O(N^1/2) 3. 더 개선된 소수판별법 -> O(N^1/2) * K (K O(K(logN)^3) ~ O(K(logN)^2) [구간대상 소수판별] 1. 개선된 소수판별법 + 브루트포스 -> O(N * N^1/2) 2. 에라토스테네스의 체 -> O(Nlog(logN)) [소인수분해] 1. 개선된 소수판별법 + 브루트포스 -> O(N^1/2) 2. 브루트포스 + 전처리/예외처리 -> O(NlogN) 3. 폴라드로 -> O(N^1/4) 단일대상 소수판별법은, 대개 다음과 같은 상황에서 사용됩니다. -> 입력은 한개의 정수가 들어오며, 이것이 소수인지 판별하는 경우 입력이 N개 들어온다면, 의 시간복잡도에 N을 곱한 시..
-
[LPS] Longest Palindrome Substring / Subsequence알고리즘 2021. 9. 3. 20:15
입력으로 문자열이 들어온다. 문자열의 substring / subsequence중 Palindrome을 만족하는 문자열의 최대길이를 구해야한다. 결론적으로 subsequence는 O(N^2), substring은 O(N)의 시간복잡도를 갖는다. 그 이유에 대해서 알아보자. ※ N = 문자열의 길이 ※ 문자열은 0부터 n-1의 인덱스를 갖는다. 1. 가장 먼저 떠올릴만한 방법은 (L, R)을 브루트포스로 구성하는 방법이다. L의 범위는 0부터 n-2까지, R의 범위는 L+1부터 n-1까지 돌려준다. 여기에 O(n^2)의 시간이 소요된다. 이후 팰린드롬에 대한 판별은 구성된 문자열의 길이 M만큼의 시간이 소요된다. M은 1~N의 값을 갖기에, O(N^3)의 시간복잡도를 갖는것으로 생각할 수 있다. 더 정확히..