기록하는삶

위상 정렬은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미하는데, 대학의 선수과목 구조가 대표적인 예이다. 정렬의 순서는 여러 가지가 나올 수 있으며, 비순환 그래프일 때만 정렬이 가능하다. 위상 정렬 알고리즘의 동작 원리 및 순서는 아래와 같다. 선행되는 노드가 없는 노드들을 먼저 순서에 삽입하는 것을 기본 원리로 한다. ① 자기 자신을 가리키는 간선의 수를 진입 차수라 할 때, 진입 차수가 0인 모든 노드를 큐에 삽입한다. ② 큐에서 원소 하나를 꺼내어, 순서 배열에 이를 삽입하고 해당 노드가 가진 모든 간선을 삭제한다. 여기서 삭제한다는 것은 해당 간선으로 발생된 진입 차수를 없애는(-1) 것을 말한다. 이때 진입 차수가 줄어드는 노드의 진입 차수가 0이 된..

스패닝 트리(spanning tree)는 신장 부분 그래프(spanning subgraph)의 한 종류이다. 신장 부분 그래프는 원본 그래프의 모든 꼭짓점을 포함하는 부분 그래프로, 생성 부분 그래프라고도 한다. 이때 해당 부분 그래프가 트리라면 스패닝 트리 혹은 최소 신장 트리라고 부르고, 간선의 가중치가 동일하지 않은 경우에 한하여 가장 적은 가중치의 합으로 표현되는 스패닝 트리를 최소 스패닝 트리라 부른다. 즉, 최소 비용으로 모든 노드가 연결될 수 있도록 만드는 트리가 최소 스패닝 트리다. 아래의 사진이 그 예가 되겠다. 최소 스패닝 트리를 구할 수 있는 대표적인 알고리즘이 크루스칼 알고리즘과 프림 알고리즘이다. [크루스칼(Kruskal) 알고리즘의 동작 원리 및 순서] 1. 전체 간선을 가중치 ..

다익스트라, 플로이드-와샬과 함께 노드와 간선, 간선의 비용이 주어진 상황에서 최단 거리를 구할 수 있는 알고리즘 중 하나이다. 다익스트라와 작동 방법이 유사하지만, 존재하는 모든 간선에 대해 최단 거리를 업데이트하는 시행을 (노드의 개수 -1)만큼 진행하는 것이 그 특징이다. 또한 노드의 개수만큼 업데이트한다면 경로 내에 음수 간선의 순환이 있는지 여부도 파악할 수 있다. [동작 과정] ① 출발 노드 설정 및 최단 거리 테이블 초기화(충분히 큰 숫자로, 시작 노드는 0으로 초기화) ② 아래의 과정을 N-1번 반복 ②-1: 전체 간선 E개에 대하여 확인 ②-2: 해당 간선을 이용해 이동하는 것이 더 짧은 경로라면, 이를 이용해 최단 거리 테이블 갱신 ③ ②의 과정을 한 번 더 수행하여, 이때 최단거리 테..

최단 경로 알고리즘은 그래프 탐색 관련 문제로 그래프 상에서 특정 지점으로부터 다른 지점까지 가장 짧은 경로를 찾는 알고리즘이다. 대표적으로 다익스트라와 플로이드-와샬 알고리즘이 있다. 1) 다익스트라(dijkstra) 다익스트라가 제안한 몇 개의 알고리즘 중 가장 잘 알려진 것이 최단 경로 알고리즘이어서 그냥 다익스트라 알고리즘이라 부르기도 한단다. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하며, 음의 간선이 없어야만 정상적으로 동작할 수 있다. 기본적으로 매 상황 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문에, 일종의 그리디 알고리즘이며 계속해서 최단 거리 테이블을 갱신하기에 동적 프로그래밍의 아이디어를 사용하기도 한다. 추가적인 작업을 더해준다면, i에서 j로 이동..

1) 그래프 데이터의 다양한 표현 방법 중 하나로, 꼭짓점(vertex) 혹은 노드(node)와 변(edge)으로 구성된 한정된 자료구조를 말한다. 데이터 간의 연결성을 표현하는 데에 그 장점이 있는 자료구조로, 지도나 도로 등의 경로에서의 최단거리 문제 등에서 활용된다. 코딩 테스트에서 그래프 탐색 문제는 자주 출제되는 유형이기도 하다. 경우에 따라 노드 간의 연결(간선_edge)에 방향성이 있기도, 없기도 하다. 즉 단방향 연결과 양방향 연결이 모두 가능하다. 간선에 가중치가 존재하기도 하며(ex_ 도로의 통행료, 도로 선택시 걸리는 시간 등), 순환이 가능한지 여부나 모든 노드가 연결되어있는지 여부에 따라 그 종류를 구분하기도 한다(사이클 vs 비순환 그래프, 완전 그래프). 구현은 아래의 두 가지..

배열의 정렬 방법에는 여러 가지가 있다. 대부분의 프로그래밍 언어들은 가장 빠른 시간 복잡도인 O(n*logn)을 자랑하는 퀵정렬을 배열의 정렬 알고리즘으로 채택하여 사용하고 있다고 한다. 이 글에서는 보다 느리고 효율은 떨어지지만 기본적이고 쉬운, 버블 정렬과 선택 정렬에 대해 알아보자. 1) 버블 정렬 버블 정렬은 마치 가장 큰 숫자가 버블이 되어 차례로 맨 뒤로 이동하는 정렬 방법이다. 아래의 방법을 따라 정렬이 이루어진다. ① 0번째 원소와 1번째 원소를 비교, 순서대로 정렬한다. 그 다음 1번째 원소와 2번째 원소를 비교, 정렬한다. 이를 n-1번째 원소와 n번째 원소까지 반복하고 나면, 배열에서 가장 큰 원소(버블)가 배열의 맨 뒤로 이동한 상태가 되고 하나의 사이클이 종료된다. ② 다시 ①의..

> 트리(tree) 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합한 자료구조다. 연결 리스트와 같이 메모리 칸을 이용해 정보를 저장하며, 각 메모리 칸은 다른 칸의 위치를 가르키는 포인터를 가진다. 다만 그 모양이 일방향 혹은 양방향의 사슬이 아닌, 하나의 뿌리를 둔 나무의 모양을 띈다는 점에서 다르다. 각 칸을 노드(node), 포인터를 엣지(edge), 그리고 트리의 최상위 정점은 뿌리(root)라 부르며, 노드간 상하관계를 부모자식관계로 표현한다. (학과의 자식 노드는 윤리교육과, 국어교육과, ... 컴퓨터교육과의 부모노드는 학과) 자식 노드를 하나도 갖지 않는 노드들은 잎(leaf)이라 부른다. 한 노드에서 뿌리까지의 경로의 길이를 깊이(level), 트리에서 가장 깊은 노드의 깊이가 트리의..

> 추상 자료형(ADT_Abstract Data Type) 클래스와 유사한 개념으로서 논리적 관계와 구현 시 관계의 연관성을 서로 분리하며, 물리적 요소와 논리적 요소를 서로 구분하는 작업인 절차적 추상화의 결과로 만들어진 것. 특정 데이터 유형에 필요한 연산이 무엇인지 정해 둔 명세로, 데이터 변수를 조작하기 위한 인터페이스와 실제 구현을 분리함으로써 메모리에서 실제 데이터 조작에 필요한 모든 세부사항을 감출 수 있다. 내가 컴퓨터의 내부 작동 원리에 대해 잘 모르지만, 마우스와 키보드로 컴퓨터를 작동할 수 있는 것 역시 '절차적 추상화' 덕분이다. ex) list, dictionary, set, queue, stack 등 > 데이터 구조(자료구조, Data structure) 데이터 값의 모임, 또 ..

> 방법(method) 어떤 목적을 달성하기 위해 해야 할 작업에 대해 명확하게 지시한 것 > 알고리즘(algorithm) 방법 중에서도 작업의 횟수가 유한한 것. 절차, 방법, 명령어들의 집합을 말하기도 하며, 일련의 순서를 포함한다. 주로 컴퓨터가 작업을 처리하는 방법을 말한다. > 시간 복잡도(time complexity) 알고리즘이 문제를 해결하는데 걸리는 시간. 처리해야하는 연산의 수와 연관된다. n개의 데이터가 주어졌을 때, 해당 알고리즘이 수행되는데 필요한 연산의 수를 n에 관한 함수, T(n)으로 표현한다. 이때 연산의 수는 최선의 경우, 평균적인 경우, 최악의 경우로 나누어 생각할 수 있는데 보통은 최악의 경우를 기준으로 생각한다. ex) 선택 정렬 알고리즘 주어진 리스트 중에 최소값을 ..

1. 이진트리 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 이때 전체 자료의 수가 크기, 최상단 노드로부터 최하단 노드로까지의 거리가 높이이다. 노드가 하나 뿐일 때는 높이가 0이다. 2. 포화 이진 트리(Perfect Binary Tree)와 완전 이진 트리(Complete Binary Tree) > 포화 이진 트리(Perfect Binary Tree) 모든 잎의 레벨이 동일하고, 내부 노드들은 모두 2개의 자식을 가지는 트리를 말한다. 즉, 쉽게 말하면 꽉 차 있는 이진 트리이다. > 완전 이진 트리(Complete Binary Tree) 포화 이진 트리의 잎(leaf)들을 오른쪽부터 순서대로 제거하여 얻을 수 있는..