Algorithm/concept

Coding Test(정렬 알고리즘)

선택정렬 - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다. - 한번씩 순회를 하고 가장 큰 수를 찾은다음 바꿈 - 시간 복잡도 : O(N*2) - 공간 복잡도 : O(N) int[] arr = {7, 5, 2, 4, 6, 1, 3, 9, 8}; for (int i = 0; i arr[j]) { min = j; } } int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } 삽입정렬 - 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. - 현재위치에서 아래쪽을 순회하며 크기가 작을..

Coding Test(Topological Sort)

위상 정렬(Topological Sort) 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 선행 조건들을 만족하는 일의 수행 순서 특정 노드를 방문하려면, 조건으로 갖는 다른 노드들이 방문된 상태여야함 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다 위상정렬에서 중요하게 쓰이는 개념인 진입차수와 진출차수 1. 진입차수가 0인 모든 노드를 큐에 넣는다(진입차수가 0이라는건 시작점이라는 뜻) 2. 큐가 빌 때 까지 다음의 과정을 반복한다 2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2-2) 새롭게 진입차수가 0이 된ㄷ 노드를 큐에 넣는다 => 결과적으로 각 노드가 Queue에 들어온 순서가 위상 ..

Coding Test(최단 경로 - Dijkstra, Bellman-Ford, Floyd-Warsahall)

다익스트라 알고리즘(Dijkstra Algorithm) 특정한 노드에서 다른 모든 노드로의 최단경로를 구하는 알고리즘 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구함 그리디를 이용한 알고리즘으로 MST의 PRIM()과 유사 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 가중치 없는 경우 1 BFS 가중치 있는 경우 하나의 정점 양수 Dijkstra 음수 Bellman-Ford 모든 정점 Flod-Warsahall 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정..

Coding Test(Prim Algorithm)

Prim의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다. PriorityQueue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사하다. BFS + PriorityQueue 1. 임의 정점을 하나 선택해서 시작 2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 3. 모든 정점이 선택될 때 까지 1,2과정 반복 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리르 구성 하므로 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클..

Coding Test(Kruskal Algorithm)

최소 신장 트리(MST : Minunum Spanning Tree) 신장 트리(Spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 신장 트리(Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않은 부분 그래프 정점이 N개인 무방향 그래프에서 나올 수 있는 최대 간선의 수 : N(N-1)/2 정점이 N개인 방향 그래프에서 나올 수 있는 최대 간선의 수 : N(N-1) 크루스칼 알고리즘(Kruskal Algorithm) O(ElogE) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 = 최소 신장 트리를 만들기 위한 알고리즘 그리디 알고리즘(결정의 순간..

Coding Test(Two Pointer)

리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리 아마 투 포인터를 몰랐다면 완전 탐색을 이용해서 O(N^2)만큼 했을텐데 투 포인터를 이용하면 선형 관계에서 해결 가능 n = 5 # 데이터의 개수 N m = 5 # 찾고자 하는 부분합 M data = [1, 2, 3, 2, 5] # 전체 수열 count = 0 interval_sum = 0 end = 0 # start를 차례대로 증가시키며 반복 for start in range(n): # end를 가능한 만큼 이동시키기 while interval_sum < m and end < n: interval_sum += data[end] end += 1 # 부분합이 m일 때 카운트 증가 if interval_sum == m: count +=..