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

1. 그래프 그래프란 연결되어있는 원소 간의 관계를 표현하는 자료구조를 말한다. 버스 노선도, 전철 노선도, 인간관계를 나타내는 연결구조는 구조가 너무나도 다양하고 복잡하기 때문에 선형 자료구조나 트리로 표현할 수 없다. 그래프는 연결할 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)로 구성된다. 그래프 G를 G = (V, E)로 정의하는데, V는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선의 집합을 의미한다. 2. 그래프의 종류 (1) 무방향 그래프 무방향 그래프는 간선에 방향이 없는 그래프를 말한다. 무방향 그래프는 정점 V₁과 정점 V₂를 연결하는 간선을 (V₁, V₂) 로 표현한다. 아래 [그림 1]은 무방향 그래프를 나타낸 그림이다. 위 무방향 그래프 G를 정점의 ..

1. 버블 정렬 버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다. 첫 번째 원소부터 마지막 원소까지 반복하여 가장 큰 원소가 마지막 자리로 오게 정렬 방식이다. 버블 정렬은 탐색 방법이 선택정렬(이전 포스트 글)과 반대라고 생각하면 된다. 선택 정렬은 처음 요소를 1씩 늘려 탐색하는 방법이라고 한다면, 버블 정렬은 마지막 요소를 1씩 빼서 탐색하는 방법이라고 생각하면 된다. 2. 동작 순서 동작 순서도 크게 어려울 건 없다. 선택정렬(이전 포스트 글)에서 썼던 예시 입력 값을 그대로 써서 설명하도록 하겠다. 우리는 이제 위의 입력값 [5, 10, 1, 2, 6]을 버블 정렬을 이용하여 오름차순으로 정렬하려고 한다. 먼저 첫 요소인 5부터 끝 요소인 6까지 탐색을 실시하여 현재 요소 ..

1. 선택 정렬 선택정렬은 정렬 알고리즘의 하나이다. 동작 순서는 별거 없다. 이 한마디만 기억하면 된다. 최소 값을 맨 앞으로 보내라 2. 동작 순서 이것이 무슨 말입니까...? 생각이 든다면, 간단한 예를 들어보도록 하겠다. 선택 정렬의 동작순서를 설명을 하기 위해 다음의 리스트 값으로 예를 들어보도록 하겠다. 우리는 선택정렬을 이용해서 이 리스트 값을 오름차순으로 정렬하려고 한다. 먼저, 첫 번째 요소 5에서부터 리스트 끝인 6까지 탐색해서 최솟값을 찾도록 한다. 최솟 값은 1이 나온다. 찾은 최솟 값 1을 맨 앞 요소와 스와핑한다. 그리고 두 번째 요소 10에서부터 리스트 끝인 6까지 탐색해서 최솟 값을 찾도록 한다. 최솟 값은 2가 나온다. 그 후 찾은 최솟 값을 10과 스와핑하여 맨 앞으로 보..