미가공 필기(알고리즘)24

• 

  위상정렬 (Topological Sort) 위상정렬 (Topological Sort) 선후 관계가 정의된 그래프 구조에서 정렬하기 위해 사용 그래프가 순환 구조 가지면 사용 불가 동작 진입 차수 테이블 생성 및 진입 차수 계산 진입 차수가 0인 노드 큐에 넣기 (순서 상관 X) 큐에서 노드 꺼내 연결된 노드들 진입 차수 감소 ( -1 해준다), 진입 차수가 0이 되면 큐에 넣기 큐가 비어버릴 때 까지 3번 반복하며 꺼낸 노드들 줄세우기 (이게 위상 정렬 결과값) 백준 문제 : 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A.. 미가공 필기(알고리즘) 2022. 2. 23.

• 

  유니온 파인드( Union Find ) 그래프 알고리즘 합집합 찾기, 상호 배타적 집합 여러 노드 존재시, 두 개의 노드 선택하여 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 2가지 연산 Find : x 가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x 와 y가 포함되어 있는 집합을 합치는 연산 미가공 필기(알고리즘) 2022. 2. 18.

• 

  220117 이분탐색 : UpperBound vs LowerBound Lower bound 는 타겟보다 같거나 큰 값이 처음 나오는 위치 Upper bound 는 타겟보다 처음으로 큰값이 나오는 위치 이진 탐색에서 Pivot == Target 인 경우 return 하는데 이것을 LowerBound, UpperBound 를 찾는 경우에는 Pivot == Target 일 때 low 나 high 를 조절해서 적절한 위치를 찾아주어야 한다. 미가공 필기(알고리즘) 2022. 1. 17.

• 

  210713 NP vs P Polynomial problems(P) : 다형식 시간으로 해결되는 문제 ex) 정렬 : O(nlog n) , O(n^2) , 등등 Exponential problems(E) : 지수 부분이 n에 따라 무한대로 증가하는 문제 ex) n^n , n^(n^2), 2^n Interactable (Non - Computable) Problems (I) -> 결정할 수 없는 문제 ex) Halting (어떤 프로 그램이 무한 루프에 빠지는지 알아내는 알고리즘) 알고리즘에서 핵심적인 문제 : Exponential 문제를 푸는 법은 아는데 이것을 polynomial time에서 해결하는 방법, 애초에 할 수 있는지를 모름 Ex) 0/1 Knapsack -> O(nW) -> O(2^n) 되면 Exponential 이.. 미가공 필기(알고리즘) 2021. 7. 13.

• 

  210712 Matrix Multiplication , 플로이드-와샬(Floyd-Warshall 알고리즘) 모든 쌍의 최단 경로(All Pairs Shortest Path, ASP)의 대표적인 알고리즘 Matrix Multiplication 예시 플로이드-와샬(Floyd-Warshall 알고리즘) 거처가는 정점을 기준으로 최단 거리를 구하는 것 다익스트라,벨만-포드의 경우는 간선 하나씩 늘어나면서 계산, 반면 플로이드-와샬은 경유하는 정점이 하나씩 늘어나면서 계산 D : 그래프의 가중치를 담은 인접행렬 , 모든 쌍의 최단경로 비용 표시 π : 선행자 인접행렬 , 최단 경로 그 자체를 구할 때 사용 k 정점을 거쳤을 때 거리가 그대로거나 더 크다면 그대로 , 작아졌다면 값을 갱신 하는 과정 pseudo code 시간 복잡도 : O(n^3) 공간 복잡도 : O(n^2) 예시 정점의 개수 4 까지 하여 나온 행렬들.. 미가공 필기(알고리즘) 2021. 7. 13.

• 

  210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra) 최단 경로(Shortest Path)를 찾는 대표적인 알고리즘들 중 일부 벨만-포드(Bellman-Ford) 벨만포드는 가중치가 음수일 경우에도 사용가능 ( 다익스트라와의 차이점 ) 초기화 : 간선 검사 순서 임의로 정하는 등등 앞서 정한 순서대로 모든 간선 확인하며 Relax ( 정점에 기존 보다 더 낮은 가중치로 도달할 수 있으면 값 갱신 == 최단거리 값 갱신) 해줌 정점의 개수 - 1 번 만큼 반복 시간복잡도 : ( 간선의 개수 ) * ( 정점의 개수 -1 ) => O ( 간선의 개수 * 정점의 개수 ) 다익스트라(Dijkstra) Greedy 알고리즘이라고 할 수 있음 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단경로를 구하는 알고리즘 효율적, 실생활에서 많이 사용됨 ex) gp.. 미가공 필기(알고리즘) 2021. 7. 13.

• 

  210708 최소 신장 트리 with Kruskal, Prim 알고리 최소 신장 트리 (Minimum Spannig Tree, MST) 신장 트리(spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 //신장 트리(spanning Tree) : 모든 정점을 포함하고, 정점 간 서로 연결이 되며 사이클이 존재하지 않는 그래프 Kruskal, Prim 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘 Kruskal 모든 간선들 중에서 가중치가 가장 낮은 간선부터 선택하는 방식 단, 선택하는 과정에서 사이클이 만들어지는 경우에는 선택하지 않는다 n개의 정점을 가지는 그래프일 경우, n-1 개의 간선 선택하면 종료 시간복잡도 : 간선을 오름차순으로 정렬하는 것에 수행시간 좌우되기에 최선의 선택을 한다고 가정하면, O((간선의 수) * log_2 (간선의 수).. 미가공 필기(알고리즘) 2021. 7. 10.

• 

  210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS, Breadth - First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 즉 깊게 보다 넓게를 우선시한 탐색 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 활용함 BFS의 과정 시작 정점 방문 깊이 1인 모든 노드 방문 깊이 2인 모든 노드 방문.... (반복) 더 이상 방문할 곳 없으면 탐색 마침 노드 방문 세부 과정은 (큐에서 꺼낸) 노드를 방문하였을 경우 큐에서 꺼낸 노드 방문 큐에서 꺼낸 노드와 인접한 노드들 모두 방문 방문한 노드들 큐에 삽입, 더 이상 없다면 큐에서 노드 꺼냄 이런 과정을 반복한다 예시 시간복잡도 : 인접 행렬 사용시 : O(노드수 +간선수) 인접 리스트 사용시 : O(노드수^2) 깊이 우선 탐색(DFS, Dep.. 미가공 필기(알고리즘) 2021. 7. 9.

• 

  210707 DP - 배낭 문제 (Knapsack Problem) 배낭 문제 (0/1 Knapsack Problem) 배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 0/1 knapsack = 물건 못 쪼갬 Fraction knapsack = 물건 쪼갤 수 있는 문제 사실 kanpsack 문제는 dp에 있어야... 예시 문제 해결법 시간 복잡도 , 공간복잡도 미가공 필기(알고리즘) 2021. 7. 8.

• 

  210707 그리디 알고리즘(Greedy, 탐욕) 동적 프로그래밍(DP) 을 사용할 때 너무 많은 작업을 하는 경우가 발생하기에 보완하는 목적으로 생김 차이점 : 그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 방법 활동 선택 문제 (Activity Selection Problem) 활동 선택 문제란, 한번에 하나의 활동만 처리할 수 있는 하나의 방에서 주어진 활동들에서 최대한 많은 활동을 처리할 수 있는 스케줄을 짜는 문제입니다. 문제를 해결하는 아이디어로는 보통 평범하게는 활동시간이 짧은 순으로 정렬하여 짧은 것부터 선택하는 등의 방법들을 생각할 수 있지만, 최적의 방법은 끝나는 시간순으로 선택하면 됩니다. 허프만 부호화 (Huffman Coding) 문자의 빈도나 확률 정보 등을 이용하여 통계적으로 압축하는 방법 압축할 문자.. 미가공 필기(알고리즘) 2021. 7. 8.

• 

  210706 동적 계획법(DP) 2- LCS ,OBST LCS ( Longest Common Subsequence) - 최장 공통 부분수열, 문자열 를 DP로 해결 LCS의 예시) 목표: 부분수열이기에 중간에 맞지 않다면 문자 사이를 건너뛰어 공통되면서 가장 긴 문자열을 찾는 것 해결법 : 를 다시 정리하면 문자열 X, 문자열 Y의 한 글자씩 비교 두 문자가 같다면 LCS[i - 1][ j - 1 ] +1 두 문자가 다르다면 LCS[i - 1][ j ] 와 LCS[ i ][ j - 1 ] 중 큰 값 표시 1 ~ 3 번 과정 반복 앞서 예로 들었던 malestrom 과 becalm 으로 과정을 보이면 한 단어를 기준으로 잡고 한 글자씩 잡고 위의 점화식대로 테이블을 채워나간다 예를 들어 b를 기준으로 잡고 m,a,l,e....m 까지 검사 이 경우 문자가 같은.. 미가공 필기(알고리즘) 2021. 7. 7.

• 

  210705 동적 계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming, DP) vs 분할 정복법(Divide and Conquer) 문제를 분할하여 작은 문제로 만들어 해결한 후 합쳐서 문제 해결하는 것은 동일 동적 계획법은 서브 문제들 간의 관계가 존재하여 overlapping (작은 문제들이 중복되는 일) 발생 => 작은 문제들의 결과 저장하여 다시 계산하는 일 생략 서브 문제들간의 overlapping 없음 최적 부분구조(Optimal Substructure) 전체 문제가 최적(optimal)구조가 되려면 그 서브 문제들도 최적화 된 솔루션으로 해결가능 해야 함. => 문제를 해결할 때 서브 문제들을 해결하여 그 결과들을 이용하여 최종적인 답 구함 이러한 구조를 가진 문제로 대표적인 예가 최단 경로 문제 피보나치 210.. 미가공 필기(알고리즘) 2021. 7. 6.