2019. 5. 5. 21:40ㆍ코딩/알고리즘
간단간단하게 정리해보는중..
big o 표기법
- 기본적으로 worst caes를 생각하고 만듬
- 알고리즘의 수행시간을 정량화함
이분탐색은 O(logN)
정렬은 O(NlogN)이 최대 - 퀵소트, 병합 정렬등
병합정렬은 stable sort -> 원래의 순서를 유지시키면서 정렬함
거듭제곱을 빠르게 연산하는 법
- 분할정복 / 2진수 / 트리를 기억하자
공간복잡도는 용량 - 배열크기 등
시간복잡도는 구동시간 - 반복문/자료구조가 걸리는 시간 등
비트연산자
~ NOT, & AND, | OR, ^ XOR, << L-shift, >> R-shift
파라매트릭 서치
- 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것
- 어느시점부터 답이 되고 어느시점부터는 안되는지..
선형 자료구조 : 데이터가 일렬로 나열되어 있음
- 배열, 연결리스트, 스택, 큐
비선형 자료구조 : 데이터가 특정한 형태를 띄고 잇음
- 트리, 그래프
배열)
- 데이터 접근 용이
- 삽입/삭제 어려움!!
- 구조가 간단해서 프로그램 작성 쉬움
연결리스트)
- 데이터 접근 느림
- 삽입/삭제 용이!!
- 포인터를 위한 추가공간 필요. 프로그램 작성이 어려움
스택)
- 삽입/삭제연산이 한방향(뒤)에서 이루어짐.
- 링크드리스트로 구현됨
- LIFO(Last In First Out) -> 나중에 삽입된 데이터가 먼저 삭제됨. 후입선출
- 스택에 데이터가 삽입될 위치를 Top이라고 한다
큐)
- 뒤에서 삽입 연산, 앞에서 삭제 연산이 이루어짐
- 스택과 마찬가지로 링크드리스트로 구현됨
- FIFO(First In First Out) -> 먼저 삽입된 데이터가 먼자 삭제됨. 선입선출
- 데이터가 삭제될 위치 : Front 또는 Head
- 마지막 데이터가 삽입된 위치 : Rear / Tail
- 양방향에서 삽입련산과 삭제연산이 모두 이루어지는 큐 = 덱(deque)
- 삽입은 push 또는 Enqueue, 삭제는 pop 또는 Dequeue
트리)
- 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조
- 부모(Parent)-자식(Child)관계로 표현됨
- 1개 이상의 노드를 갖는 집합. 하단의 조건들을 만족하는 것을 트리라고 한다
>> Root 노드가 존재함. 트리의 부분트리(SubTree) 또한 트리구조를 따름
- 루트 노드(Root Node) : 트리의 최상위 노드. 한 트리당 하나만 존재!
- 깊이(Depth) : 루트노드에서 해당 노드까지 도달하는데 사용되는 간선의 수
참고로 루트노드는 깊이가 0이다
- 레벨(Level) : 노드의 깊이 + 1. 현재 노드의 층 수라고 보면 될거같다
- 부모 노드(Parent Node) : 부모-자식 관계에서 상위 계층의 노드.
상위 계증에 있을수록 깊이와 레벨이 낮다
- 자식 노드(Child Node) : 부모 자식 관계에서 하위 계층에 있는 노드
- 형제 노드 : 부모가 동일한 노드
- 조상 노드 : 해당 노드의 부모부터 루트까지 가는 경로에 존재하는 노드
- 후손 노드 : 해당 노드를 루트로 하는 서브트리에 있는 모든 노드
- 노드의 차수(Degree) : 노드의 자식 수
- 트리의 차수 : 해당 트리 내 모든 노드의 차수 중 최대값
- 내부 노드 : 자식(Child)가 존재하는 노드
- 외부 노드(Leaf node) : 자식이 없는 노드. 트리의 가장 끝에 존재
- 높이(Height) : 루트 노드에서 해당 노드까지 도달하는데 지나간 정점 개수
노드 중 가장 높이가 높은 노드의 높이를 트리의 높이라고 함
이진 트리)
- Degree가 2 이하인 트리. 즉 한 노드당 자식이 최대 둘밖에 없음
- 트리 구조들 중에서 가장 많이 쓰이는 트리 구조이다
- 자식이 최대 2개이기 떄문에 자식을 왼쪽/오른쪽 자신으로 구분한다
- 높이가 N인 이진 트리의 최대 노드 개수는 2^N - 1개이다.
- 정 이진트리(Full Binary Tree) : 모든 Degree가 0 또는 2인 이진트리
- 포화 이진트리(Perfect Binary Tree)
>> Full Binary Tree에서 모든 단말 노드의 깊이가 같은 이진트리
>> 높이가 H인 포화 이진트리의 개수 : 2^H -1
>> 노드가 N개인 포화 이진트리의개수 : log2(N+1)
>> 깊이가 D인 포화 이진트리의 단말 개수 : 2^D
- 완전 이진트리(Complete Binary Tree)
>> 마지막 레벨의 노드가 왼쪽에 몰려있고, 마지막 레벨을 제외한 구조가 포화 이진트리 구조일때 완전 이진트리라고 부름
- 사향 이진 트리(Skewed binary Tree) : 연결리스트처럼 한줄로 연결되어있는 이진트리
- 이진트리는 연결리스트 또는 1차원 배열을 이용하여 구현 가능함
>> 연결리스트의 경우, data, left_child, right_child를 가짐
>> 1차원 배열의 경우 Parent는 i/2, left_child는 i*2, right_child는 I*2+1
이진트리의 순회)
- 트리는 비선형 구조이기 때문에 모든 노드를 for문 한번으로 방문이 불가
- 이진트리의 순회는 Left_child 탐색, Right_child 탐색, 현재 노드 방문 세가지 주요 과정을 통해 진행됨
- 모든 순회는 루트노드에서 시작됨
- 전위 순회(Pre-order) : 현재 노드 방문 - 왼쪽 자식 탐색 - 오른쪽 자식 탐색
- 중위 순회(In-order) : 왼쪽 자식 탐색 - 현재 노드 방문 - 오른쪽 노드 탐색
- 후위 순회(Post-order) : 왼쪽 자식 탐색 - 오른쪽 자신 탐색 - 현재 노드 방문
힙)
- 완전 이진트리 형태의 자료구조
- 힙 조건(Heap Condition)을 만족함 : 각 노드의 키값 > 자식노드의 키 값
>> 즉 루트노드가 가장 큰 키 값을 가지고, 리프 노드(Leaf Node)가 가장 작다
- 일차원 배열로 구현함
- 일반적으로 그룹을 정력(Heap Sort)하거나, 입력된 데이터 안에서 Max/Min값을 찾을때 사용한다.
- 데이터의 삽입/삭제가 빠르며, 각각의 수행시간이 O(logN)이다.
- 최소 힙 : Heap Condition = 부모 노드의 키 값 < 자식 노드의 키 값
- 최대 힙 : Heap Condition = 부모 노드의 키 값 > 자식 노드의 키 값
- 힙의 삽입 연산
>> 1. 트리의 가장 마지막 위치에 노드 삽입
>> 2. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인
>> 3. 만족하지 않는다면 부모와 자식 값 바꿈
>> 4. 조건에 만족하거나, 추가된 노드가 루트에 닿을때까지 2~3 반복
- 힙의 삭제 연산
>> 1. 루트 노드를 삭제한다(제일 크거나 제일 작을 것이므로...)
>> 2. 트리의 가장 마지막 노드를 루트 자리로 삽입
>> 3. 바꾼 위치의 노드가 힙 조건을 만족하는지 확인
>> 4. 만족하지 않는다면 왼쪽/오른쪽 자식 중 적합한 노드와 키값을 바꿈
>> 5. 조건을 만족하거나 리프노드 도달할때까지 3~4번 반복
- 위의 삽입.삭제 연산은 완전이진트리의 루트부터 리프노드까지 연산을 하므로, 노드가 N개일때 수행시간은 O(logN)이다
우선순위 큐)
- 이름은 큐이지만, 힙을 활용한 자료구조이다.
- 각 데이터에 우선순위를 부여하여, 큐에 넣은 데이터를 꺼낼때 우선순위가 높은 데이터를 먼저 꺼내는 자료구조
- 주로 정의된 우선순위를 Heap Condition으로 가지는 Heap 자료구조를 통해 구현된다
- 우선순위 큐는 기본적으로 아래의 두가지 연산을 지원
>> 큐에 데이터를 우선순위를 지정하여 추가
>> 큐에서 가장 우선순위가 높은 데이터를 제거하고 반환
- 힙을 통해 우선순위큐를 구현하면 위 연산이 아래와 같이 정의됨
>> Heap에 데이터를 우선순위(힙 컨디션)를 지정하여 삽입연산 수행
>> Heap의 삭제연산을 수행하고 삭제된 데이터를 반환함
인덱스 트리)
- 구간의 합을 계산하는데 특화된 트리
- 포화 이진트리 형태이다
- 일반적인 구간의 합 복잡도가 O(NM)인데, 인덱스트리는 O(MlogN)
- 각 노드는 다음의 의미를 가짐
>> 리프 노드 : 배열에 적혀 있는 수
>> 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합
- 리프 노드의 개수가 N개 이상인 포화 이진트리의 높이는 최소 logN이다
>> 포화 이진트리이므로!!
- 리프 노드의개수가 N개보다 많아 비어있는 공간이 발생할 경우 구조에 지장이 가지 않도록 초기값을 설정한다
- 자세한 내용은 책 참조!
해싱)
- 입력된 데이터(Key)를 해쉬 함수를 통해 얻은 주소로부터 그 위치를 직접 참조하는 방법이다
- 탐색/삽입/삭제 연산 모두 해시함수를 거치는 시간만 소요되기 때문에 일반적으로 O(1)의 시간복잡도를 가진다
- 해시 표(Hash Table)
>> 버킷(Bucket)과 슬롯(Slot)으로 구성된 이차원 배열
>> 버킷 개수 : 해시 함수를 통해 나오는 주소 값의 범위
>> 슬롯 개수 : 각 버킷에 저장할 수 있는 데이터(key)의 개수
셋)
- 집합을 정의하는 자료구조. 동일한 자료형을 모아놓은 것
- 집합의 모든 원소는 유일하다! 즉 key이므로 중복이 허용되지 않음
- 삽입/삭제/탐색의 세가지 연산을 지원
- 구현방식에 따라 해쉬셋(hash set), 트리 셋(tree set)등이 존재
맵)
- key와 value로 이루어진 객체를 저장하는 자료구조
- Set과 같이 key값의 중복을 허용하지 않으며, value값을 제약이 없다.
- hash map, tree map이 존재하며 각가의 특징은 set과 같다
그래프)
- 현실세계의 사물이나 개념간의 연결관계를 수학적 모델로 단순화하여 표현한것
- 정점(vertex, node) 집합 V = { V1, V2, V3 ... Vn }
- 정점간의 연결관계들을 나타내는 간선(Edge, Link, Arc) 집합
- 유향 간선(Directed Edge) : 방향이 있는 간선
- 무향 간선(Undirected Edge) : 방향이 없는 간선
- 인접(Adjacent) : 정점 Vi, Vj에 대해 간선 e = (Vi, Vj)가 존재한다 = Vi와 Vj는 인접한다!
- 부속(Incident): 정점 Vi, Vj에 대해 간선 e = (Vi, Vj)가 존재한다 = 간선 e는 정점 Vi와 Vj에 부속한다.
- 차수(Degree) : 정점에 부속된 간선의 수
>> in-degree : 방향 그래프에서 정점에 들어오는 간선의 수
>> out-degree : 방향 그래프에서 정점에서 나가는 간선의 수
- 다중 간선 : 두개의 정점끼리 연결된 간선 수가 두개 이상이면 다중 간선
- Self-loop : 자기 자신에서 나가서 자기 자신에게 들어오는 간선
- 경로(Path) : 정점과 간선이 교대로 구성된 sequence
- 회로(Cycle) : 시작정점과 끝정점이 같은 경로
>> 정점과 간선이 중복되지 않은 경로/회로를 단순 경로/회로(Simple path/cycle)이라고 한다
- 연결됨(Connected) : 정점 Vi에서 정점 Vj로의 경로가 존재하면, 정점 Vi와 정점 Vj는 연결되어 있다고 한다.
그래프 종류)
- 무향 그래프 : 무향 간선으로 이루어짐
- 유향 그래프 : 유향 간선으로 이루어짐
- 가중치 그래프 : 가중치(비용)를 갖는 간선으로 이루어진 그래프
- 정규 그래프 : 모든 정점이 동일한 차수를 가지는 그래프
- 완전 그래프
>> 임의의 두 정점 Vi, Vj에 대해서 Vi, Vj를 잇는 간선 Edge(Vi, Vj)이 존재하는 그래프 -> 즉 모든 정점이 연결되어 있다!
>> 완전그래프이면 정규그래프이다!!
>> N개의 정점을 가지는 방향그래프 : 간선 개수 = N(N - 1)
>> N개의 정점을 가지는 무향그래프 : 간선 개수 = N(N - 1)/2
- 연결 그래프 : 임의의 두 정점 Vi, Vj에 대해서 경로 Path(Vi, Vj)가 존재하는 그래프 -> 즉 동떨어져 있는 정점이 없음.
- 부분 그래프
>>어떤 그래프의 정점집합의 부분집합과 그에 속한 간선들로 이루어진 그래프
>>어떤 그래프의 간선집합의 부분집합과 그에 속한 정점들로 이루어진 그래프
- 트리 그래프
>> 순환을 갖지않는 연결 그래프
>> 임의의 두 정점에 대하여 경로가 정확히 1개 존재한다
>> 하나 이상의 정점을 가지며, 임의의 간선 e를 제거한 그래프는 연결 그래프가 아니다
-> 경로가 하나씩만 존재하므로, 간선이 제거되면 연결이 되지 않기 때문
-> 순환을 가지지 않으므로 제거된 쪽으로 연결되는 다른 경로도 없다
그래프 표현)
- 간선 리스트(Edge List)
>> 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대하여 E * 2(또는 E * 3)이차원 배열(A)에 간선 정보를 저장한다
>> 어떤 두 정점 Vi, Vj를 연결하는 간선 E = (Vi, Vj)에 대하여...
-> A[k][0] = Vi, A[k][1] = Vj 이다
-> 즉 페어로, 0 1에 Vi, Vj를 넣는다는 뜻
>> 가중치 그래프의 경우 배열의 3번째 열에 간선의 가중치를 저장한다
- 인접 행렬(Adjacency Matrix)
>> 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해 V * V 이차원 배열(A)에 그래프 정보를 저장한다
>> 어떤 정점 Vi, Vj를 연결하는 간선 e가 존재(인접)한다면 A[i][j] = 1. 없다면 0
- 인접 리스트(Adjacent List)
>> 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서, V개의 연결리스트로 그래프 정보를 저장한다.
>> 일반적으로 List나 Vector의 배열로 구현한다
>> 인접리스트가 가장 빠르고 효율적이다!
서로소 집합(Union-Find, Disjoint set) )
- 교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)히거 조작(Union)할 수 있는 자료구조
- Union 연산 : 어떤 두 원소 a,b에 대해서 union(a,b)는 각 원소가 속한 집합을 하나로 합치는 연산
- Find 연산 : 어떤 원소 a에 대해서 a가 속한 집합을(집합의 대표 번호) 반환
- 1차원 배열로 표현 시.. Union연산은 O(n), Find 연산은 O(1)
- 트리로 표현시... 수행시간은 트리 높이에 비례한다
DAG(Directed Acyclic Graph) )
- 순환을 가지지 않는 방향그래프 (비 순환 방향 그래프)
- 일반적으로 우선순위를 가진 일련의 작업들은 DAG 구조를 가짐
- 선행자. 수행자... 잘모르겟다
위상정렬(Topological Sort) )
- DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것!
- BFS로 작성하는 것을 추천. DFS로 해도 상관은 업슴
- 위성정렬은 각 정점을 우선순위에 따라 배치한것
- 일반적으로 위상정렬의 결과는 유일하지 않다!
- 수행과정
>> 1. 자기 자신을 가리키는 간선이 없는 정점을 찾음(in-degree가 0)
>> 2. 찾은 정점을 출력하고 출력한 정점과 그 정점에서 출발하는 간선 삭제
>> 3. 아직 그래프에 정점이 남아있다면 단계 1로 돌아가로고 아니면 알고리즘 종료
DFS)
- 깊이 우선 탐색
- 한 방향으로 쭉 탐색후, 다음 방향으로 탐색
BFS)
- 너비 우선 탐색
- 한 위치에서 갈수 있는 모든 방향을 한칸식 탐색해감
신장트리(Spanning Tree) )
- 무향 연결 그래프 G의 부분그래프이고, G의 모든 정점을 포함하는 트리인 그래프
최소신장트리(Minimum Spaning Tree / MST) )
- 무향 연결 가중 그래프 G에서 간선의 가중치의 합이 최소인 신장트리
- 유일하지 않음! 같은 가중치의 값이 나오는 다른 MST가 있을수 있다
크루스컬(Kruskal's Algorithm) )
- 1. V개의 정점 E개를 가진 가중 그래프 G에서, 모든 간선을 가중치 오름차순 정렬한다
- 2. 정렬된 간선 목록에서.. 처음부터 마지막까지(or V-1개의 간선을 선택할때까지) 아래의 내용을 반복한다
>> 1) 간선 목록에서 하나를 꺼낸다
>> 2) 현재 간선에 연결된 두 정점이 현재 간선 이외의 다른 간선으로 연결되어 있지 않다면, 간선을 선택하여 두 정점이 이루는 트리를 연결
>> 3) 연결되어있다면 다시 1)로 돌아감
>> 즉 정렬 - 코스트 낮은 것부터 선택 - 같은 집합이 아니라면 사용
-> 유니온파인드!
최소 공통 조상(Lowest commom Ancestor / LCA) )
- 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통조상은 A와 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점이다
>> 즉 LCA는 A 혹은 A의 조상, B 혹은 B의 조상인 정점들 중 가장 깊은 정점!
- LCA를 구하기 위해서는 DFS/BFS 탐색을 하여, 각 정점의 깊이와 부모 정점을 저장한다
>> 1. A와 B의 깊이가 다르면, 더 깊은 정점의 부모를 따라 "하나씩" 올라가 서로의 길이를 맞춘다!!
>> 2. 1의 결과가 A=B면 A(or B)가 LCA다
>> 3. 1의 결과가 A!=B면... A와 B의 깊이가 같으므로, A와 B가 같아질때까지 각자 "하나씩" 올라간다!
>> 처음으로 두 정점이 같아진 정점이 LCA이다
- LCA를 구하는 단게에서 하나씩 올라간다는 특징이 있으므로, 트리의 깊이가 H일때 O(H)이다.
>> 즉 최악의 경우 O(N)이 된다
- 이분탐색&DP로 하나씩 올라가는 작업을 2^K씩 올라갈 수 있다
>> DP 배열 정의 : parent[K][V] = V번 정점의 2^K번째 부모 정점 번호
>> DP 배열 점화식 : parent[K][V] = parent[K-1][ parent[K-1][V] ]
- 빠르게 구하는 법
>> 1. 위 점화식으로 parent[K][V]를 채운다
>> 2. 정점 A,B의 LCA는...
-> 1) A/B의 깊이가 다르다면
depth(A) > depth(B) 일 경우 깊이의 차이는 diff = depth(A) - depth(B)
diff와 parent를 이용하여 A의 조상을 따라 올라가, 깊이를 같게함
-> 2) 1)의결과가 A=B면 A or B가 LCA
-> 3) A!=B면 A와 B의 깊이는 같으므로, parent를 이용해 처음으로 A와 B의 부모가 같아지는 A,B 정점을 찾는다
-> 4) LCA는 parent[0][A] = parent[0][B]가 된다!
- 시간복잡도는.. 트리의 깊이가 N-1이므로 O(logN)
- 보통 트리가 최대 10만 정도 하므로.. K를 17로 잡고 -1씩 하면서 내려간다
단절점)
- 정점을 제거했을때, 그래프가 두개 또는 그 이상으로 나누어지게 되는 정점
- 즉 해당 정점 A를 거치지 않는 우회경로가 없는 경우 A는 단절점이다
>> union find로 그룹을 만들어 단절점을 찾을경우.. O(N^2)이므로 시간초과
>> DFS를 사용할 경우 O(N)으로 만들수 있다
-> 방문하지 않은 임의의 점을 선택하여, 거기를 시작으로 DFS 수행
-> DFS로 방문하는 점마다 방문한 순서(order)를 기록한다
-> 자신의 order와 자신과 연결된 정점의 Low case를 확인하여 단절점 여부를 파악한다
-> Low case : 자신 이후로 방문하는 정점 중, 자신을 거치지 않고 방문할 수 있는 정점들의 order중 가장 작은 값
- 내용이 너무 어려워서 직접 보고도 잘 못짜겠음 ㅠㅠ
최단 경로)
- 문제의 종류
>> 단일 출발 : 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단경로 찾기
>> 단일 도착 : 모든 정점에서 출발하여 하나의 정점까지 최단경로 찾기
>> 단일 쌍 : 특정 정점 A에서 B까지 갈 수 있는 최단경로를 구하는 문제
>> 전체 쌍 : 모든 정점들 사이의 최단 경로를 찾는 문제
- BFS, 다익스트라, 벨만-포드, 플로이드-워셜 등을 쓰면 된다
- BFS : 가중치 없을 경우 or 모든 가중치 동일할 경우 가장 빠르게 구할수있다
- 다익스트라 : 음이 아닌 가중그래프에서 단일쌍/단일출발/단일도착 최단경로
- 벨만-포드 : 가중그래프. 단일쌍/단일출발/단일도착 최단경로(음수 가능!)
- 플로이드-워셜 : 전체 쌍 최단경로 문제
다익스트라 알고리즘)
- 그냥 짜는 법도 있지만 우선순위 큐(힙)을 이용하자
- 1. D[K] (출발점부터 K까지의 최단거리를 저장하는 배열)를 무한대로 초기화
- 2. D[S] = 0 (S : 출발점). 최소 힙(우선순위 큐)에 S를 넣는다
- 3. 우선순위 큐에서 맨 위에 있는 정점 I를 꺼낸다(큐가 비어있다면 알고리즘 종료)
- 4. 정점 I와 인접한 모든 정점 J에 대해서...
>> 현재까지 저장된 S에서 J까지의 최단거리(D[J])보다 S에서 I를 거쳐 간선 E를 이용하여 J로 가는 거리(D[i] + E.weight)가 더 짧다면...
>> D[J] = D[I] + W로 갱신하고, 우선순위 큐에 정점 J를 넣는다
- 시간복잡도는 O(E logV)
>> 최악의 경우.. 모든 간선을 확인할때마다 거리 배열이 갱신되면, 큐에는 최대 E번 정점을 넣게 된다(즉, 간선의 개수 E만큼 넣는것!)
>> 이경우 하나의 정점을 꺼낼때마다 logE의 연산이 필요
>> 이때는 O(E logE) 가 된다
벨만포드)
- V개의 정점과 E개의 간선을 가진 가중 그래프
- 어떤 정점 A에서 B까지 최단거리는 최대 V-1개의 간선을 사용한다
- 1. D[K] (출발점부터 K까지의 최단거리를 저장하는 배열)를 무한대로 초기화
- 2. D[S] = 0 (S : 출발점).
- 3. V-1번 모든 간선을 확인하여 아래의 조건을 만족할때마다 최단거리배열 갱신
>> 간선 E = (I -> J, 가중치 W). D[I] != INF && D[J] > D[I] + W면 D[J] = D[I]+ W
- 4. V번째 모든 간선을 확인하였을 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가지는 그래프이다.
- 시간복잡도는 O(VE)
>> 최단거리를 구하는데 V - 1번 E개의 모든 간선을 확인하므로.. (V - 1) * E
>> 음의 사이클이 있는지 확인하기 위해 한번더 E개의 간선 확인
플로이드-워셜)
- 정점 사이의 최단 경로는 바로 연결되거나, 경유지를 거치는 경우 두가지이다
>> ex) A -> B 또는 A -> 경유지 -> B
- 만약 경유지(K)를 거진타면 그것을 이루는 부분경로 역시 최단경로이다!
>> ex) A -> K -> B가 최단경로라면 A -> K와 K -> B 역시 최단경로이다
- 부분문제를 이용하는 방법이라 할 수 있다
- 1. D[i][j] = 정점 i에서 정점 j까지의 최단거리를 저장하는 배열
>> D[i][j] = (i == j) ? 0 : INF // i와 j가 같다면 0, 아니면 무한대
- 2. D[i][j]에 간선정보를 저장
>> D[i][j] = W
- 3. for 1 <= 경유지 K <= V
for 1 <= 출발 정점 I <= V
for 1 <= 도착 정점 J <= V 까지의 최단거리를 아래와 같이 갱신
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
- 시간복잡도 : O(V^3) -> 모든 가능한 경유지에 대해서 최단거리를 확인함!
유클리드 호제법)
- 두개의 자연수의 최대공약수(GCD)를 구하는 알고리즘
- a를 b로 나눈 나머지가 r이라면(a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다
>> a % b = r (a > b)일때 GCD(a, b) == GCD(b, r)
- 확장 유클리드 호제법을 사용하면 Ax + By = gcd(x, y)의 해가 되는 A,B 짝을 찾을수도 있다
>> 베주의 정의 라고 하며, a와 b중 하나는 보통 음수가 된다
소수(Prime number) )
- 1보다 큰 정수 p의 양의 약수가 1과 p뿐일때 p를 소수라고 하며, 1보다 큰 정수 n이 소수가 아닐때 n을 합성수(Composite number)라고 한다.
- 서로소 : 두 수가 1 이외의 양의 공약수를 가지지 않는 경우 서로소. 즉 최대공약수가 1!
소수 판별)
- 가장 간단하고 빠른 방법은 루트 N(제곱근 N)보다 작은 소수들로 나누어 보는 법이다
>> 루트 N을 계산하기 귀찮으므로.. for(int i = 2; i * i < N; i++) 처럼 i * i로 계산한다
>> 시간복잡도는 O(root(N) / ln(root(N))
- 에라토스테네스의 체를 이용하는 방법이 보편적이다
>> 소수를 찾으면 소수의 배수들을 모두 지워줌으로써 지워지지 않은 숫자를 찾는다
>> bool 배열을 N만큼 공간을 선언하여 인덱싱으로 접근해서 하는 방식으로 사용
>> 시간복잡도는 O(N loglogN)
오일러파이)
- 서로소를 더욱 빠르게 구하는 방법
- 시간복잡도는 O(N^2 / ln N)
순열)
- n P k = N! / (N - k)!
- N가지의 물건 중 K개의 물건을 순서 구분하여 고르는 경우의 수
- C++에서는 next_permutation을 이용하여 구현할 수 있다
조합)
- n C k = N! / (N - k)! * K!
- N가지의 물건 중 K개의 물건을 순서 구분 없이 고르는 경우의 수
- 파스칼의 삼각형을 이용하여 계산할 수 있다
- D[n][k] =n C k라면.. D[n][k] = D[n-1][k-1] + D[n-1][k]
- O(N^2) 시간복잡도를 가짐. 다만 N*N배열의 공간이 필요하므로 공간복잡도 주의
다이나믹 프로그래밍)
- 부분문제를 이용하여.. 작은문제의 결과를 이용해 큰 문제의 결과를 내는 방법
- 점화식 : 작은 문제의 결과에서 큰 문제의 결과를 계산하기 위한 관계식
- 이것만큼은 정말 문제를 많이 풀어봐야지만 적응이 된다. 좀 더 적응해보자..
- 1차원 dp, 2차원dp, 3차원 dp... 이런식으로 N차원 DP 문제들이 있다
기하 - 용어)
벡터 - 크기와 방향을 가지는 물리량
스칼라 - 크기만을 가지는 물리량
단위 벡터 - 크기가 1인 벡터
영(0) 벡터 - 크기가 0인 벡터. 시점과 종점이 같다
법선 벡터 - 어떤 평면에 수직인 벡터
위치 벡터 - 시점을 원점으로 하는 벡터
>> 모든 벡터는 시점을 원점으로 평행이동하여 위치벡터로 표현 가능
내적)
- 벡터 A와 B가 이루는 각을 θ라고 할때, 스칼라곱 AㆍB = |A||B| cos θ 이다
- 내적의 결과는 스칼라이다!
- 교환법칙, 분배법칙이 성립한다
- 내적의 결과가 0인 경우 A와 B는 수직, 즉 각도가 90도이다
외적)
- 벡터 A와 B가 이루는 각을 θ라고 할때, 벡터곱 A x B = N( |A||B| sin θ ) 이다
>> N : A와 B 모두에 수직인 단위 벡터
- 외적의 결과는 벡터량이다
- 외적의 크기는 A, B 두 벡터가 만드는 평행사변형의 넓이와 같다!
- 교환법칙이 성립하지 않는다
- A x B = 0 이라면 각도는 0도 또는 180도(파이)이다!
- 행렬식을 이용한 외적의 계산에서는 라플라스 전개를 이용한다
CCW )
- 벡터의 외적을 이용하여, 평면상에 세 점이 있을때 점들의 위치관계를 판단할 수 있는 알고리즘
- 화전방향이 반시계인 경우 양수(+)가 나오며, 회전방향이 시계인 경우 음수(-)가 나옴
- 회전하지 않고 일직선에 있는 경우 0이 결과로 나온다
- A x B = |A||B| sin θ
>> CCW(ax, ay, bx, by, cx, cy) = (axㆍby + bxㆍcy + cxㆍay) - (ayㆍbx + byㆍcx + cyㆍax)
- 벡터의 외적을 이용하므로, 다각형의 넓이를 구하는 계산식에서도 사용가능
선분 교차)
- AB, CD 두 선분이 교차하려면, AB를 기준으로 점 C와 D가 반대방향에 있어야하며 동시에 선분CD를 기준으로 점 A와 B가 반대방향에 있어야 한다
- 아래 두개의 수식이 true가 나오면 된다!!
>> CCW(A, B, C) x CCW(A, B, D) < 0
>> CCW(C, D, A) x CCW(C, D, B) < 0
- 단 이때 한 점이 다른 선분 위에 있거나, 두 선분의 끝점이 맞닿아 있는 경우는 위 수식을 사용하여 교차를 판별하면 false가 나온다.. 끝점이 맞닿는 경우를 예외처리하자