푸으름

Algorithm 공부 #15 - 그래프(위상 정렬) 위상 정렬(Topology Sort) ● 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 ● 항상 유일한 값으로 정렬되지 않음 ● 진입 차수 : 자기 자신을 가리키는 에지의 개수 ● 원리 파악하기 노드는 5개이고 각 노드는 1,2,3,4,5 1번 노드는 2번과 3번 노드를 / 2번 노드는 4번과 5번 노드를 / 3번 노드는 4번 노드를 4번 노드는 5번 노드를 가리키는 그래프가 있다고 가정하기 진입차수 배열 D[N] 1 2 3 4 5 0 1 1 2 2 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하기 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼주기 이 과정을 모든 노드의 ..

Algorithm 공부 #14 - 유니온 파인드  ✏️ 유니온 파인드(Union Find)유니온 파인드는 합집합이라는 의미를 지니고 있으며, Disjoint Set이라고도 불린다. Disjoint Set은 상호 베타적 집합이라는 뜻을 가지고 있는데 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용한다.상호 배타적이라는 단어가 헷갈릴 수 있는데, 그냥 부분 집합 간의 교집합에는 원소가 없고, 모든 부분 집합들의 합집합은 전체 집합과 같다는 뜻이다. 쉽게 말해서 여러 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다고 생각하면 될 것 같다. ✏️ Union 연산Union 연산은 말 그대로 Union(합집합)을 만드는 과정이다..

✏️ 문제 링크 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 스택 구조를 이용해서 푸는 문제 ※ '()' 은 레이저 : 레이저를 기준으로 앞에 쌓여있는 막대의 개수를 더해준다 즉 레이저 앞에 스택에 들어있던 '('의 개수, 즉 스택의 크기를 result에 더해준다. ')' 은 닫히는 막대기 : 막대기가 새롭게 추가된다고 생각하기 new_Bar를 ++시켜주고 괄호가 닫혔으므로 스택에 있던 '('의 짝을 찾았다고 생각하기 ..

✏️ 문제 링크 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 false일 때 출력되기 위해서는 버블 정렬 중 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 게 핵심 이중 for문을 다 돌리기에는 N의 값이 크기 때문에 버블 정렬로 풀면 시간 초과가 발생할 수 있음 vector를 생성해 pair쌍으로(입력값, 인덱스) push해주고 sort알고리즘을(O(nlogn)) 통해 v..