요즘 백준 문제 풀면서 많은 것을 느꼈다. 알고리즘 문제는 어느정도 규칙과 흐름이 정해져있다는 것을, 그 중 첫번째는 문제 이해!
가장 먼저 문제를 해결하기 위한 최적의 절차는 문제를 이해하는 것이라고 생각한다. 문제를 이해함으로써 문제 해결에 필요한 조건과 제약사항을 파악한다. 여기서 문제해결에 필요한 조건은 어떤 자료구조와 알고리즘을 사용하여 문제해결을 할지이다. 제약사항은 보통은 어떤 테스트 케이스의 횟수가 주어지면 몇 초 이내 실행하라는 요구사항이 주어진다. 문제를 해석하면서 주어진 조건들을 만족할 수 있는 자료구조와 알고리즘을 먼저 설계해야한다.
아니, 잠깐만! 설명하기전에 자료구조와 알고리즘이 대체 뭔데!?
사실, 작년까지만해도 비전공자 친구들이 물어보면 매우 곤란했다. 머리가 아닌 가슴으론 이해가 되는데 막상 머리를 굴러 입 밖으로 꺼내려고하면 말이 잘 나오지 않았다. 하지만, 작년과 지금은 다르다. 지금 간단하게 설명해주겠다!
자료구조는 데이터를 효율적으로 저장하고 관리하는 방법이고 알고리즘은 이러한 저장된 데이터를 가지고 문제를 해결하는 방법을 다룬다.
그래도 이해가 안된다면...예를 들어주겠다.
자료구조는 배열, 리스트, 스택, 큐, 트리, 해시 테이블등 같은 데이터를 저장하는 구조라라면 알고리즘은 이러한 자료구조 배열, 리스트, 스택, 큐, 트리, 해시 테이블을 가지고 문제 해결에 선택하고 사용하여 알고리즘을 설계하고 주어진 문제를 풀어 해쳐 나갈 것이다.
이 게시글은 자료구조와 알고리즘에 대해서 설명하는 글이 아니니까, 이정도까지만 하고 다음에 다룰수 있다면 다뤄보겠다.
알고리즘 문제를 풀때 중요한 설계 사항 중 하나는 알고리즘의 수행 시간이다.
알고리즘은 자원을 얼마나 많이 또는 적게 소모하는지 분석할 때가 필요하다. 여기서 자원이라고 하면 메모리나 제한 시간을 말한다. 특히, 알고리즘에서 중요한 개념은 수행시간이라는 것이다. 데이터를 정렬하더라도 30개 100개 200개는 별다른 차이가 없지만, 만약 기업에서 10만개 100만개 혹은 1억개, 그 이상 레코드를 나이순 혹은 어떤 고유한 아이덴티티의 정보의 기준으로 정렬한다면 똑같은 정렬 알고리즘을 구현 하더라도 선택정렬과 버블정렬은 최악의 경우 logN^2 시간이 걸려서 몇주 혹은 몇달이 걸릴 수가 있다. 이럴 땐 힙정렬이나 병합정렬로 정렬을 해도 최악의 시간은 NlogN이 걸린다. 실무에서 가장 많이 사용이 된다고 한다.
여기서 나오는 수행시간은 입력의 크기에 대해 시간이 얼마나 소요되는지 표현한다. 시간복잡도라고 하는데 보통 빅-오 O-표기법을 주로 사용한다. 다른 표기법인 오메가 표기법, 섹타 표기법도 있다. 여기에 대한 주제는 다음 포스트에 시작 하겠다.
알고리즘의 또 다른 설계, 재귀와 귀납적 사고
Recursion은 컴퓨터 과학 이론의 근간을 이루는 아주 중요한 개념이다. 자기 호출은 어떤 문제를 해결하는 과정에서 자신과 같은데 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제에 해결에 간명하게 접근하는 방식이다. 재귀는 함수가 자기자신을 호출하는 것인데 많은 알고리즘 문제가 재귀를 사용한다. 재귀 함수를 사용하면 코드가 더 직관적이며, 간결해지며, 일부 알고리즘의 구현을 쉽게 할 수 있다.
예를들어, 재귀 알고리즘의 가장 대표적인 것들 중엔 피보나치 수열, 팩토리얼, 하노이 탑 등이 있는데 아래 코드는 피보나치 수열을 구하는 자바로 구현한 알고리즘이다. 재귀를 사용하면 아주 간단하게 코드를 구현할 수 있다.
public static int fibonacci(int n){
if(n == 0){
return 0;
}
else if( n == 1){
return 1
}
else
return fibonacci(n-1) + fibonacci(n-2);
}귀납적 사고(Inductive Reasoning)는 일반적인 패턴이나 규칙을 찾기 위해 특정 사례에서 출발하여 일반적인 패턴이나 규칙을 도출하는 과정이다. 알고리즘 설계에서 귀납적 사고는 일부 경우를 살펴 보고 일반적인 규칙을 도출하여 문제를 해결하는데 도움이 된다.
예를 들어, 여기 1부터 n 까지 합을 구하는 문제가 있다. 생각해보자면, 귀납적 사고를 사용하여 간단하게 해결할 수 있다. 합을 구하는 함수(메소드)를 자바로 표현해보겠다.
public static int sum(int n) {
if (n == 1) { // n이 1인 경우
return 1; // 1을 반환
} else { // n이 1보다 큰 경우
return n + sum(n - 1); // n과 n-1까지의 합을 반환
}
}
이 함수는 합을 재귀적으로 계산한다. 이러한 방식으로 귀납적 사고를 하고 점화식같이 일반적인 패턴이나 규칙이 나오면 재귀적 관점으로 보고 재귀 함수로 나타내면 아주 쉽게 문제에 접근할 수 있다.
마지막으로 글을 정리하며... 개인적으로 알고리즘 설계에 큰 힌트는
1.먼저, 문제를 잘 이해하고 이해하는 과정에서 나오는 요구하는 조건과 제약사항을 파악한다.
2.요구하는 조건과 제약사항에 대해 어떤 자료구조와 알고리즘을 사용하는게 가장 적절한지 생각을 한 후 적용시킨다.
3.귀납적 사고를 하여 어떻게 하면 재귀적으로 문제를 풀 수 있을까 생각해보고 적용시킨다.
4.사실, 가장 중요한건 많이 풀어보고 많이 적용시켜보는게 최고이지 않을까 싶다.
