Simple in Complex with Simple

1. 개요

 그래프 문제를 풀기 위해서는 그래프 운행을 위한 메커니즘이 필요하다. (일반 운행법으로는 풀 수 없다. 중요!) 이를 

그래프 탐색 알고리즘이라고 한다. 이에 관한 두 가지 기초이자 가장 중요한 알고리즘이 있다.

● DFS (Depth First Search) 깊이 우선 탐색

● BFS (Breath First Search) 넓이 우선 탐색

이다. 두 기법의 가장 큰 차이는 이렇다.

(1) DFS는 비밀이야기다. 한 번에 한 사람에게만 전해진다. BFS는 소문이다. 자기가 아는 모든 사람에게 전한다.

(2) DFS는 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. BFS는 모든 노드를 탐색 후 끝난다.

(3) 두 기법다 매트릭스 그래프일 경우 시간복잡도는 O(V^2)이고, 인접리스트 기반일 경우 O(V+E)다.

(4) 무엇이 더 좋고 나쁜지는 없다. 찾으려는 데이터가 어디에 위치해있는지에 따라 다르다.

(5) DFS는 역추적 과정이 있어 스택 또는 리커젼을 사용. BFS는 현재 연결된 모든 노드를 차례대로 찾기에 큐를 사용.

2. 문제

 매트릭스 기법으로 최대한 간단하게 BFS 운행법을 코드로 작성하시오. (리커젼 사용)

 그래프의 모양은 다음과 같다.

3. 코드

3-1) 메인

3-2) 그래프 생성

3-3) DFS 알고리즘

3-4) 출력

4. 해설

 딱 2가지만 기억하자.

 (1) 스승님은 위대하다.

 (2) DFS는 시작위치에서 다시 시작위치로 돌아와야 끝나는 알고리즘이다.

1. 개요

 이번 화에서는 그래프 생성의 기본을 작성한다. 그래프는 항상 자료구조의 끝에 등장하기 때문에 익숙하지 않다. 하지만

다른 어떤 자료구조보다 문제의 출현 빈도는 높다. 그러므로 이 기회에 그래프의 가장 기본인 그 생성을 확실히 이해하자.

2. 문제

 매트릭스(2차원 배열)와 리스트(연결리스트)를 사용하여 그래프 생성 함수를 작성하시오.

3. 코드

3-1) 메인

3-2) 매트릭스 방식으로 생성

3-3) 인접리스트 방식으로 생성

3-4) 출력

4. 해설

 반드시 기억해야할 3가지

 (1) 그래프의 매트릭스(2차원 배열)와 인접리스트 형 자료구조.

 (2) 보통 밀집 그래프일 경우 매트릭스가 좋음, 분산 그래프일 경우 인접리스트가 좋음.

 (3) 그래프가 어떻게 메모리가 할당되었는지.

1. 개요

 먼저 동적배열이란 뜻은 프로그래머가 크기를 설정한 배열 또는 프로그램 자체에서 크기를 조절하는 배열등으로 

설명할 수 있다. 예를 들어 만약 프로그램 내부에서 배열을 사용해야 하는데, 이 때 배열이 어느정도의 크기를 가질지

모른다면 우리가 흔히 사용하는 arr[100]과 같은 정적 배열 선언 방식은 사용할 수 없다. 이 때 사용하는 방법이 가변

자료구조인 리스트나 또는 동적배열을 사용한다. 동적배열은 당연히 동적할당을 기반으로 만들어진다. 이게 첫 번째

문제다. 그리고 2번째 문제가 있다. 만약 크기100의 동적배열을 사용하다가 데이터 인풋이 이 배열의 크기를 초과할 때,

현재 데이터를 유지하면서 데이터의 인풋에 맞게 배열의 크기를 더 늘리고 싶다. 이 때, 사용되는 방법 역시 동적배열이다.

2. 문제

 데이터의 수에 따라 크기가 2배로 증가하는 동적배열을 작성하시오. 단, realloc() 함수를 사용하자.

3. 코드

3-1) 메인

3-2) realloc 동적배열 함수

3-3) 출력

4. 해설

 딱 3개만 기억하자.

 (1) realloc() 함수를 사용할 때에는 반드시 메모리 부족으로 실패할 경우를 대비해서 주소를 저장하자! (면접때 물어봄)

 (2) void* 형은 간접 참조와 포인터 연산이 불가능하며, 나중에 반환해야 하는 포인터 주소 저장을 위해서만  사용.

 (3) malloc(), realloc(), memset() 등등 메모리 연산의 크기를 지정할 때에는 항상 sizeof(type)*size가 크기이다.

1. 문제

 링크드 리스트가 회문(palindrome)인지 알아내는 알고리즘을 작성하시오.

 회문(palindrome)은 'abba'나 'madam', 'nurses run' 등등 앞 뒤로 동등한 문장이다.

 '이하이'는 거꾸로 해도 '이하이'와 같은 맥락이다.

 이를 풀어내는 가장 알고리즘은 이렇다.

 1. 리스트의 절반을 탐색한다.

 2. 절반으로 나뉜 리스트의 뒤쪽 리스트를 거꾸로 뒤집는다.

 3. 앞쪽리스트와 뒤쪽리스트와 비교한다.

2. 코드

2-1) 메인

2-2) 알고리즘

2-3) 출력

3. 해설

 이 문제는 간단하다. 먼저 리스트를 절반으로 나눈다. 절반을 찾기 위해서는 전체 길이를 알아야 하기 때문에 O(n)이

걸린다. 다음으로 리스트를 반으로 나눈다. O(n/2)시간이 걸린다. 다음 나눈 리스트 중 하나를 뒤집는다. O(n/2)시간이

걸린다. 마지막으로 앞 뒤의 두 리스트를 비교한다. O(n/2)시간이 걸린다. 

 결론적으로 위의 빅 오 시간을 다 더하면 O(n)+O(n/2)+O(n/2)+O(n/2)이다. 하지만 빅 오 관점에서는 가장 최악의

경우를 고려하므로 결론적으로는 O(n)의 시간이 걸린다. 또한 이 알고리즘을 풀어내는데 생성을 제외하고 추가적으로 

메모리 할당이 없으므로 공간 역시 O(n)이다.