시간초과가 뜨면 보통 while문에서 뜨게 된다. 그 말은 while안에서 답이 안나왔을 가능성이 크다. 이럴 때에는 break의 조건이나 위치를 한 번 더 생각해본다.
2. 동적 할당을 어설프게 쓰지 말자.
정적 할당으로 원하는 만큼 배열을 만들면 에러가 날 수 있다. ex) cin >> n; int arr[n];
gcc버전에 따라서 다르기 때문에 이런식으로 쓰면 될 수도 있고 안 될수도 있다. 그러면 동적할당을 쓰는게 편한데..
int * arr = new int [];
이렇게 쓰면 되는데 확실히 알고 쓰지 않으면, 예를 들어 위의 대괄호를 소괄호로 바꿔쓴다거나 하면 시간초과로 문제를 실패할 수도 있다. 동적할당은 완벽하게 쓰자.
3. 누가 봐도 큰 수를 조심하자.
주어지는 변수의 범위가 K(1<=K<=2,000,000) 이런 것들이 있다. 이 때에는 모두를 조사하지 않는 예외 조건을 붙이거나 최소한으로 계산할 수 있도록 해야한다. 하지만 여기서 중요한 것은 테스트 코드를 실행시켰는데 틀렸다는 것과 시간초과가 같이 뜬다면 그냥 틀린거다.
이분 검색이란 정렬된 배열에서 원하는 결괏값을 빠르게 찾는 방법이다. 우리가 보통 업/다운 게임을 하면 정해진 숫자 범위 안에서 절반부터 나누며 시작하는 것을 알 수 있다. 그것과 같은 원리로 정렬이 된 상태에서 업다운 게임을 하며 원하는 배열을 찾는 것이다. 소스의 구현은 다음과 같다.
위에 9개의 배열이 있다. 배열의 왼쪽 끝 배열을 left 변수에, 오른쪽 끝 배열을 right 변수에, (left+right)/2를 mid에 넣는다. 그 후에 찾으려는 값을 mid와 비교한다.
예를 들어 내가 원하는 값이 4라면 어떻게 찾을까? 초기 값은 left는 0, right는 배열의 끝, mid는 (left+right)/2이다.
left=0, right=8, mid=4
원하는 값이 4라면 mid[(0+8)/2]보다 작으므로 right에 mid-1 값이 들어가게 된다. 그러면 left는 0이고 right는 3이 들어간다.
left=0, right=3, mid=1
mid는 (0+3)/2=1.5이므로 1의 값이 되고(정수) 2번째 배열인 2값을 가리킨다.
2보다 크므로 left에 mid+1이 들어가서 2가 된다.
left=2, right=3, mid=2
마지막으로 left는 2, right는 3이므로 mid는 2가 되고 mid가 4가 되었으므로 탐색을 종료한다.
장점은 아무래도 모든 값을 조사하는 것보다 훨씬 적은 수를 비교하게 되어 속도면에서 빠르다는 것을 알 수 있다. 그리고 배열을 가리키는 변수를 놓는 방식으로 응용문제를 해결할 수 있다. 예를 들면 다음과 같다.
배열의 크기(1≤N≤1,000), 나누는 수(1≤M≤N), 배열 값(1≤arr≤10000)이 주어진다. 배열의 순서를 바꾸지 않고 나눈다고 했을 때, 나누어진 각각의 배열의 합 중 최대인 것이 가장 작아질 수 있도록 하여라. 아래 예제는 9개의 배열을 3개로 나눌 때 8+9가 17이 되어 1+2+3+4+5, 6+7보다 크지만 가장 작게 나눌 수 있는 방법이다. 왜냐면 8이나 9가 딴 데 붙으면 다른 배열이 17보다 커지기 때문이다.
이런 문제를 풀 때는 정답을 미리 정해놓고 생각할 수 있다.
예를 들면, 이 예제에서 나올 수 있는 최대 정답은 1에서 9까지 모두 더한 45일 것이다. 그러면 정답의 범위가 1부터 45까지이다. 여기서 이분 탐색으로 정답을 정해놓는다. 정답을 (1+45)/2라고 하자. 그러면 23을 기준으로 나누게 된다. 그러면 분명 위의 배열은 3개가 아닌 2개로 나누어진다. 그러면 값이 너무 큰거니 정답을 다시 이분탐색 알고리즘에 넣어 (1+23)/2=12로 놓고 배열을 나눈다. 그러면 3개로 나누고 더 많이 남게 된다.[(1,2,3,4),(5,6), (7)...] 그러면 값이 너무 작은거니 다시 바꾼다.
이렇게 맞춰질 때까지 값을 정해서 푸는 방법을 결정알고리즘이라고 한다.
간단한 알고리즘이지만 매우 효과적이며 응용도 가능한 좋은 알고리즘이라 꼭 외워두면 좋은 것 같다.
이제 기본적인 산수, 반복 문제를 쉽게 풀 수 있다면 sort 문제를 쉽게 풀 수 있을 것이다. sort는 정렬이라는 의미로 알고리즘을 처음 배우는 사람들이 가장 먼저 접하는? 그리고 공부하는 사람들이 가장 먼저 배우면서 짜증 나는 파트이기도 하다. 왜냐하면 정렬의 종류가 많은데 뭔 의미인지 모르겠기 때문이다. 일단 가장 기본적인 세 가지 정렬이 있다. 이 기본적인 정렬은 작성하기는 쉽지만 시간복잡도가 큰, 즉 효율이 적은 정렬을 말한다.
하지만 이 세 가지 정렬은 마지막에 보고 그 전에 빠르게 알고리즘을 사용할 수 있는 방법이 있다. 바로 sort 함수를 이용하는 것이다. 사용법은 <algorithm> 라이브러리를 추가한다. 그리고 sort 함수를 사용하면 된다. sort 함수를 사용하는 방법은 두 가지인데 compare 함수를 쓰느냐 마느냐가 있다. 빠르게 오름차순으로 정렬하려면 compare함수가 필요 없이 배열의 크기만 알고 있으면 된다.
#include <algorithm>
int arr [100];
sort(arr, arr+100);
이렇게만 하면 정렬이 된다. 여기에 오름차순 내림차순을 바꿔주려면 compare함수를 추가한다.
bool compare(int x, int y)
{ return x <y;
}
저기에 x <y면 앞에가 더 작고 뒤에나 더 커지는 오름차순, x> y를 하면 내림차순으로 정렬이 된다. 그리고 sort 함수에 추가한다.
sort(arr, arr+100, compare);
이렇게 하면 기본적인 정렬 문제를 풀 수 있다. 예시로 구글 문제를 가져왔다.
이 문제의 경우 배열을 정렬시켜서 값을 처음부터 비교해보면 쉽게 알 수 있다.
이 아래는 3가지 정렬인데 이름과 비슷하므로 이러한 정렬이 있구나를 생각만 해놓으면 된다. 나중에 응용해서 다른 문제를 풀 수도 있다.
1. 버블 정렬
버블 정렬은 기준 배열과 바로 오른쪽 옆 배열과 비교하여 바꾸는 형식으로 가장 쉽게 생각할 수 있는 방식 중 하나이다. 비교대상이 바로 옆이라 직관적으로 알기 쉽다. 바꾼 뒤에는 기준 배열을 오른쪽으로 한 칸 옮기고 다시 비교하고... 이런 식이다. 딱 봐도 여러 번 실행해야 하는 것을 알 수 있다. 기본적인 코드는 아래와 같다.
void bubbleSort(int arr [], int size) {
int i, j;
for (i = size - 1; i>0; i--)
for (j = 0; j <i; j++)
if (arr [j]<arr [j + 1])
swap(&arr [j], &arr[j + 1]);
}
2. 선택 정렬
선택 정렬은 가장 작은 수나 가장 큰 수를 찾아 첫 번째에 넣고, 그다음 큰 숫자를 그 다음 배열에 넣고 하는 식으로 진행이 된다. 넣을 때에는 새로운 배열을 써도 되지만 swap을 통해 하나의 배열로 바꿀 수도 있다. 정렬은 기본적으로 한 개의 배열로 하나보다. 기본적인 코드는 아래와 같다.
void selectionSort(int arr [], int size) {
int minIndex;
int i, j;
for (i = 0; i < size - 1; i++) {
minIndex = i;
for (j = i + 1; j < size; j++)
if (arr [j] < arr [minIndex])
minIndex = j;
swap(&arr [i], &arr [minIndex]);
}
}
3. 삽입 정렬
삽입 정렬에서는 key값이 등장하는데 보통 배열의 1번부터 시작해서 맨 앞의 원소랑 비교한 뒤 그 뒤에 원소들과 비교를 한다. 그래서 그 원소보다 작으면 그 위치에 넣고 뒤의 배열을 밀어버린다.
기본적인 산수를 풀 수 있는 실력이 되었다면 그다음으로 보는 것이 반복문이다. 반복문의 종류는 크게 두 가지로 나뉜다고 생각한다.
1. 배열로 저장이 필요 없는 반복문.
2. 배열로 저장이 필요한 반복문.
배열로 저장이 필요 없는 반복문은 값을 받는 for문에서 바로 비교가 가능하고 계산해서 출력이 가능한 경우이다. 예를 들면 다음과 같다.
ex) 3< n <100,000,000의 숫자가 입력이 되고, 1부터 n까지의 숫자를 센다. 사용된 숫자의 개수는 몇일까?라는 문제에서 1부터 n까지의 숫자를 모두 배열에 저장할 필요는 없다. for문을 돌려 앞에서부터 바로바로 값을 저장시키면 된다. 위의 문제는 수가 크기 때문에 일일이 값을 받지 않고 약간의 수학적 직관성을 이용하여 문제를 풀 수 있다. 10 단위씩 끊어서 10까지 몇 개, 100에서 10 빼면 몇 개, 1000에서 100 빼면 몇 개라는 식으로 풀 수 있다.
int n, sum=0, cnt=1, digit=9, res=0; scanf("% d", &n); while(sum+digit <n){ sum=sum+digit; res=res+(cnt*digit); cnt++; digit=digit*10; } res=res+((n-sum)*cnt); printf("% d\n", res);
배열로 저장이 필요한 부분은 정렬 같은 문제가 대표적이다. 다른 뒤에 것들과 모두 비교해서 순서나 등수를 매기는 문제들은 모두를 놓고 비교해야 하므로 배열에 저장할 필요가 있다. 근데 위에 문제처럼 단위가 1억 개 정도로 커지면 그때는 저장보다는 바로 비교가 가능하다는 뜻이다. 다음 문제처럼 문자열이 나오거나 서로 비교해야하면 보통은 문자열로 받아서 풀면 편하다.
아마 많은 사람들이 알고리즘을 처음 공부할 때 어떤 언어로 하는 것이 이득인지 생각하고 찾아볼 것이다. 나도 그랬으니까...
결과적으로는 똑같다고 한다. 두 언어 다 못한다면 python으로 공부하는 것이 편할 수 있다. 하지만 그렇다고 c언어에 익숙한데 python을 따로 공부하는 것은 비효율이라는 뜻이다.
python이 편하기는 하지만 c언어와 사용법이나 함수명이 확연히 다르므로 괜히 쓰다 헷갈릴 수도 있다. 그리고 python이 지원하는 함수들이 많아서 확실히 편할 것이라고 생각할 수 있는데, 사실이긴 하나 c언어에서 충분히 구현 가능하고 python 쓴다고 코테에서 무조건 좋은 성적을 받는 것은 아니기 때문에 처음 알고리즘을 공부하는 사람들이라면 자신이 평소에 쓰는 언어, 편한 언어로 공부하는 것이 좋을 것 같다.
