본문내용
1. 알고리즘 학습
1.1. 배열
배열은 같은 자료형을 갖는 여러 데이터를 하나의 변수명으로 모아놓은 데이터의 집합체이다. 배열에는 논리적 순서와 저장된 물리적인 순서가 동일하기 때문에 삽입과 삭제가 발생할 때 순서 유지를 위해 부가적인 자료의 이동이 필요하다. 또한 배열은 인덱스를 통한 빠른 임의 접근이 가능한 자료구조이다.
배열에서 각 데이터에 대한 접근 시간은 원칙적으로 동일하다. 하지만 데이터의 삽입과 삭제 시 추가적인 자료의 이동이 발생한다. 이는 배열의 논리적 순서와 물리적 순서가 동일하기 때문이다.
스택에서 데이터를 push하기 전에는 top을 하나 올려준 뒤 값을 하나 넣으며, pop할 때는 값을 하나 뺀 뒤 top을 하나 내려준다. 큐에서 삽입되는 부분은 Rear/Tail이고 삭제되는 부분은 Front/Head이다. 큐에서 맨 처음에 삽입되는 입구에 front, rear가 같이 위치해 있으며, 삽입 시 rear를 하나 앞으로 보낸 뒤 값을 넣고, 삭제 시에는 front를 앞으로 하나 보낸 뒤 그 값을 뺀다.
배열은 논리적 순서와 물리적 순서가 동일하며, 데이터의 삽입과 삭제 시 추가적인 자료의 이동이 발생한다는 특징을 가지고 있다. 또한 인덱스를 통한 빠른 임의 접근이 가능하다는 장점도 있다."
1.2. 스택과 큐
스택은 데이터를 순서대로 저장하고 꺼내는 자료구조이다. 스택에서는 가장 최근에 저장된 데이터를 가장 먼저 꺼내는 "후입선출(LIFO, Last-In-First-Out)" 방식을 따른다. 스택에서 데이터를 추가하는 것을 "push", 데이터를 꺼내는 것을 "pop"이라고 한다. 스택은 함수 호출, 수식 계산, 브라우저의 뒤로가기 기능 등 다양한 분야에서 활용된다. 예를 들어 함수 호출 시 함수의 매개변수, 지역변수, 복귀주소 등이 스택에 저장되고 함수가 종료되면 스택에서 해당 정보가 pop된다.
큐는 데이터를 순서대로 저장하고 꺼내는 자료구조이다. 큐에서는 가장 먼저 저장된 데이터를 가장 먼저 꺼내는 "선입선출(FIFO, First-In-First-Out)" 방식을 따른다. 큐에서 데이터를 추가하는 것을 "enqueue", 데이터를 꺼내는 것을 "dequeue"라고 한다. 큐는 프로세스 스케줄링, 네트워크 패킷 전송, 프린터 출력 대기열 등 다양한 분야에서 활용된다. 예를 들어 프로세스 스케줄링에서 ready 상태의 프로세스들이 큐에 저장되고 CPU가 사용 가능해지면 먼저 큐에 들어온 프로세스부터 실행된다.
스택과 큐는 순서를 유지하며 데이터를 관리한다는 공통점이 있지만, 데이터 추출 순서가 다르다는 점에서 구분된다. 스택은 후입선출, 큐는 선입선출 방식을 따른다. 이러한 차이로 인해 스택은 함수 호출, 수식 계산 등 후입선출 방식이 필요한 분야에, 큐는 프로세스 스케줄링, 네트워크 패킷 전송 등 선입선출 방식이 필요한 분야에 효과적으로 활용될 수 있다.
1.3. 트리 및 이진 트리
트리는 노드와 간선으로 구성된 비선형 자료구조로, 데이터 간의 계층적 관계를 효과적으로 표현할 수 있다"" 트리는 하나의 루트 노드를 중심으로 계층적으로 구성되며, 각 노드는 임의의 개수의 자식 노드를 가질 수 있다"" 트리에서 노드의 차수(degree)는 해당 노드의 자식 노드 수를 의미하며, 트리의 차수는 트리에 포함된 노드의 차수 중 가장 큰 값을 의미한다"" 리프(leaf) 노드는 자식 노드가 없는 노드이며, 비단말(nonterminal) 노드는 자식 노드가 있는 노드를 의미한다"" 레벨은 루트 노드로부터의 거리를 나타내며, 트리의 높이(depth)는 가장 깊은 레벨의 번호에 1을 더한 값이다""
이진 트리는 각 노드의 차수가 2 이하인 트리로, 노드에 저장된 값이 왼쪽 서브트리의 값보다 작고 오른쪽 서브트리의 값보다 크도록 구성된다"" 이진 트리는 높이 h인 경우 최대 2^h-1개의 노드를 가질 수 있으며, 단말 노드의 개수는 2^(h-1)개, 비단말 노드의 개수는 2^(h-1)-1개이다"" 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있는 이진 트리이며, n개의 노드를 가지는 완전 이진 트리의 높이는 log2n이다"" 전(full) 이진 트리는 노드의 차수가 0 또는 2인 이진 트리이며, 균형(balanced) 이진 트리는 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이내인 이진 트리이다""
이진 탐색 트리(Binary Search Tree)는 이진 트리의 한 종류로, 각 노드의 왼쪽 서브트리에 있는 모든 키값은 해당 노드의 키값보다 작고 오른쪽 서브트리에 있는 모든 키값은 해당 노드의 키값보다 크도록 구성된다"" 이진 탐색 트리에서 키값 검색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이에 비례하며, 최악의 경우 O(n)이 될 수 있다"" 이를 방지하기 위해 균형 탐색 트리(Balanced Search Tree)가 고안되었는데, 대표적인 예로는 레드-블랙 트리(Red-Black Tree)와 B-트리(B-Tree)가 있다"" 이러한 균형 탐색 트리는 삽입, 삭제, 검색 연산의 시간 복잡도를 O(logn)으로 보장할 수 있다""
1.4. 그래프
그래프는 정점(vertex)의 집합 V와 정점들을 연결하는 간선(edge)의 집합 E로 구성된다. 그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다. 무방향 그래프에서는 간선이 양방향으로 연결되어 있지만, 방향 그래프에서는 간선이 한 방향으로만 연결되어 있다.
그래프에서 정점 v1에서 vn까지의 경로란 간선 (v1, v2), (v2, v3), ..., (vn-1, vn)으로 연결된 정점의 순서 리스트 v1, v2, ..., vn을 의미한다. 그래프에서 정점의 차수는 해당 정점에 부수된 간선의 개수를 의미하며, 방향 그래프에서는 진입 차수와 진출 차수로 구분된다.
그래프는 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)로 표현할 수 있다. 인접 행렬은 그래프의 정점들을 2차원 배열로 나타내며, 간선이 있으면 1, 없으면 0으로 표시한다. 인접 리스트는 각 정점의 인접 정점들을 연결 리스트로 나타낸다. 인접 행렬은 정점 간 연결 관계를 빠르게 확인할 수 있지만, 메모리 공간이 많이 필요하고 간선의 추가/삭제가 어려운 반면, 인접 리스트는 메모리 효율적이며 간선의 추가/삭제가 용이하다.
그래프는 네트워크, 지도, 소셜 관계 등 다양한 영역에서 활용된다. 특히 최단 경로 문제, 최소 신장 트리 문제, 그래프 탐색 등의 알고리즘이 그래프 이론에 기반하고 있다. 따라서 그래프 이론은 컴퓨터 과학, 운영 연구, 사회 네트워크 분석 등 다양한 분야에서 중요한 역할을 한다고 볼 수 있다.
2. 알고리즘 기초
2.1. 알고리즘의 조건
알고리즘은 효과적으로 문제를 해결하기 위해 고안된 단계적인 절차 또는 방법이다. 알고리즘이 적절하게 작동하기 위해서는 반드시 갖추어야 할 조건이 있다. 첫째, 알고리즘은 입력값을 받아 출력값을 내놓는 과정을 명확하게 정의해야 한다. 둘째, 알고리즘은 각 단계가 명확하고 구체적이어야 하며 모호함이 없어야 한다. 셋째, 알고리즘은 유한한 단계 내에 종료되어야 한다. 넷째, 알고리즘은 올바른 결과를 도출해내야 한다. 이렇듯 입출력, 명확성, 유한성, 유효성이 알고리즘의 기본 조건이다. 이와 더불어 실용적인 관점에서 효율성 또한 중요한 조건으로 간주된다.
2.2. 알고리즘의 시간 복잡도
알고리즘의 시간 복잡도는 입력 데이터의 크기에 따른 알고리즘의 수행 시간을 나타내는 지표이다. 알고리즘의 효율성을 평가하는 주요 기준으로 사용되며, 이를 통해 알고리즘의 실행 속도를 예측할 수 있다.
알고리즘의 시간 복잡도는 입력 데이터의 크기 함수로 표현된다. 예를 들어, 순차 탐색의 경우 최악의 경우 n번 비교를 해야 하므로 시간 복잡도는 O(n)이 된다. 이진 탐색의 경우 입력 크기가 증가할수록 비교 횟수가 절반씩 줄어들어 시간 복잡도가 O(logn)이 된다.
알고리즘의 시간 복잡도에 영향을 미치는 주요 요인은 다음과 같다.
첫째, 입력 크기이다. 일반적으로 입력 데이터의 크기가 증가할수록 알고리즘의 수행 시간이 증가한다.
둘째, 입력 데이터의 상태이다. 최악의 경우와 평균적인 경우의 시간 복잡도는 다를 수 있다. 예를 들어, 역순으로 정렬된 배열에 대한 삽입 정렬의 시간 복잡도는 O(n^2)이지만, 이미 정렬된 배열에 대한 삽입 정렬의 시간 복잡도는 O(n)이 된다.
셋째, 알고리즘의 구조와 설계이다. 동일한 문제를 해결하는 경우에도 알고리즘의 설계에 따라 시간 복잡도가 크게 달라질 수 있다. 예를 들어, 이진 탐색과 순차 탐색은 모두 데이터 탐색 문제를 해결하지만, 시간 복잡도는 각각 O(logn)과 O(n)으로 크게 다르다.
알고리즘의 시간 복잡도는 점근 표기법으로 나타낸다. 대표적인 점근 표기법은 다음과 같다:
- O(1): 상수 시간 복잡도로, 입력 크기에 관계없이 일정한 시간이 소요된다.
- O(logn): 로그 시간 복잡도로, 입력 크기가 증가할수록 수행 시간이 천천히 증가한다.
- O(n): 선형 시간 복잡도로, 입력 크기에 비례하여 수행 시간이 증가한다.
- O(nlogn): 선형 로그 시간 복잡도로, 입력 크기에 비례하면서도 로그 시간이 소요된다.
- O(n^2): quadratic 시간 복잡도로, 입력 크기의 제곱에 비례하여 수행 시간이 증가한다.
이와 같은 점근 표기법을 활용하여 알고리즘의 효율성을 비교하고 분석할 수 있다. 일반적으로 O(1), O(logn), O(n), O(nlogn)의 시간 복잡도를 가진 알고리즘이 효율적이라고 볼 수 있다.
2.3. 알고리즘 설계 기법
알고리즘 설계 기법에는 분할정복(divide-and-conquer) 방법, 동적 프로그래밍(dynamic programming) 방법, 욕심쟁이(greedy) 방법 등이 있다"
분할정복 방법은 주어진 문제를 순환적으로 더 작은 문제들로 나누어 해결하고, 이렇게 해결된 작은 문제들의 해를 결합하여 원래 문제의 해를 구하는 기법이다. 순환 알고리즘으로 표현되며 점화식으로 시간 복잡도를 도출할 수 있다. 대표적인 알고리즘으로는 이진 탐색, 퀵 정렬, 합병 정렬 등이 있다"
동적 프로그래밍 방법은 상향식 접근 방법으로, 작은 문제들의 최적해를 구하고 이를 조합하여 더 큰 문제의 최적해를 구하는 기법이다. 최적화 문제에 효과적으로 적용되며 최적성의 원리가 만족되어야 한다. 피보나치 수열, 연쇄 행렬 곱셈, 편집 거리 문제 등이 대표적이다"
욕심쟁이 방법은 현재 선택이 최선이라고 판단되는 방향으로 문제를 해결해 나가는 기법이다. 최적화 문제에 효과적이며 역시 최적성의 원리가 만족되어야 한다. 최소 신장 트리, 단일 출발점 최단 경로 문제 등에 적용된다"...
