알고리즘 문제 해결 전략 I (4)

알고리즘 문제 해결 전략 I  (4)

프로그래밍 대회에서 많이 하는 실수 : 쉬운 문제를 어렵게 푸는것 - 무식한 알고리즘

컴퓨터의 빠른 계산을 이용한 가능한 경우의수를 일일이 나열하면서 답을 찾는 방법을 의미.

- > 완전 탐색 (exhaustive search) 이라고 부른다.

사실, 컴퓨터의 장점을 가장 잘 이용하는 방법.

 

*STL 표준 템플릿 라이브러리

vector 컨테이너 클래스 : 배열을 다루기 용이한 함수

#include <vector>

vector<int> intV(5); // intV라는 int 데이터형 5개의 변수를 가진 배열을 생성

vector<int> intV; // 0개의 변수를 가진 배열을 생성 가능

intV.push_back(value); //value 값을 배열에 마지막 원소 자리를 생성 후 대입

intV.resize(intV.size() + 1); //intV의 원소 size에 1을 더한 수만큼 intV의 원소 개수를 resize 시킴

 

list 클래스 : 데이터목룍들을 포인터를 사용하여 연결한 것으로서 , 한쪽 방향으로만 연결된 단방향 링크드 리스트와 양쪽방향으로 연결된 양방향 링크드 리스트가 있다. 

배열과 유사하게 리스트를 쉽게 다룰 수 있도록 함

#include <list>

list<int> MyList; //int 형 list 생성

MyList.push_back(i); //MyList의 마지막 원소 뒤에 i를 삽입

MyList.front() // MyList의 첫번째 원소

MyList.back() // MyList의 마지막 원소

 

리스트와 배열의 차이점

배열의 경우 [index]를 활용하여 임의 원소에 대한 접근이 빠른반면 리스트는 포인터 base로 되어 있어, 처음 원소부터 포인터로 따라가야 하는구조를 가짐.

배열은 임의 위치로의 삽입과 삭제가 느린 반면 리스트는 빠른 특징을 갖고 있음.

 

 

재귀호출과 완전 탐색

재귀호출/재귀함수: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고 나머지를 자기 자신을 호출해 실행하는 함수

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

 

출처 : 나무위키

코드1. 자연수 n이 주어졌을때 1 부터 n까지의 합을 반환하는 함수 sum()의 구현을 보여준다.

int sum(int n) {
	int ret = 0;
	for (int i = 1; i <= n; ++i)
	{
		ret += i;
		return ret;
	}
}

int rSum(int n) {
	if (n == 1) return 1;
	return n + rSum(n - 1);
}

 

 *더 이상 나눌수없는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다.

더 이상 나눌수없는 가장 작은 작업들을 가리켜 재귀호출의 기저 사례 (Base case)라고 한다

 

재귀호출은 기존의 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공한다.기존의 코드에서는 이득이 얼마 없지만, 문제의 특성에 따라 코딩을 훨씬 간편하게 해줄 수있는 도구가 된다.

 

예제) 전체 원소에서 n개의 수를 뽑아내는 모든 경우의 수를 출력하는 함수

코드2. 보통 for문을 이용한 코드

	int number[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
	int n = 8;
	int count = 0;
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			for (int k = j + 1; k < n; ++k)
				for (int l = k + 1; l < n; ++l)
				{
					cout << i << " " << j << " " << k << " " << l << endl;
					count = count + 1;

				}
	cout << count << endl;

 

 

재귀함수를 이용한 코드

 

 

 

 

참고문헌 : 알고리즘 문제 해결 전략 I pp.144~ 中 

2020.07.10