본문 바로가기

자료구조13

[LCA] 백준 13116번 30번 (Swift 풀이) 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net [문제] 혹시 2007학년도 대학수학능력시험 수리영역 가형 이산수학 30번 문제를 아는가? 여러분은 수능을 치는 수험생의 마음으로 이 문제를 해결해야만 한다. 하지만 우리는 저작권 위반으로 판사님을 뵙고 싶지 않았기 때문에 이 문제를 직접 수록할 수는 없었다. 아래 링크 중 하나를 클릭해서 pdf 파일을 내려받아 가장 마지막 페이지를 보면, 위의 그림과 아주 유사한 문제가 하나 있을 것이다. 여러분은 바로 그 문제를 해결해야만 한다... 2021. 4. 21.
LCA (Lowest Common Ancestor) LCA는 이름에서 알 수 있듯이 두 정점 A와 B에서 가장 가까운 공통된 조상을 찾는 알고리즘입니다. 여기에는 2 가지 방법이 있는데요, 하나씩 조상 노드를 살펴보는 방법과 DP를 사용하는 방법이 있습니다. 트리의 depth를 H라고 할 때, 조상 노드를 하나씩 살펴보는 방법으로는 보통 시간복잡도가 O(H)가 나오지만, 최악의 경우 O(N)이 걸릴 수 있습니다. 하지만 DP를 사용하게 된다면? 보통 O(log H)가 걸리지만, 최악의 경우 O(log N)이 걸립니다. DP를 사용하는게 훨씬 빠르죠? 그래서 노드의 개수가 매우 많고, 검사해야할 노드가 매우 많은 경우에 DP를 사용한 방법을 활용하면 빠르게 답을 찾을 수 있습니다! 먼저, 조상 노드를 하나씩 살펴보는 방법은 사실 간단해요. 두 정점 A와 B.. 2021. 4. 1.
확장 유클리드 호제법 이전에 유클리드 호제법에 대해 알아본 적이 있었습니다. 유클리드 호제법과 확장 유클리드 호제법 모두 정수론을 이용한 알고리즘인데요, 유클리드 호제법이 a와 b의 최대 공약수 gcd(a, b)를 구하는 알고리즘이었다면, 확장 유클리드 호제법은 더 나아가 a와 b의 최대 공약수 gcd(a, b)와 ax+by = gcd(a, b)를 만족하는 x, y까지 구하는 알고리즘 입니다. 그럼 확장 유클리드 호제법을 어떻게 사용하는지 알아보겠습니다. 확장 유클리드 호제법을 사용하기 위해 간단한 규칙을 먼저 살펴봐야 합니다. 아래 규칙을 통해서 Ri가 0이 될 때까지 반복했을 때 마지막으로 나온 Xi, Yi가 gcd(a, b)를 만족하는 x, y가 됩니다. 초기 설정해줘야 하는 값은 X0 = 1, X1 = 0, Y0 = .. 2021. 3. 25.
인덱스 트리 (Indexed Tree) 구간합을 구하는 트리 종류에는 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있습니다. 그 중에서도 오늘은 인덱스 트리(Indexed Tree) 에 대해 알아보려 합니다. 참고로, 인덱스 트리에 포함되어 있는 종류 중 하나가 세그먼트 트리이기 때문에 세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있습니다. 인덱스 트리는 A라는 수열에서 구간 S ~ E 가 주어졌을 때, A의 구간 S ~ E 사이의 합을 구하기 위해 사용합니다. 중간 중간 A의 값이 하나씩 바뀔 때마다 그 구간의 합을 구할 때 인덱스 트리를 사용할 수 있습니다. 구현 과정을 보면 다소 복잡해 보일 수 있지만, 그래도 천천히 단계를 밟으면 쉽게 이해할 수 있습니다. 저는 Swift로 구현을 해볼건데요, 마지막에 Java 로 구현.. 2021. 3. 24.
플로이드 와샬 (Floyd Warshall) 플로이드 와샬 역시 벨만 포드나 다익스트라와 같은 최단 경로 찾기 알고리즘입니다. 다만, 1:N 최단 경로를 찾는 벨만 포드와 다익스트라와 달리, 플로이드 와샬은 N:N 사이의 최단 경로를 찾습니다. 그렇기 때문에 비용을 저장하는 배열로 이중 배열을 사용하게 됩니다. 순환만 발생하지 않는다면 음수 가중치도 가능하며, 기본적으로 동적계획법으로 접근하게 됩니다. 플로이드 와샬은 가능한 모든 경유지에 대해 모든 정점에서 모든 정점으로 가는 최단거리를 확인하기 때문에, 시간복잡도는 O(N^3)이 나옵니다. 역시 n:n 경로라 그런가 다른 알고리즘들보다 시간이 많이 걸리네요ㅎ.. 먼저 플로이드 와샬을 구현하기 위해서 좀 복잡하지만 아래와 같은 그래프를 사용하겠습니다. 그래도 보는사람 쉽게 보시라고 제가 색도 다르.. 2021. 3. 23.
다익스트라 (Dijkstra) 오늘은 최단거리 구하는 알고리즘 중 다익스트라 알고리즘에 대해 알아보려 합니다. 학교에서 갓 2학년에 되었을 때 알고리즘 수업시간에 다익스트라를 배웠었는데요, 사실 1학년 말에도 과 학회 선배들이 다익스트라를 알려줬었습니다. 하지만 저는 이것만큼 거부감드는게 없었어요ㅠㅠ 그냥 다익스트라 라는 단어 자체가 너무 어려워 보였던 것 같습니다. 하지만 이제와서 다시보니 왜 이렇게 간단한 개념을 이해조차 못했는지.. 이렇게 보니 저도 그 때보다 성장하긴 했나봐요ㅎㅎ.. 다익스트라는 V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점 (S) 에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (1:N) 입니다. 벨만-포드 알고리즘과 달리 음의 가중치를 가지지 않아, 각 정점을 최대 한.. 2021. 3. 9.
벨만-포드 (Bellman-Ford) 오늘은 최단 경로를 찾는 대표적인 기법 중 하나인 벨만-포드 알고리즘을 알아보려 합니다. 벨만-포드는 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점 S 에서부터 다른 정점까지의 최단경로 (1:N) 를 구하는 알고리즘입니다. 다익스트라와 달리 음의 가중치를 가진 간선을 가질 수 있고, 때문에 음의 사이클의 존재 여부를 확인해주어야 합니다. 최단거리를 구하기 위해 최대 (V-1)번 E개의 모든 간선을 확인하고, 음의 사이클을 확인하기 위해 한 번 더 E개의 간선을 확인합니다. 따라서 벨만-포드 알고리즘은 O(VE)의 시간복잡도를 가지게 됩니다. 구체적인 벨만-포드 Swift 코드를 보기 전에, 벨만-포드 알고리즘의 구현을 슈도 코드(Pseudo Code)로 먼저 보겠습니다. 슈도 코드.. 2021. 3. 8.
크루스칼 (Kruskal) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 보통 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하는 문제에서 적용됩니다. 크루스칼 알고리즘에서는 간선 리스트를 많이 이용합니다. 아래와 같이 방향이 있는 그래프에서는 출발, 도착 지점을 기록하고 비용이 있는 경우 추가적으로 기록해줍니다. 만약 방향이 없는 그래프라면 출발과 도착의 순서는 상관이 없습니다. 그럼 크루스칼을 한 번 구현해볼까요? 크루스칼을 구현하기 위한 단계를 간단하게 정리해보았습니다. Step 1. 비용이 적은 순서대로 간선 리스트를 정렬해줍니다. Step 2. 가장 위의 간선(비용이 가장 적.. 2021. 3. 4.
Disjoint-Set / Union-Find (디스조인트 셋, 유니온 파인드) 저는 예전에 디스조인트 셋이 유니온 파인드인지 몰라서 엥? 디스조인트 셋? 이건 뭐랭 했었는데 알고보니 같은 말이었네요ㅋㅋㅋ 그래서 말이죠, 오늘은 크루스칼에서도 사용되는 Disjoint Set을 알아볼게요. Disjoint Set의 원리는 서로소 집합과 연관되어 생각하면 됩니다. 새로운 집합을 추가하거나, 기존의 집합과 합치거나, 집합에 어떤 원소가 들어있는지 찾는 연산을 거의 선형시간에 가깝게 수행하는 자료구조라고 할 수 있죠. Disjoint Set이 Union-Find라고도 불리는 이유는, Disjoint Set을 구성하는데에 union과 find라는 함수? 개념? 을 사용하기 때문입니다. find를 통해서 a라는 요소가 b라는 요소와 같은 집합인지(연결되어 있는지) 를 확인 할 수 있고, uni.. 2021. 3. 3.
Lower / Upper Bound Binary Search (이분 탐색) 가 '원하는 값 x를 찾는 과정' 이라면, Lower Bound는 '원하는 값 x 이상이 처음 나오는 위치를 찾는 과정' 입니다. 마찬가지로 Upper Bound는 '원하는 값 x를 초과한 값이 처음 나오는 위치를 찾는 과정' 입니다. 따라서 Lower Bound와 Upper Bound를 이해하기 전에 Binary Search (이분 탐색) 에 대해 먼저 이해하고 오셔야 합니다❗️❗️ Lower Bound 의 계산 과정은 이분 탐색과 다를 바가 없습니다. 1. 탐색할 리스트는 정렬되어 있어야 한다. 2. start와 end, mid 변수로 이분탐색을 시작한다. 3. mid의 값이 number보다 작을 때 start를 mid+1로 설정한다. 4. mid의 값이 num.. 2021. 2. 26.
투 포인터 (+ 백준 2003) 오늘은 투 포인터라는 개념을 알아보겠습니다! 투 포인터는 알고리즘.. 이라기보다는 개념이라고 하는게 더 맞는 표현인 것 같아요. 1차원 배열을 두고 start, end 라는 두 개의 인덱스를 사용해서 답을 구하기 때문에 Two Pointer (투 포인터) 라는 이름이 붙었습니다. 사실상 두 개의 인덱스 (포인터) 를 사용한다는 것 외에 특별히 설명할 수 있는게 없어서 오늘은 백준 2003번: 수들의 합 2 를 예시로 투 포인터를 설명해보려 합니다. 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤.. 2021. 2. 25.
Linked List (링크드리스트) 링크드 리스트는 이름과 같이 하나하나의 요소가 연결되어 리스트를 이루는 구조입니다. 그리고 보통 싱글 링크드 리스트 (Single Linked List)와 더블 링크드 리스트 (Double Linked List)로 나뉩니다. 링크드 리스트를 사용하게 되면, 새로운 요소를 넣을 때 그 요소와 원래의 요소들을 연결하기 때문에 미리 데이터 공간을 할당할 필요가 없어집니다. 하지만 연결을 위한 별도 데이터 공간이 필요하기 때문에 저장공간 효율이 높지는 않습니다. 중간 데이터를 삭제할 때도 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하죠. 하지만 만약 데이터를 얼마나 집어넣을지 모르는 상태라면 링크드리스트를 사용해보는 게 좋습니다. 애초에 많은 데이터 공간을 할당하고 시작하는 것보다 리스트에 추가해.. 2021. 2. 24.

티스토리툴바