26일차: 알고리즘(Algorithm)과 시간복잡도(Time Complexity)

❯ 알고리즘(Algorithm)

알고리즘이란, 문제를 해결하는 최선의 선택을 구하는 것을 의미한다.

이를 위해 문제를 정확하게 이해하고, 어떻게 해결할지 전략을 수립하고, 수립한 전략을 실제 코드로 작성할 수 있어야한다.

알고리즘 문제 풀이를 위해서는 의사코드(PseudoCode)를 잘 작성하는것이 중요하다.

자연어(혹은 프로그램언어)를 사용하여 프로그램 작동 논리를 작성하게된다.

의사코드를 구체적이고 논리적으로 작성해야 코드 작성시 시간이 단축되고 디버깅이 용이해진다.

❯ 시간 복잡도(Time Complexity)

이때까지 문제 풀이 혹은 기능 구현만 신경써서 연산 수행시간은 전혀 고려하지 않았다.

시간 복잡도란, 프로그램 입력값과 연산 수행시간의 상관관계를 나타내는 척도로 입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마나 걸리는지를 나타내는 수치이다.

따라서 효율적인 알고리즘이란, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구현하는 것을 말한다.

시간 복잡도 표현 방법

크게 세가지로 나뉜다.

• Big-O : 최악의 시간까지 고려한 것. (이 정도 시간까지 걸릴 수 있다.)
• Big-Ω : 최선의 시간을 고려한 것. (최소 이 정도 시간이 걸린다.)
• Big-𝜃 :  평균(중간)의 시간을 고려한 것. (보통 이 정도 시간이 걸린다.)

따라서, 최악의 경우를 고려해 대비하는것이 바람직하므로 보통은 Big-O 방식을 사용한다.

위의 표는 Big-O 표기법에 따른 시간을 나타내는 그래프와 자료구조/행위별 시간을 나타낸 표이다.

• O(1) : 입력값에 관계 없이 일정한 시간이 소요되는 알고리즘 ex. 배열에서 특정 인덱스를 갖는 값 찾기
• O(n) : 입력값이 증감함에 따라 시간 또한 같은 비율로 증가하는것.
• O(log n) : O(1) 다음으로 빠른 복잡도. ex. BST 탐색
• O(n^2) : 입력값이 증가할 때 시간은 n^2비율로 증가하는것 ex. 이중 for문
• O(2^n) : 가장 느린 시간 복잡도. ex. 재귀로 구현한 피보나치 수열

---

이때까지는 코드 작성과 문법 위주의 학습이 진행됐었는데, 학습을 진행하면서 점점 CS 기초 개념도 필요하다는 느낌이 든다.

아직은 진도를 따라가기에 바빠서 보충학습을 하기는 어려운데, 최대한 시간을 내서 CS 도 학습할 수 있도록 해야겠다