1. 강한 결합 요소(SCC, Stongly Connected Component) 강한 결합 요소란 유향 그래프 안에서 강하게 결합된 정점 집합을 의미한다. 서로 긴밀하게 연결되어있기 때문에 강한 결합 요소라고 하며, SCC 알고리즘이라고 불린다. 좀 더 쉽게 설명하자면, 싸이클(원형 그래프)를 생각하면 되는데, 두 가지 조건을 만족해야 한다. 1. 임의의 유향 그래프 내 정점 A, B 사이에 경로가 항상 존재해야한다. 2. A에서 B로 가는 경로, B에서 A로 가는 경로가 동시에 존재할 수 없다. [그림 1]을 보면 충분히 SCC인지 아닌지 판별할 수 있다. 왼쪽 섹션에 있는 그림은 조건 1, 2를 둘 다 만족하고 있으므로 강한 결합 요소다. 하지만 오른쪽 두 그림은 두 점을 지나는 경로가 존재하기 때..

1. 위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. [그림 1]을 보자. [그림 1]은 임의로 만든 마법사로 전직을 한후 배워야하는 스킬의 관계도다. 각 스킬에 대한 관계도를 정리하면 다음과 같다. 에너지 볼트는 맨 처음에 배우는 기본 마법이다. 매직클로를 배우려면 에너지볼트를 먼저 배워야한다. 메테오를 배우려면 먼저 매직클로, 텔레포트를 배워야한다. 마력 흡수를 배우려면 먼저 에너지 볼트를 배워야한다. 텔레포트를 배우려면 먼저 마력흡수, 매직클로를 배워야한다. 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 먼저 마법사로 전직하면 에너지 볼트를 찍고, 그 다음엔 마력 흡수 또는 매직클로를 찍는다. 그리고 텔레포트를 찍고 최종적으..

1. 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘이다. 최단거리 알고리즘의 사용 예시로 도시의 지도에서 출발지에서 목적지 사이의 거리 중 가장 짧은 거리를 찾는 네비게이션이나, 인공위성 GPS 소프트웨어 등이 있다. 다익스트라 알고리즘은 음의 간선을 포함할 수 없기 때문에 모든 가중치가 양수여야만 한다 다익스트라 알고리즘의 실행 순서는 다음과 같이 동작한다. 모든 꼭지점을 미방문 상태로 만든다. 시작 정점을 정한다(정점 A에서 탐색을 시작할 건지, 정점 B에서 시작할 건지 결정). 시작정점 A를 방문상태로 처리한다(시작 정점을 A라고 가정). 정점 A에 인접한 정점으로 가는 모든 거리 값을 기록한다. 정점 A에 각각의 인접 정점과 연결된 거리 중에서, ..

1. 다이나믹 프로그래밍 다이나믹 프로그래밍이란, 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 이전에 나는 퀵 정렬, 병합 정렬, 이진검색과 같은 자료구조를 포스팅한 적이 있다. 이 셋을 언급한 이유는 분할 기법을 이용하기 때문이다. 퀵 정렬, 병합 정렬, 이진검색은 분할 기법을 이용해서 평균 시간복잡도 O(Nlog₂N)이라는 굉장히 빠른 속도를 장점으로 가질 수 있었다. 하지만 되게 빨라보이는 분할기법도 어떤 상황에서는 단점이 존재하는데, 그것은 바로 동일한 문제를 반복해서 푼다는 것이다. 그 대표적인 예시가 피보나치 수열이다. 피보나치 수열은 제 0항, 제 1항을 1로 제쳐두고 두 번째 항부터는 앞에 두 수를 더한 값을 결과로 두는 수열을 말한다. 피보나치 수열은 보통 프로그래밍 언어에서 재귀..

1. 이진 검색 이진 검색(Binary Search)은 자료 가운데 있는 항목을 키 값과 비교하여 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법이다. 이진 검색(Binary Search)은 퀵 정렬과 마찬가지로 분할과 정복 기법을 사용하기 때문에 시간 복잡도가 O(log₂N)으로 엄청나게 빠른 속도를 자랑한다. 하지만 이진 검색은 삽입, 삭제를 수행한 후에 항상 배열의 상태를 정렬된 상태로 유지해야 하는 작업이 따로 필요하다. 그 이유는 이진 검색(Binary Search)이 정렬된 순차 자료구조에서만 사용할 수 있기 때문이다. 2. 동작 순서 퀵 정렬의 동작을 제대로 알고 있다면, 이진 검색(Binary Search)의 동작도 쉽게 이해할 수 있을 것이다. 이진 검색의..

1. 순차 검색 순차 검색은 가장 쉽고 단순한 검색 방법으로써, 순서대로 항목을 비교하면서 검색하는 순차 검색과 인덱스 테이블을 사용하여 검색의 효율성을 높인 색인 순차검색이 있다. 정렬되지 않은 순차 자료구조에서의 순차검색 첫 번째 원소부터 시작해서 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다. 키 값이 일치하는 원소를 찾 으면 그 원소가 몇 번째 원소인지를 반화한다. 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 검색이 실패된다. 순차 검색에서 비교횟수는 원소의 위치에 따라 다르다. 찾고자 하는 원소가 첫 번째 원소면 비교횟수는 1이고, 마지막 원소라면 비교횟 수가 n이다. 따라서 순차 검색의 평균 시간 복잡도는 O(n)이다. 정렬되어 있는 순차 자료구조에서의..