0. Intro

전북대학교 알고리즘 동아리 'COALA'에서 진행하는 기초 알고리즘 튜터링 내용을 기록합니다.

 

이 튜터링을 진행하기에 앞서 필요한 지식은 다음과 같습니다.

 

1. C/C++ 기본 문법에 대해 알고 있어야합니다.

2. 함수 사용 및 재귀함수가 무엇인지 알고 있어야 합니다.

 

 

알고리즘 문제를 잘 해결하기 위해서는 3가지가 필요합니다.

 

1. 여러 알고리즘, 자료구조 등 배경지식이 필요합니다.

2. 배경지식을 현재 문제 상황에 맞게 잘 선택, 변형할 줄 아는 능력(문제해결능력)이 필요합니다.

3. 생각한 풀이를 코드로 나타낼 수 있는 능력(구현력)이 필요합니다.

 

우리는 이 세가지 능력을 기르는 연습을 해야합니다.

 

www.acmicpc.net  

Baekjoon Online Judge

알고리즘 문제 채점 사이트인 백준 온라인 저지입니다.

우리는 이 사이트에서 같이 문제를 해결하며 성장해나가면 됩니다.

 

알고리즘에 대해 알기 전에 시간복잡도, 공간복잡도에 대한 이해가 필요합니다.

 

시간복잡도는 해당 코드가 "몇번 정도 연산을 하는가?" 에 대한 내용이고,

공간복잡도는 해당 코드가 "어느 정도의 메모리 공간이 필요로 하는가?" 에 대한 내용입니다.

 

먼저 시간복잡도 입니다.

 

컴퓨터는 1초에 대략 3억번의 연산을 처리할 수 있습니다. (어떤 연산이냐에 따라 횟수는 달라지므로 3억번이 절대적인 수치는 아닙니다.)

만약 해당 문제의 시간 제한이 1초라면, 입력에 대해 3억번 이내의 연산횟수로 문제를 해결해야만 합니다.

 

 

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
        printf("%d\n", i * n + j);
    }
}

위 코드를 실행한다고 합시다. 

printf()함수는 총 \( n^{2} \) 번 호출되는 것을 알 수 있습니다.

\( n = 100 \) 이라면 총 10,000 번 연산하므로 1초 이내로 코드가 돌아가지만,

\( n = 1,000,000 \) 이라면 총 1,000,000,000,000 번 연산하므로 1초 이내로 코드가 돌아가지 않습니다.

 

우리는 이런 시간복잡도를 빅오 표기법(O)을 사용하여 나타냅니다.

\(  O(n^{2}) \) -> \( 대략 n^{2} \) 회 정도 연산한다는 뜻입니다.

시간 복잡도 함수가 \( 2n+7 \) 과 같이 나올 수 있지만 빅오 표기법은 최고차항의 계수와 낮은 차수의 항을 제외시켜 간단하게 표기하는 방법입니다.

\( 2n+7 \) -> \( O(n) \) 과 같이 표현할 수 있습니다.

 

다음은 공간복잡도 입니다.

 

우리는 메모리 제한이 128MB 또는 256MB인 문제들을 만나게 될 확률이 높습니다.

프로그래밍 언어 기초를 배우셨다면 아시겠지만, 자료형 int의 크기는 4byte 입니다.

 

어떤 이유로 우리가 int형 배열을 10억 크기로 만들어서 문제를 푼다고 합시다.

이때 필요한 메모리 크기는 얼마일까요?

\( 4 \times 10^{9} byte \) 만큼의 메모리 크기가 필요할 겁니다.

 

메모리제한이 128MB 였다면 우리가 만들 수 있는 int형 배열의 크기는 

\( 4 \times 32 \times 10^{6} byte  \) 일겁니다. (실제로는 더 적은 크기를 선언할 수 있습니다.)

그러므로 10억 크기의 배열을 선언하는 방법이 아닌 다른 방법으로 문제를 해결해야겠죠?

 

 

 

지금 당장은 위 내용이 이해가지 않을 수 있습니다. 하지만 여러 알고리즘을 접해보고 문제를 해결하다보면 익숙해지고 편해집니다.