수포자의 코딩테스트 준비하기(feat.시간복잡도)

~글을 읽는 분들에게 전하는 혼잣말~

저는 수포자 입니다.ㅠㅠ 수학은 제가 가장 먼저 포기한 과목이었지만, 개발자가 된 후 이 선택이 이렇게 큰 후회로 남을 줄은 몰랐습니다. 중학교 2학년 때부터 수학을 멀리했던 저는 프론트엔드 개발자로 직종을 전환한 뒤에도 수학의 빈자리를 크게 느끼지 못했습니다. 실무에서 배워야 할 것들이 산더미였거든요.

하지만 이직 준비를 위해 [코딩테스트]라는 넘을 마주한 순간, 제게 부족했던 수학적 사고 능력을 뼈저리게 느끼게 되었습니다. 처음에는 코딩 문법과 자료구조 개념이 생소해서 그런가 보다 했지만, 반복되는 좌절 끝에 깨달았죠. '근본적인 해결책은 수학과 친해지는 것이다.'

그래서 수포자 스터디에 참여해 초등~고등학교를 아우르는 개념 보충용 수학 교재를 사서 풀어보고 있습니다. 비전공자라는 이유로 포기하지 않고 기초부터 차근차근 풀어나가는 지금, 조금씩 성장하고 있는 제 모습을 보며 희망을 느낍니다..(진짜?)

코딩테스트를 당당히 마주하기 위해 노력하는 과정을 공유하며, 지금까지 보충한 개념 및 앞으로 공부해야할 부분을 정리하고자 글을 작성합니다.

---

1. 시간복잡도와 Big-O 표기법

코딩테스트를 풀 때 3개짜리 테스트 케이스에서는 통과돼서 호기롭게 제출했는데, 시간 초과로 실패한 경험이 다들 있을 것이다.ㅋㅋㅠ 그 이유와 관련이 있는 항목이다.

 

시간복잡도는 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것이다. 즉, 알고리즘의 성능을 설명하는 것.

시간복잡도에서 중요하게 보는 것은 입력 값 n의 단위이다. 입력 값을 통한 연산 수행 시간의 상관관계를 나타내는 척도가 시간복잡도라고 할 수 있다.

n이 1일 때 O(1)

2n + 20 일 때 O(n)

3n^2 일 때 O(n^2)

 

여기서 등장한 O. 이게 Big-O 표기법이다. 불필요한 연산을 제거하고 알고리즘 분석을 쉽게 할 목적으로 사용된다.

Big-O 표기법은 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려한다.

입력 값의 변화에 따라 연산을 실행할 때, 최선보단 최악의 경우도 고려하여 대비하는 것이 바람직하니까...

 

위 사진은 많이 봤을 것이다. log도 모르는 나는 그냥 얼레벌레 그렇구나 하고 넘어갔었지ㅎㅎ

시간 복잡도가 빠른 순서대로 Big-O 표기법을 정리를 해보면,

 

O(1) 상수 시간 복잡도

입력 값이 증가하더라도 시간이 늘어나지 않는다. 다시 말해 입력 값의 크기와 관계없이, 즉시 출력 값을 얻어낼 수 있다는 의미이다.

예시 : 편의점 냉장고에서 내가 원하는 브랜드의 물병을 찾는 상황.

 

O(log n) 로그 복잡도 

문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦.

입력 데이터가 늘어나도 경우의 수가 절반씩 줄어드는 이진탐색 알고리즘이 로그 복잡도를 가지고 있다.

일상 예시 : 내가 이미 봤던 책에서 원하는 내용을 찾을 때, 대략적인 목차를 보고 필요없는 부분은 버리고 찾아내는 방식. 혹은 생각하는 숫자 맞추기 업앤다운 게임

 

O(n) 선형 복잡도

문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가지는 것. 즉, 입력 값이 커질수록 그에 비례해서 시간이 늘어난다.

리스트에서 값을 하나하나 비교하며 찾는 선형탐색이나 단일 반복문이 선형 복잡도를 가지고 있다.

일상 예시 : 택배가 모여있는 곳에서 내 택배를 찾을 때, 택배 수량에 비례하여 찾는 시간이 오래 걸리는 상황.

 

O(n log n) 선형 로그 복잡도

데이터가 증가할수록 n만큼 증가하는 선형적인 성질과, log n만큼 더 빠르게 증가하는 특성을 동시에 갖는다.

데이터를 선형적으로 다루되, 특정 방식으로 효율적으로 나누거나 병합하는 작업이 포함되는 병합정렬 이나 퀵정렬 알고리즘이 선형 로그 복잡도를 가지고 있다.

일상 예시 : 책이 수 백 권 있을 때 분류하는 방식. 분류별로 선별하고 다시 책의 제목별로 재 정리 하는 상황.

 

O(n^2) 2차 시간 복잡도

입력 값이 늘어날 수록 연산 시간이 n의 제곱수의 비율로 증가함. 입력 값이 1일 경우 1초 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 되었을 때를 뜻한다.

반복문을 최소 2번 수행하는 버블 정렬 이나 선택 정렬 알고리즘이 2차 시간 복잡도를 가지고 있다.

일상 예시 : 티셔츠와 바지의 조합. 티셔츠의 종류와 바지의 종류를 모두 조합해 입어보는 상황.

 

O(2^n) 지수 시간 복잡도

입력 값 n이 증가할 때, 수행 시간 또는 연산량이 2의 n제곱의 비율로 증가하는 알고리즘을 말한다.

선택의 수가 반복적으로 늘어나니 기하급수적 복잡도라고도 하며, Big-O 표기법 중 가장 느린 시간 복잡도이다.

모든 경우의 수를 시도해야 하는 완전탐색 알고리즘이 지수 시간 복잡도를 가지고 있다. 

일상 예시 : n자리 숫자로 이루어진 비밀번호를 해킹하려고 하는 상황.

---

어휴, 이것만 작성했는데도 지쳐버렸다. 아직 자료구조랑 알고리즘도 정리해야 하는데, 천천히 해보도록 할게요.....

사실 위의 내용들은 수도 없이 검색하고, 머릿속에 꾸역꾸역 넣으려고 노력했던 것들이다. 그런데도 명확하게 정의를 내리지 못했던 부분들이 많았다.

이번에는 일상 속 예시를 찾아보며 대입해보니, 흐릿했던 개념들이 그제서야 조금 선명해졌다. 역시 이론만 공부하는 것보다, 내가 이해할 수 있는 방식으로 다시 풀어보는 게 중요하다는 걸 느꼈다.

앞으로도 기억에 오래 남길 수 있도록, 이런 식으로 하나씩 풀어가며 공부해보려고 한다. 마주한 어려움들을 하나씩 넘어가다 보면, 언젠가는 코딩테스트도 당당히 풀어내는 날이 오겠지? 아자아자 화이팅...😔