Simple in Complex with Simple

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)이다.

1. 문제

 다음과 같은 그림에서 초록색 노드를 찾는 알고리즘을 작성하시오.

2. 코드

2-1) 메인

2-2) 교차 리스트 생성 함수

2-3) 메인 알고리즘 함수

2-4) 출력

3. 해설

 이 문제는 아주 간단하다. 2개의 리스트 생성 시간 O(n+m)에 검색시간 O(n)을 더해서 최종적으로 빅오를 따지기에

O(n+m)에 풀린다. 스택이나 다른 방법으로도 충분히 풀어낼 수 있지만 이 포스팅에서는 Hash방법을 이용해서 

풀었다. 메인 알고리즘은 처음 생성한 리스트의 노드 주소를 모두 Hash 테이블에 저장한 뒤, 두 번째 리스트와

Hash 테이블을 같은 노드의 주소가 나올 때까지 비교한다. 

 딱히 어려운 알고리즘은 아니지만 굳이 포스팅한 이유는 Hash라는 기법에 더 익숙해지기 위해서이다. 왜냐하면 모든

기초 알고리즘은 모든 경우를 다 검색하는 Brute Force기법, 정렬을 이용한 기법, 스택이나 큐를 이용한 자료구조를

활용한 기법 그리고 마지막으로 Hash 방법을 사용하여 풀어내는 기법. 총 4가지로 구분되기 때문이다. 앞으로 알고리즘

을 생각할 때에는 위의 순서에 준해서 생각한다.