탐색이란?

컴퓨터 프로그램에서 탐색은 하나 이상의 필드(field)로 구성되는 레코드(record)의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이러한 레코드들의 집합을 테이블(table)이라 부른다. 레코드들은 서로 중복되지 않고 고유한 값을 가지는 키를 가지는데, 이것을 탐색키(search key)라 부른다.

맵이란?

맵은 탐색을 위한 자료구조이다. 맵(map) 또는 사전(dictionary)은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조를 말한다. 맵은 키를 가진 레코드(keyed record) 또는 엔트리(entry)라 불리는 키-값 쌍(key, value)을 테이블에 저장한다. 이때 각 키는 유일하고 맵에 저장되는 키와 값은 어떠한 자료형도 가능하다.

키를 가진 레코드의 추상 자료형은 다음과 같다.

• 객체
  • 키(key)와 값(value)을 가진 요소 (key, value)의 집합
• 연산
  • create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성한다.
  • getKey(): 레코드의 키를 반환한다.
  • getValue(): 레코드의 값을 반환한다.
  • update(value): 레코드의 값을 value로 변경한다.

맵의 추상 자료형은 다음과 같다.

• 객체
  • 유일한 키를 가진 엔트리(키를 가진 레코드)의 집합
• 연산
  • create(): 공백 상태의 맵을 생성한다.
  • search(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 반환한다.
  • insert(entry): 테이블에서 주어진 entry를 삽입한다.
  • delete(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 삭제한다.
  • count(): 테이블의 모든 레코드 수를 반환한다.

맵을 구현하는 가장 간단한 방법은 배열일 것이다. 그러나 맵의 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 보다 효율적인 자료구조를 사용해야 한다.

Continue reading →

정렬이란?

정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 말한다.

일반적으로 정렬시켜야 될 대상은 레코드(record)라고 불린다. 레코드는 다시 필드(field)라고 하는 보다 작은 단위로 나누어진다. 예컨대 학생들의 레코드에는 이름, 학번, 주소, 전화번호 등이 필드가 될 것이다. 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 한다. 학생들의 레코드의 경우에는 학번이 키가 될 수 있다.

정렬 알고리즘의 분류

정렬 알고리즘은 다음의 2가지 그룹으로 나눌 수 있다.

• 단순하지만 비효율적인 방법 – 삽입 정렬, 선택 정렬, 버블 정렬 등
• 복잡하지만 효율적인 방법 – 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 등

정렬 알고리즘을 내부 정렬(internal sorting)과 외부 정렬(external sorting)으로 구분할 수도 있다. 내부 정렬은 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬을 의미한다. 반면 외부 정렬은 외부 기억장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬하는 방법이다. 여기서는 내부 정렬만을 다루기로 한다.

Continue reading →

가중치 그래프란?

간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph)라고 한다.

가중치 그래프는 수학적으로는 G = (V, E, w)와 같이 표현된다. V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미하고, w(e)는 간선 e의 강도(weight), 비용(cost), 또는 길이(length)라고 부른다. 어떤 가중치 그래프의 경로를 p = (v₀, v₁, v₂, … v_k)라고 한다면 경로의 강도 w(p)는 다음과 같이 경로 상의 모든 간선의 강도 합으로 표현된다.

가중치 그래프의 표현

가중치의 표현

가중치 그래프의 클래스에서는 인접 행렬을 약간 다른 용도로 사용해야 한다. 인접 행렬의 값을 간선의 유무가 아니라 간선의 가중치를 직접 나타내게 하면 가중치 그래프를 나타낼 수 있다.

그러나 이 경우 간선의 유무를 판단하기 어려워지는데, 이런 경우에는 간선의 유효 범위를 넘어서는 값을 지정하여 –예컨대 999999– 그 값 이상이 되면 간선이 없는 경우로 판단하여 처리하는 방법이 있다.

Continue reading →

그래프란?

그래프는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

그래프의 역사

그래프는 오일러에 의해 처음 창안되었다. 오일러는 ‘모든 다리를 한번만 건너서 출발했던 장소로 돌아올 수 있는가’라는 문제가 답이 없다는 것을 그래프 이론을 이용하여 증명하였다. 오일러는 이 문제의 핵심은 ‘A, B, C, D의 위치가 어떠한 관계로 연결되었는가?’라고 생각하고 ‘위치’라는 객체는 정점(vertex)로, 위치간의 관계인 ‘다리’는 간선(edge)로 표현하여 그래프 문제로 변환하였다. 오일러는 그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명하였다.

그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. 수학적으로는 G = (V, E)와 같이 표시한다. 여기서 V(G)는 그래프의 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 여러 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 객체 정점들 간의 관계를 의미하는데, 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. 정점은 노드(node)라고 불리며, 간선은 링크(link)라고도 불린다.

Continue reading →

우선순위 큐

우선순위 큐란?

도로에서 먼저 진입하는 차가 먼저 가게 되지만, 만일 구급차나 소방차가 나타나면 모든 자동차들은 이러한 긴급 차량을 위하여 도로를 양보해야 한다. 이러한 긴급 차량들은 도로 교통법에 의하여 높은 우선순위(priority)를 갖고 있기 때문이다. 컴퓨터에서도 우선순위 개념이 필요할 때가 있는데, 네트워크 패킷 중에서 네트워크 관리와 관련된 것들은 다른 일반 패킷보다 우선순위를 가진다.

우선순위 큐는 바로 이러한 우선순위의 개념을 큐에 도입한 자료구조이다.보통의 큐는 선입선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되는데 우선순위 큐(priority queue)는 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 출력된다.

우선순위 큐는 사실 가장 일반적인 큐로 볼 수 있는데, 우선순위 큐를 이용하여 스택이나 큐도 얼마든지 구현할 수 있기 때문이다. 예컨대 데이터가 들어온 시각이 빠른 것을 높은 우선순위로 처리하면 큐처럼 동작하고, 늦게 들어온 것을 높은 우선순위로 처리하면 스택으로 사용할 수 있다.

우선순위 큐는 배열, 연결 리스트 등 여러 방법으로 구현이 가능하지만 가장 효율적인 구조는 힙(heap)이다.

Continue reading →

이진 탐색 트리

탐색이란?

컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다.

레코드는 하나 이상의 필드(field)로 구성된다. 예컨대 학생의 레코드는 이름, 주소, 주민등록번호 등의 필드들로 이루어진다. 일반적으로 레코드들의 집합을 테이블(table)이라고 한다.

레코드들은 보통 키(key)라고 불리는 하나의 필드에 의해 식별할 수 있다. 키는 서로 중복되지 않는 고유한 값을 가지는데, 키를 사용하면 각각의 레코드들을 구별할 수 있다. 이러한 키를 주요키(primary key)라고 한다.

Continue reading →

트리(Tree)의 개념

트리는 계층적인 자료를 표현하는데 이용되는 자료구조이다.

인공지능 문제에서도 트리가 사용되는데, 대표적인 것이 결정 트리(decision tree)이다. 결정 트리는 인간이나 컴퓨터의 의사결정 구조를 표현하는 한 가지 방법이다.

트리의 용어들

트리의 구성 요소를 노드(node)라고 한다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나의 노드는 루트(root) 노드라 불리고 나머지 노드들은 서브트리(subtree)라고 불린다. 아래 그림에서 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.

트리에서 루트와 서브트리는 선으로 연결된다. 이 연결선을 간선 또는 엣지(edge)라고 한다.

Continue reading →

순환(Recursion)의 소개

순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. (재귀는 초기항과 수열을 이루는 규칙을 통해 수열을 간결하게 표현할 수 있는 점화식의 개념을 컴퓨터에서 구현한 것과 같다.)

순환 호출의 내부적인 구현

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 즉, 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 파라미터와 지역 변수를 스택으로부터 할당 받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(Activation Record)라고 한다.

이러한 준비가 끝나면 호출된 함수의 코드 시작 위치로 이동하여 수행을 시작한다. 만약 호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다. 혼출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 꺼내 자신을 호출한 함수로 되돌아간다. 순환 호출이 계속 중첩될 수록 시스템 스택에는 활성 레코드들이 쌓이게 된다.

Continue reading →

리스트(List)의 추상 자료형

리스트란

리스트 (또는 선형 리스트)는 항목들이 차례로 정리된 선형 자료구조를 의미한다. 순서가 있기 때문에 리스트는 집합과 다르다.

리스트는 스택이나 큐와 달리 중간에 데이터를 삽입하거나 삭제할 수 있다. 대신 그만큼 구현시에 고려해야 할 점들도 많다.

Continue reading →

포인터(Pointer)

포인터의 개념

컴퓨터에게 CPU와 Memory는 핵심 요소이고, 모든 메모리는 주소를 갖는다. 포인터는 그 메모리의 주소를 가리키는 변수를 의미한다. 보통 그 주소에는 다른 변수가 저장되어 있는데, 포인터를 이용하면 해당 데이터에 접근할 수 있다.

보통 컴퓨터의 메모리는 바이트 단위로 구성되어 있고 각 바이트마다 순차적으로 주소가 매겨져 있다.

char ch = 'a'; // 1. 문자형 변수 ch 선언 및 초기화
char* p; // 2. 포인터 변수 p 선언
p = &ch; // 3. 포인터 변수 값 저장
*p = 'b'; // 4. ch = 'b'; 와 동일. p가 가리키는 곳의 내용을 'b'로 교체
char** pp; // 5. 이중 포인터 변수 pp를 선언
pp = &p; // 6. p의 주소를 pp에 복사

Continue reading →