언제나 휴일

3. 2 list 만들기 – 더미 노드없는 이중 연결 리스트 이번에는 더미노드가 없는 이중 연결 리스트를 만들어 봅시다. 더미노드가 없는 이중 연결 리스트에도 node의 정의나 iterator의 정의는 차이가 없습니다. 여기에서는 차이가 있는 부분만 언급하겠습니다. 먼저, list를 생성했을 때의 초기 모습이 다를 것입니다. [그림 12] 더미노드 없는 이중 연결 리스트 초기화 모습 list(){ head = tail = 0; bsize = 0;} 생성자 메서드 외에 차이가 있는 부분은 노드를 매다는 hang_node와 노드의 연결을 끊는 dehang_hode와 시작 iterator를 반환하는 begin, 마지막 iterator를 반환하는 end가 있습니다. hang_node 메서드에서는 보관된 자료가 ..

10.3.2 깊이 우선 탐색(인접 행렬) 구현 이번에는 인접행렬로 구현한 그래프를 이용하여 깊이 우선 탐색 알고리즘을 구현해 봅시다. 깊이 우선 탐색은 한 정점에서 갈 수 있는 이웃 정점으로 이동한 후에 다시 이웃 정점으로 이동하는 것을 반복합니다. 단 이미 방문한 정점은 방문하지 않으면서 목적지까지 경로를 찾는 알고리즘입니다. 그런데 깊이 우선 탐색에서 이동하다가 더 이상 갈 곳이 없으면 이전 갈림길에서 다른 길을 선택할 수 있어야 합니다. 이를 위해 현재까지 이동한 경로를 경험 정보로 관리하고 한 정점에서 갈 수 있는 이웃 정점을 추가한 다음 경험 정보를 스택에 보관해 두었다가 더 이상 갈 곳이 없으면 스택에서 꺼내와서 다른 경로를 찾게 구현할 거예요. 다음은 스택을 이용한 깊이 우선 탐색 알고리즘의..

10.3.1 그래프 구현 그래프는 방향성 없는 그래프와 방향성 있는 그래프가 있습니다. 먼저 방향성 없는 그래프를 살펴보아요. 방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요. 방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠. 먼저 그래프 형식을 정의하기로 해요. 인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠. 이제 방향성 없는 그래프를 구현해 봅시다. 정점을 보관하는 벡터를 이웃이라고 정합시다.typedef vector Neighbors;class Graph..

10.2.2 순열 문제 소스 코드 다음은 앞에서 작성한 순열 문제의 소스 코드입니다. //Heuristic.h#pragma once#include #include using namespace std;typedef vector Bucket;typedef Bucket::iterator BIter;typedef Bucket::const_iterator CBIter; class Heuristic;typedef vector Heues;typedef Heues::iterator HIter;typedef Heues::const_iterator CHIter; class Heuristic{ Bucket original; Bucket out;public: Heuristic(Bucket bucket); Heues EnumN..

10.2.1 순열 문제 구현 순열 문제를 구현합시다. 0~9까지 공을 보관한 초기 경험 정보를 생성스택에 보관반복(스택이 비어 있지 않다면) 스택에서 경험 정보 꺼내옮 스택에서 꺼내온 경험 정보에서 다음 경험(공을 하나 더 꺼내는) 목록 조사 반복(다음 경험 목록을 순차적으로 반복) 바구니에 공이 비면 결과 출력 그렇지 않다면 스택에 보관 먼저 공을 보관한 바구니를 공의 번호를 보관하는 벡터로 표현할게요.typedef vector Bucket;typedef Bucket::iterator BIter;typedef Bucket::const_iterator CBIter;그리고 경험 정보를 벡터에 보관한 형식을 Heues로 정의할게요.class Heuristic;typedef vector Heues;typede..

6.3 이진 탐색(Binary Search)이진 탐색(Binary Search) 알고리즘은 정렬 상태의 배열에서 원하는 자료를 탐색하는 알고리즘으로 재귀적인 방법으로 구현할 수 있는 대표적인 알고리즘입니다. 배열의 중간에 있는 요소와 검색 자료를 비교하여 크면 뒤쪽 배열에서 재귀적으로 탐색하고 작으면 앞쪽 배열에서 재귀적으로 탐색합니다. 만약 같은 자료를 찾거나 배열의 원소 개수가 0이면 탐색을 끝냅니다. 위치 BinarySearch(base: 배열, n: 원소 개수, value: 검색할 값) 조건 n0) 반환 BinarySearch(base,n/2, fun) 반환 BinarySearch(base+n/2+1,n - n/2, fun) 순차 탐색한다면 최악의 경우 모든 요소와 비교해야 하므로 O(n) 성능을..

6.2 퀵 정렬(Quick Sort)퀵 정렬(Quick Sort) 알고리즘은 재귀적인 방법으로 문제를 해결하는 정렬 알고리즘입니다. 퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다. 그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬하여 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다. 여기에서는 맨 앞과 맨 뒤, 그리고 중간 위..

6. 재귀 알고리즘 이번에는 재귀 알고리즘을 살펴봅시다. 재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용해서 해결하는 알고리즘입니다. 수학에서 명제가 참인지 거짓인지 증명하기 위해 명제를 이용해서 증명하는 방법과 같은 방식입니다. 예를 들어 "n! 을 f(n)이라고 할 때 f(1)=1이고 n>1인 정수이면 f(n)=n*f(n-1)이다."라는 명제를 증명하면 다음처럼 증명할 수 있습니다. n-1일 때 위 명제가 참이라고 가정합시다. 가정에 의해 f(n-1) = (n-1)*(n-2)*(n-3)*...*3*2*1입니다. f(n) = n*(n-1)*(n-2)*(n-3)*...*3*2*1 = n*f(n-1) 이므로 위 명제는 참인 명제입니다. 이처럼 명제 자신을 이용하여 명제를 증명하는 것을 재귀적 ..

C언어에서 배열을 선언할 때 컴파일러에게 선언하는 것이 배열임을 알려주는 [ ]지시 연산자를 사용해요. 포인터를 선언할 때는 포인터임을 알려주는 * 지시 연산자를 사용해요. 배열을 선언하려면 컴파일러에게 선언하는 것이 배열임을 알려주는 [ ]지시 연산자 내부에 원소 개수를 지정하세요. 그리고 배열 이름과 지시 연산자, 원소 개수를 제외한 나머지 부분이 원소 형식이예요. 포인터도 변수 이름과 지시 연산자를 제외한 나머지 부분이 원소 형식이죠. int arr[10]; //배열 선언문, 원소 개수:10, 원소 형식: int int *p = arr; //포인터 선언문, 원소 형식: int int arr[10]; 구문은 원소 형식이 int 이고 원소 개수가 10인 배열 arr을 나타내는 선언문이예요. 컴파일러는 ..

C언어에서 선택문은 표현식의 값에 따라 수행할 코드의 위치를 선택하는 구문이예요. switch (선택 표현식) { case 상수: 수행 구문; break; ... default: 수행 구문; breadk; } 선택 표현식의 값에 일치하는 case 위치의 구문을 수행하며 선택 표현식의 결과는 정수여야 하죠. 그리고 일치하는 case가 없을 때는 default 위치의 구문을 수행애요. 그리고 break 문을 만나면 switch 블록을 빠져 나가죠. 조건이 여러 개일 때 조건문을 사용하는 것은 복잡하며 switch 문을 사용하여 단순하게 프로그램을 작성할 수 있어요. ◈ 성적을 입력받아 학점을 출력하는 예 (if문 사용) #include int main() { int score=-1; int level = 0..