컴퓨터하는 kimmessi

Union-find란? 합집합을 찾는 알고리즘이다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해 두 노드를 같은 집합으로 합치거나, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별해주는 알고리즘 크루스칼 알고리즘에도 쓰이는 중요한 그래프 알고리즘 알고리즘 사례 위와 같이 모두 떨어져있는 집합 각각 6개씩 있다고 가정하자. 각각의 부모노드는 자기자신이다. 여기서 2와 3를 연결했다고 해보자. (이 때 i값이 작은쪽이 부모노드가 된다고 가정한다 보통 작은 쪽이 부모노드가 되는 게 일반적) 이제 1과 2를 연결해보자. 위의 표를 보면 알 수 있듯이 합집합으로 되어있는 노드들의 부모노드 값들이 전부 조상노드로 향하는 게 아니라는 걸 알 수 있다. 그렇기 때문에 합집합으로 다 연결을 했다고..

다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다. 다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다. 동작 과정 1. 출발 노드를 설정해준다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다. 5. 3번과 4번을 반복한다. 알고리즘 사례 위와 같은 그래프가 있다고 하자 출발점은 0이다. 이제부터 0번 노드..

최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 수열을 최장 증가 부분 수열이라고 한다. 이 최장 증가 부분 수열 알고리즘을 간단하게 구현하는 방법은 DP를 사용하는 것이다. 다이나믹 프로그래밍을 이용한 최장 증가 부분 수열 for(int i=1;i dp[i]) dp[i] = dp[j] + 1; } result = max(result, dp[i]); } 각 수열의 원소까지의 최장 증가 부분 수열의 크기를 dp배열에 입력을 해주는 알고리즘이다. 처음 원소부터 해당 원소까지 for문을 돌리는데 이때, for문에서 돌리는 원소의 크기보다 해당 원소의 크기가 크고 최장 증가 부분 수열의 크기는 ..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제 해결 알고리즘 LIS알고리즘 (최장 증가 부분 수열 알고리즘)을 써준다. 이 때, $O(n \mathrm{log} n)$ 알고리즘을 사용한다 (이분 탐색). https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 알고리즘 크루스칼 알고리즘으로 풀어준다. 이 때 두 도시로 분할하는 것이므로 마지막 간선이 제일 큰 값을 가질테니까 마지막 간선의 값만 빼주면 최소값이 나온다. 그리고 find_parent함수를 int find_parent(int x){ if(parent[x] == x) return x; else return find_parent(parent[x])..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제 해결 알고리즘 비숍의 특성을 이해해야하는 문제. 체스판에 검은색 타일의 비숍과 흰색 타일의 비숍은 서로 공격할 수 없다. 그렇기 때문에 검은색 비숍과 흰색 비숍을 따로 구분해서 깊이 우선 탐색을 진행해야할 필요가 있다. 만약에 그냥 색깔 상관없이 모든 타일의 비숍을 한 번에 깊이 우선탐색을 진행한다면 시간초과가 난다. 그렇게 한다면 시간 복잡도는 $O(2^{(N*N)})$ 이지만 위의 방식대로 색깔 ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 해결 알고리즘 백트래킹, 깊이 우선 탐색 문제 (0, 0)부터 DFS를 해주는데 이 때, 문제에서 나온 것처럼 중복되는 알파벳을 체크해주는 배열과, 지나온 자리들을 체크해주는 배열을 각각 두고 탐색하는데 시간을 아낀다. 나머지는 그냥 전형적인 백트래킹이다. 소스 코드 #include using namespace std; int R, C; char arr[21][21]; bool vis..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 해결 알고리즘 전형적인 dfs 문제 소스 코드 C++ #include #include using namespace std; int answer = 0; void dfs(vector v, int target, int sum, int idx){ if(idx == v.size()){ if(target == sum) answer++; ret..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 해결 알고리즘 모든 추의 무게를 정렬 해준 후에 자기보다 왼쪽에 있는 추들의 무게의 합보다 크면 그 합에 +1인 값을 출력해주면 된다. 만약에 없다면 모든 추의 무게의 합에 +1을 해준 값을 출력해준다. 이 때, 만약 가장 무게가 가벼운 추의 무게가 1보다 크다면 1을 출력해준다. 소스 코드 #include using namespace std; int main(){ int N; cin >> N; vec..

마스터 정리 (Master Theorem) 재현식으로 표현된 알고리즘의 동작시간을 점근적으로 계산해 간단하게 계산하는 방법 $T(n) = a T( \frac{n}{b} ) + f(n) $이고 $ a>b>1, n$이 음수가 아닌 정수일 때, $$\begin{cases}T(n) \in \Theta (n^{\log _b a}) & \mathrm{if}\,\, f(n) \in O(n^{\log_b a- \epsilon }) \\ T(n) \in \Theta(n^{\log_b a} \log n) & \mathrm{if} \,\, f(n) \in O(n^{\lg _b a}) \\ T(n) \in \Theta(f(n)) & \mathrm{if} \;f(n) \in \Omega(n^{\log_b {a+\epsilon}..