CS의 꽃, 알고리즘과 시간복잡도

내 첫 TSTORY 게시글은 CS의 꽃이라 생각되는 알고리즘에 대해 쓰고 싶다.

(참고로 본 글쓴이는 구구절절하고 오프라인에서도 말이 굉장히 많다. 그러기 때문에 글이 길어질 수 있기에 중요한건 강조를 해놓겠다.)

알고리즘이란? 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것이다.(위키백과 출처) 

한 마디로 '문제 푸는 다양한 방식'이자 '문제 푸는 해결 능력'이라고 할 수 있다.

예를 들어, 내가 어떠한 장소를 가고자 할 때 그 장소를 가기 위한 버스/택시/운전/걷기 등등 다양한 방법이 있다고 하자. 나에게 지금 가장 중요한 것은 시간과 체력이라 할 때, 이 시간과 체력이라는 키워드를 가지고 가장 효율적으로 원하는 장소를 갈 수 있는 방법을 찾아내는 것이 알고리즘 사고의 핵심이다.

개인적으로 CS에서 가장 중요한 것이 자료구조 다음으로 알고리즘이라 생각하고 또한 4차 산업 혁명이 시작되면서 이른 코딩 사교육이 성행하고 있는데 어릴 적에는 '코드를 치는 법'이 아니라 이 '알고리즘'을 익히는 것만으로도 충분하다고 생각한다

-----------------------------------------------------------------------------------------------

1. CS에서 좋은 알고리즘의 기준이 되는 건 무엇일까?

 -> 정답은 '시간복잡도 - 문제를 해결하는게 걸리는 시간과 입력의 함수 관계'이다. 

대표적인 시간 복잡도는

1. O(1)

2. O(logN)

3. O(N)

4. O(NlogN)

5. O(N^2)

6. O(N^3)

7. O(2^N)

8. O(N!)

등이 있다. 

이것을 간단 그래프로 나타내면

(그래프 그리는 홈페이지 : https://www.desmos.com/calculator)

이런 형식이 되는데, 작은 값(n, 함수에선 x값)일 때는 큰 차이가 없어 보이지만, 

이게 굉장히 큰 값이 되면 결과적으로는 O(logN) 형태일 때가 가장 좋다는 것을 알 수 있다.

2. 알고리즘에서 시간복잡도는 어떻게 계산하는가?

 -> 표기법으로는 대문자 O(Big O Notation)를 사용한다. 평균적으로 입력 크기에 대해 시간이 얼마나 걸리는지 나타내는 방식인데 최악의 경우도 생각해야 하기 때문에 조금 어려운 개념일 수 있다. 보통 대학 학부에서 알고리즘 이론을 배운다 하면 다양한 알고리즘들 뿐만 아니라 시간복잡도 계산하는 방식을 배운다. (그리고 이건 대부분 수학적 귀납법/증명 을 통해 도출해내기 때문에 학부 시험 꽤나 어려웠다.) 그리고 결과값에서 상수는 값이 커져버리면 큰 의미가 없기 때문에 버린다.

CS 알고리즘에서, 시간복잡도는 어떤 의미를 갖는 것일까?

1. O(1) - 단순 계산

2. O(logN) - N개를 절반으로 계속해서 나눈 값

3. O(N) - 1중 for문

4. O(NlogN)

5. O(N^2) - 2중 for문

6. O(N^3) - 3중 for문

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

8. O(N!) - 크기가 n인 수열

등이 있다. 

3. 알고리즘 간소화 : 알고리즘은 출력하고자 하는 값과 입력으로 주어지는 값에 따라서 다양하게 변형될 수 있다. 입력 데이터가 가지는 특징을 이용하여 알고리즘을 간소할 수 있다.

• 정렬 여부

• 중복 존재 여부

• 입력 값의 범위와 크기

• 기타 수학적 특징 혹은 문제에 제시 된 규칙 등

또한, 우리가 원하는 출력 데이터를 구하기 위해 필요하지 않은 정보를 생략함으로서 기존의 알고리즘을 개선하거나 다른 알고리즘을 적용할 수 있게 된다.

예시>

• 구체적인 개수가 아닌 존재 여부만이 중요할 때
• 여러가지 정답 후보들 중 하나만이 필요할 때

4. 그렇다면, 알고리즘을 잘하려면 어떻게 해야할까?

 -> 정답은,  다양하게, 깊게, 오래 생각하는 것 그리고 문제를 많이 풀어보자 :)