본문 바로가기

Data Structure🧶5

위상 정렬 Topological Sort 위상 정렬 위상을 기준으로 정렬하는 알고리즘 (위상 : incoming edge) 일의 순서를 정할 필요가 있을때 많이 쓰인다. 위상 정렬 알고리즘 특징 DAG(direct acycle graph)에서 가능한 정렬 방법이다. 사이클이 발생하는 경우 위상 정렬 수행 할 수 없다. 의존성이 없는 노드부터 하나씩 차례대로 처리하여 의존성 높은 순으로 처리한다. * 시간 복잡도 O(V+E) 위상 정렬 알고리즘 순서 각 vertex의 위상(incoming edge수)를 저장한다. 위상이 0인 노드들에 대해 모두 queue에 넣는다. queue에서 node를 꺼내 위상 정렬에 넣어준다. 위상 정보를 하나 낮추고 엣지를 없앤다. 위상이 0이 된 노드들을 큐에 저장한다. 반복 알고리즘 예시 위상 그래프가 이렇게 되어 .. 2021. 6. 13.

그래프 이론 - DFS와 BFS 선형 구조가 아닌 비선형 구조 탐색 위해선 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 사용한다. 너비 우선 탐색은 브루트 포스와 관련이 깊고 깊이 우선 탐색은 백트래킹과 관련이 깊다. DFS 그래프의 모든 정점 방문 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다 즉 더 따라갈 간선이 없을 경우 이전으로 돌아간다. 이를 구현하기 위해 지금까지 거쳐 온 정점 모두 저장 해 둬야 하는데 재귀 호출 이용하면 이 같은 일을 간단하게 할 수 있다. 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문이다. DFS 특징 방문한 정점을 알아야 한다. 따라서 각 정점의 방문 여부를 저장하는 자료구조가 필요 더이상 방문할 정점이 없으면 이전 정점으로 돌아가야 한다 -> 재귀, stack 이용 그래.. 2021. 4. 21.

LCS 최장 공통 부분 수열 DP 🔘최장 공통 부분 수열 이란? (LCS, Longest Common Subsequence) 두개의 문자열이 주어졌을 때 공통으로 들어 있는 부분 수열 중 가장 긴 수열을 말한다. 예를 들어 ABCDE와 ACDFG이 주어졌다면 두 문자열의 공통 부분 수열은 {A}, {C}, {D}, {AC}, {AD}, {ACD} 이고 LCS는 바로 {ACD}를 말한다. - LCS와 LCS (최장 공통 부분 수열과 최장 공통 부분 문자열) 사실 LCS는 뜻이 두가지다 ..! LCS( Longest Common Subsequence) 이 있고 최장 공통 부분 문자열LCS( Longest Common Substring) 이 있다. 위 두 문자열 ABCDE와 ACDFG에 대해서 최장 공통 부분 수열는 {ACD}지만 최장 공통 .. 2021. 3. 1.

그래프 이론 - 이분 그래프 🔘이분 그래프란 ? 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프 ➿이분 그래프 특징 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다. 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 무조건 같은 색으로 칠해진다. 연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다. 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다. ☑️이분 그래프 판별 알고리즘 서로 인접한 정점이 같은 색이면 이분 그래프가 아니다. BFS, DFS 로 탐색하면서 정점 방문 할 때마다 두.. 2021. 2. 25.

정렬 - 선택, 버블, 삽입, 병합, 힙, 퀵 1. 선택 정렬(Selection sort) -> O(n^2) 에 대해 i = 0 k= n -1, min 값을 찾아 i 자리와 swap 마지막 인덱스까지 돌면서 비교 코드 : void selectionSort(int arr[], int size){ int minIndex; int i, j; for(int i = 0; i O(n^2) 현재 배열 요소와 다음 배열 요소를 비교하고 교환하는 식의 정렬 코드 :.. 2021. 2. 19.

이전 1 다음

티스토리툴바