어떤 것들끼리 비교하고 분석하기 위해서는 기준이 있어야되고,
해당 기준을 측정할 수 있는 도구가 필요합니다.
컴퓨터를 이용한 문제해결 영역에서는
얼마나 효율적으로 문제를 해결했는가에 대해 비교, 분석을 하고,
효율을 판단함에 있어서 시간복잡도와 공간복잡도라는 도구를 사용합니다.
시공간복잡도?!
먼저, 시간복잡도에 대해 알아봅시다.
시간복잡도를 간단하게 말하면,
"문제를 해결하는데에 당신의 코드가 얼마나 오래 돌아갈껀지"를 뜻합니다.
알고리즘 문제를 풀 때 시간복잡도는
입력 데이터가 주어졌을때, 당신의 코드가 얼마나 시간이 걸릴지를 알아내는 도구입니다.
회사에서 업무를 볼때에는
일이 주어졌을때, 당신이 얼마만에 처리할 수 있는지
프론트 개발자가 업무를 볼때에는
디자인이 나왔는데, 당신이 얼마만에 구현할 수 있는지
학교에서 수업을 들을때에는
과제가 주어졌을때, 당신이 얼마만에 풀어낼 수 있는지
친구와 연인 사이에서는
카톡을 보냈는데, 당신이 얼마만에 답장하는지
말을 걸었는데, 당신이 얼마만에 대답하는지
등등
주어진 일에 대한 처리 시간으로 요약됩니다.
보통 시간복잡도는 코드를 모두 작성한 다음 생각해보는 대상이 아닌
코드를 작성하기 전에 고려해봐야하는 대상입니다.
내 코드가 얼마나 시간이 걸릴지 실행시켜보지 않고 어떻게 알 수 있을까요?
도대체 어떻게 가능한 일이죠?
그전에 코드가 있을 때 복잡도를 어떻게 계산하는지 알아봅시다.
프로그램 작성 코드에 기본 단위가 존재합니다.
연산자들이 기본 단위인 1로 계산됩니다.
연산자에는 종류가 많죠?
- 대입 연산자
- 논리 연산자
- 관계 연산자
- 대입 연산자
- 증감 연산자
- 조건 연산자
보통 한 줄로 하나의 일이 마무리되는 코드가 1의 시간이 걸린다고 봅니다.
하나의 일을 여러번 반복시키는 반복문의 경우 1을 반복시킨 횟수만큼 더하면 되겠죠?
해당 연산자들이 모여 1억(10^8)이 될 경우 대략 1초가 걸린다고 예측합니다.
만약에 아래와 같은 코드를 작성했다고 합시다.
int data[100], n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&data[i]);
}
int max = 0;
for(int i=0;i<n;i++){
if(max<data[i]){
max=data[i];
}
}시간복잡도는 아래와 같이 계산됩니다.
int data[100], n; // 1
scanf("%d",&n); // 1
for(int i=0;i<n;i++){ // n
scanf("%d",&data[i]); // 1
}
int max = 0; // 1
for(int i=0;i<n;i++){ // n
if(max<data[i]){ // 1
max=data[i]; // 1
}
}
// 3 + n*1 + n*1*1 = 2*n + 3이제 대충 계산하는 방법을 알았으니,
코드를 대충 써놓고 계산하는 방법을 알아봅시다.
코드를 컴파일 할 수 있을 정도로 작성했다면,
그냥 실행해봐서 얼마나 걸릴지 보면 됩니다.
허나 문제를 해결하기 전에는 코드가 작성되어있을 수 없겠죠?
적당히 대충 쓴 코드를 수도 코드라고 합니다.
사실, 수도 코드도 "코드"이기때문에 위에 보여드린 예시처럼 계산할 수 있습니다.
곧바로 다음 단계로 넘어가서,
코드란 것을 아예 짜기도 전에 시간복잡도를 어떻게 계산할까요?
이는 훈련에 의해 가능해집니다.
아래의 글은 다음 3가지 가정을 깔고 갑니다.
1. 탐색할 공간에 대한 파악이 완전히 된 상태를 가정합니다.
2. 필요한 계산을 어떤 논리로 짜면 되는지 알고 있는 상태입니다.
3. 입력 데이터 크기 제한에 대한 파악이 된 상태입니다.
생각의 순서는 다음과 같습니다.
1. 문제분석: 목표, 상황 분석
2. 방법생각: 무식한 방법부터 적용, 세부 목표 설정 및 관계 파악
3. 제한검토: 시간복잡도, 공간복잡도, 문제 제한 상황에 맞게 동작하는 방법인지
예를 들어 설명해보겠습니다.
N개의 숫자가 주어지고, 2개의 숫자를 합 했을때 값이 K가 되는 쌍을 찾고 싶습니다.
가장 무식한 방법은 모든 숫자 조합 합을 탐색하고 합이 K가 되는지 확인하는 것 입니다.
해당 방법의 복잡도는 N개의 숫자 중 2개를 골라야하므로 nC2가 됩니다.
N개의 숫자 중 숫자 1개를 고르고, 바로 다음으로 숫자 1개를 고르는 상황이니
2중 for문이 필요하다는 것을 알 수 있습니다.
만약 코드가 감이 잡히지 않더라도
코드를 작성하지 않아도 탐색해야될 공간의 개수를 알고 있어서,
대략적인 시간복잡도를 예상할 수 있습니다.
이때, N이 엄청나게 클 경우 제한 시간 내에 원하는 결과를 얻지 못할 수도 있습니다.
N이 10,000이 되면 10,000 x 10,000 = 10^8으로 1초가 소요되고,
그 이하일 경우 더 이상 생각할 필요 없이 코드를 작성하면 됩니다.
그 이상으로 커질 경우 1초보다 더 시간이 걸리게 됩니다.
내 논리가 얼마나 많은 연산량을 요구할지 알기 위해서는
나의 논리를 최적화된 코드로 바꿔보는 연습을 많이 해봐야합니다.
처음부터 복잡한 논리를 예측해보는 것은 쉽지않습니다.
쉬운, 간단한 논리부터 코드로 구현해보면서
점차 어려운 논리까지 단계적으로 훈련해나가는 것이
운동으로 치자면 점진적 과부하가 되겠죠?
이제, 공간복잡도는요?
공간복잡도는 여러분들이 사용하게 될 변수의 개수, 크기와 관련이 있습니다.
변수의 개수가 많고, 크기가 클 경우 공간을 더 많이 필요로 하죠.
공간복잡도에 대한 자세한 얘기는 생략하고,
Memory limit exceed에 대한 얘기만 해봅시다.
문제를 읽어보면 메모리 제한이 나와있습니다.
보통 128MB, 256MB, 512MB로 적혀있습니다.
문제를 푸실 때 사용하신 변수형이 INT고, 배열로 10,000개를 만들었다고 하면
INT의 크기인 4Byte x 10,000 로 0.04 MB 만큼 사용한 것입니다.
만약, INT로 10,000 x 10,000 2차원 배열을 만들 경우,
400MB를 사용하게 되겠죠. 아마 생각한 것보다 많이 메모리를 사용하고 있을거에요.
보통 문제를 풀 때 배열을 만든다고하면 10^6을 최대라고 봅니다.
그 이상을 넘어가게 되면 메모리도 그렇고, 시간복잡도도 그렇고 제한사항에 걸리게 되죠.
만약 10^6 보다 큰 배열을 잡아야된다고 생각이 들면 효율적으로 개선시켜야 합니다.
효율성 따져서 개선시켜봅시다
이제 판단 기준과 도구를 알았으니, 무식한 방법을 효율적 방법으로 바꿔볼까요?
N개의 숫자가 주어지고, 2개의 숫자를 합 했을때 값이 K가 되는 쌍을 찾는 문제에서
무식한 방법의 한계를 봤습니다.
무식한 방법을 하나씩 뜯어보며 어디를 개선할 수 있을지 생각해봅시다.
처음부터 다른 새로운 방법을 생각해보는 것이 아닌
무식한 방법에서 효율적으로 할 수 있는 부분을 찾는 것이죠.
상황을 다시 보자.
N개의 숫자 중 숫자 1개를 고르고, 바로 다음으로 숫자 1개를 고르는 상황이었습니다.
또한, 두 수의 합이 K가 되어야하는 조건이 있습니다.
두 수를 A, B로 뒀을때, A+B=K가 되는 숫자 조합을 찾아야합니다.
만약 A를 결정했다면 B는 자연스레 K-A가 되는 것을 알 수 있습니다.
상황을 다시 써보면, 다음과 같이 바뀌게 됩니다.
N개의 숫자 중 숫자 1개 A를 고르고, K-A를 찾는 상황입니다.
이전의 무식한 방법으로는 숫자 N개를 모두 뒤져봐서 K-A가 맞는지 확인했습니다.
만약 모두 뒤져보지 않아도 된다면, 탐색 효율이 좋아지겠죠?
공간을 손볼까?
현재 탐색 공간은 어떠한 규칙성이 있는지 모르는 상태이며,
규칙성 자체가 없을 수도 있습니다.
만약, 탐색 공간을 어떠한 규칙성을 가지고 정돈을 한다면,
굳이 모든 수를 훑어보지 않아도 대충 어떤 값이 있을지 알게 됩니다.
이전에는 임의의 위치에 어떤 값이 있는지 아예 몰랐지만,
특정 위치에 이 정도 값이 있겠구나 정도 알게 됩니다.
수의 체계에서는 비교를 통해 크고 작음이 존재합니다.
해당 기준을 통해 오름차순, 내림차순으로 숫자들을 나열할 수 있죠.
숫자가 뒤로 갈수록 커지게 오름차순으로 정렬되어있다면,
가장 앞의 수는 가장 뒤의 수보다 작다는 것을 직접 확인하지 않아도 알 수 있습니다.
이제, 대충 원하는 수가 어디쯤 존재할지 알게되었습니다.
정리
숫자를 정렬한다.
첫 번째 숫자부터 짝을 찾는다.
짝을 찾을때는 이진 탐색을 통해서 한다.
안쪽에 존재한 짝을 찾는 for문이 선형 탐색에서 이진 탐색으로 개선되었습니다.
for(){ for(){} }
for(){ binary_search() }
이에 따라, 시간 복잡도가 O(N^2)에서 O(NlgN)으로 개선되었습니다.
사실 말이죠
보통 사람이라면 자연스레 이진 탐색을 떠올릴 확률이 좀 적습니다.
효율적인 알고리즘들은 논문을 통해 세상에 공개된 것이 많죠.
그만큼 오래 생각을 해봐야하고, 검증도 해봐야합니다.따라서, 효율적 알고리즘을 만들어내는 것이 목표가 아니라면,
문제해결능력을 기르는 것이 목표라면,
효율적 알고리즘은 개념적 지식으로 습득하는 것이 좋습니다.효율적인 방법들을 단계별로 정리하고 머리에 넣어두고,
상황에 맞게 알맞은 방법으로 문제를 해결하는 연습이 중요하겠습니다!
마무리
문제해결방법을 비교하는 기준과 도구에 대해서 알아봤고,
해당 도구를 사용해서 무식한 방법을 개선시켜도 봤습니다.
시간복잡도, 공간복잡도 개념 자체에 대해서는
구글링을 하시면 더욱 자세한 내용을 학습하실 수 있습니다.
다음 시간 예고
binary search에 사용된 분할 정복에 대해서 알아봅시다!
