[알고리즘] Algorithm 이란? (시간 복잡도, 빅오 표기법)

 

안녕하세요. 코딩 좀 해본 한코딩입니다.

본교 교과목 중 알고리즘 수업을 대비하여 예습 내용을 정리해볼까 합니다.

알고리즘이란?

- 어떠한 문제를 해결하기 위한 여러 동작들의 모임

​

그렇다면 알고리즘을 배우기 위해선 어떻게 해야 할까요?

알고리즘 공부는 문제 풀이가 핵심입니다.

---

 

알고리즘 공부 방법

이런 알고리즘을 공부하며 문제가 있는 여러 사이트가 있습니다.

​

1. Baekjoon

https://www.acmicpc.net/

Baekjoon Online Judge

Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. 9198 전체 문제 7870 채점 가능한 문제 6697 풀린 문제 36 채점 가능한 언어

www.acmicpc.net

2. Algospot

https://algospot.com

algospot.com :: 알고스팟에 오신 것을 환영합니다!

kriii 제8회 전국 대학생 프로그래밍 대회 동아리 연합 대회(이하 UCPC2019)가 삼성전자와 삼성소프트웨어멤버십 의 후원을 받아 열립니다!!!! 예선은 7/27(토)에 진행할 예정이며, 본선은 8월 중 토요일에 진행할 예정입니다. (장소가 아직 확정되지 않아 후에 공지할 예정입니다. 1주차 또는 2주차 토요일로 예상합니다.) 반드시 3인 1팀으로 작성해주셔야 합니다. 신청은 6월 30(일)까지 받을 예정입니다. 그러니 늦지 않게 신청해주시기 바랍니다. 예선은 온라인, 본선은 온사이트로 진행됩니다. 본선은 팀원 모두가 시간 내...

algospot.com

3. Codeforces

http://codeforces.com

 

Codeforces

 

codeforces.com

4. Topcoder

http://topcoder.com

Design & Build High-Quality Software with Crowdsourcing | Topcoder

The Topcoder Community is the world’s largest network of designers, developers, and data scientists, and we’re ready to begin work on your projects. Start getting more work done with the world’s largest talent marketplace today!

topcoder.com

대표적으로 이런 사이트에서 문제를 보고 채점해주는 서비스를 제공합니다.

그렇다면 공부는 어떻게 해야 할까요?

​

- 알고리즘이나 문제를 푸는 방법을 이해하자!

- 관련 문제를 풀어보자!

- 어려운 부분이 있다면 질문하자!

- 정말 못 풀 때까지 하고 안되면 풀이를 보자!

​

포기하지 않고 끝까지 해보고, 정 안되면 풀이를 보는 것이 중요합니다. 왜냐하면, 알고리즘 공부는 알고리즘을 만드는 것이 중요한 게 아니라 생각하는 과정에서 스스로 생각해내는 사고력을 키우는 것이 중요하기 때문입니다.

​

참고로, 알고리즘을 공부할 때에는 C++로 진행하는 것이 좋습니다. C, C++, JAVA 등 여러 언어를 사용하지만, C++이 좀 더 대중화되어 있습니다. 후에 모르는 것을 구글링 하면 대부분 C++ 소스코드로 작성되어 있어 풀이를 보기 편합니다.

 

---

 

시간 복잡도, 빅오 표기법 (Big O Notation)

시간 복잡도는 '입력의 크기에 대해서 시간이 얼마나 걸리는지'를 나타내는 방법입니다.

즉, 작성된 코드가 시간이 얼마나 걸릴지 예상을 할 수 있습니다. 표기법은 대문자 O를 사용합니다.

자료구조 과목을 이수하셨다면 복잡도를 잘 아실 겁니다. 간단하게 예를 들어봅시다.

int sum = 0; for (int i=1; i<=N; i++) sum += i;

자 이렇게 반복문으로 1부터 n까지 합을 구하는 소스의 복잡도는 무엇일까요?

바로 O(N)입니다. 하지만, 우리는 알 수 있습니다.

1부터 N까지의 합을 구하려 할 때 굳이 반복문을 사용하지 않아도 됩니다. 바로 이렇게요.

int sum = 0; sum = N * (N+1) / 2;

마찬가지로, 이 소스도 1부터 n까지의 합을 구합니다. 복잡도는 무엇일까요?

바로 O(1)입니다. 대입 연산 하나만 존재하기 때문이죠.

이렇게, 같은 기능을 하는 프로그램이라도 복잡도는 개발자의 숙련도에 따라 달라집니다.

​

대표적으로 시간 복잡도는

​

O(1) < O(log N) < O(N) < O(N * log N) < O(N^2) < O(N^3) < O(2^N) < O(N!)

​

순으로 시간 복잡도가 증가하여 프로그램 실행 시간이 길어집니다.

​

대체로 시간 복잡도의 의미는 이렇습니다.

​

O(1) : 단순 계산 ( a + b)

O(log N) : n 개를 절반으로 계속 분할

O(N) : 반복문

O(N * log N)

O(N^2) : 2중 반복문

O(N^3) : 3중 반복문

O(2^N) : 크기가 n인 집합의 부분 집합

O(N!) : 크기가 n인 순열

​

우리는 우리가 만든 프로그램의 시간 복잡도를 계산할 줄 알아야 합니다.

그럼 빅오 표기법은 무엇인가?

빅오 표기법은 단순히 시간 복잡도에서 상수를 제거한 것입니다. 예를 들어,

​

1) O(6 * N^2) => O(N^2)

2) O(2 * N^2 + 3 * N) => O(N^2)

3) O(3 *N + M) => O(N + M)

​

이렇게 바꾸는 것입니다. 1)에서는 N^2의 상수만 제거하였습니다.

​

하지만 2)에서는 N^2에 상수뿐만 아니라 3 * N도 제거한 이유는

두 항 중에 더 큰 항을 살리고 나머지 항은 제거했기 때문입니다.

​

게다가, 시간 복잡도에 변수가 2개 이상이면 상수만 제거하고 변수가 다를 때에는 모든 변수를 제거하지 않습니다.