[TIL] 05/13 항해99 5일 차 - 빅오(Big-O), 공부법, 문제풀이

들어가며

2주차 알고리즘/코테 주차가 시작되었다. 알고리즘은 처음 공부하는데 아니나 다를까 되게 어렵고 힘들다. 꼭 필요한 과정이라고 생각했기에 정규트랙 대신 심화트랙을 들어온 건데 1일차부터 내가 진짜 할 수 있을까라는 고민이 들기 시작했다. 빨리 잘 하고 싶은 마음이 커서 더 부담감이 크게 다가오는 것 같다.

 

알고리즘은 차근차근 단계별로 공부해야 한다고 생각했는데 단기간 안에 일정 수준만큼 끌어올려야 한다고 한 문제를 몇시간이고 붙잡고 있어서 12시간도 부족한 기분이어서 공부방식을 효율적으로 바꿔야 앞으로 3주를 버틸 수 있을 것 같아서 매니저님과 면담을 진행했고 나에게 맞는 공부방법을 어느정도 찾았기에 오늘의 TIL은 알고리즘 주차에서 제공해준 강의와 과제를 정리하고, 공부방식을 어떻게 가져갈 지 작성해보기로 한다!

---

알고리즘 개요

알고리즘이란?

수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다. 출처 - 위키백과

쉽게 말하면, 알고리즘이란 문제를 해결하는 절차나 방법이라고 할 수 있다.

 

점근표기법

알고리즘의 성능을 수학적으로 표기하는 방법. 알고리즘의 ‘효율성'을 평가하기 위해 사용한다.

시간 복잡도(실행 시간)와 공간 복잡도(실행 공간)으로 이루어진다.

 

대표적인 점근표기법 종류

• 빅오(Big-O) 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 나타낸다.
• 빅오메가(Big-Ω) 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 나타낸다.

빅오와 빅오메가 중 어떤 표기법을 많이 사용할까? 개발할 때 최선의 성능을 표기하는 건 의미가 없다. 개발은 최악의 성능을 최대한으로 끌어올려야하기 때문에 빅오(Big-O) 표기법을 주로 사용한다.

 

빅오 (Big-O)

출처 - https://www.bigocheatsheet.com/

빅오의 수학적 접근법은 가볍게 지나치도록 하자. 어차피 봐도 이해를 못한다. 나는 개념만 가지고 가는걸로!

 

위의 빅오 표기법의 그래프를 보면 어느게 가장 속도가 빠른지 한눈에 볼 수 있다. 그래프의 위(빨간부분)으로 갈 수록 효율이 적으며 아래(초록색부분)으로 갈 수록 효율이 좋아진다.

 

빅오 표기법 별 예제

빅오 표기법 별 예제는 알아만 두고 알고리즘 문제들을 공부하면서 깨달아가보자. 처음 공부하는 나는 예제만 본다고 아는게 아니니까!

• O(1) : 스택에서 Push, Pop
• O(log n) : 이진트리
• O(n) : for 문
• O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
• O(n^2) : 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
• O(2^n) : 피보나치 수열

 

나만의 알고리즘 공부방식

한 문제에 너무 많은 시간을 쏟다보니 너무 비효율적이라는 생각이 들어서 적절한 공부방법을 고민해보고 다음과 같이 정하였다.

 

1. 문제를 파악한다. 문제에서 요구하는게 무엇이고 입출력은 어떠한지 확인한다.
2. 문제를 어떻게 해결할 지 흐름을 그림과 글로 써본다. 코드를 글로 써보는 것도 좋음. 한 문제를 공부하는데 2시간이 넘어가지 않게 하기 위해서 이 과정에서 1시간이 넘어가면 과감하게 힌트를 본다.
3. 문제 풀이방식이 이해가 됐다면 직접 코드를 작성해본다. 이때, 나는 초보이기 때문에 시간 복잡도를 생각하지 않고 풀어본다. 어떻게든 결과가 제대로 출력된다면 OK. 이 과정 역시 30분이 넘어가면 과감하게 풀이를 본다.
4. 풀이 코드를 찬찬히 읽어보며 어떤 접근방식을 가져갔는 지, 어떤 함수와 라이브러리를 사용했는 지, 내가 생각한 방식과 어떻게 다른 지 등을 보면서 코드를 따라쳐본다. 이때, 무작정 따라치는게 아니라 흐름을 이해하면서 작성한다.
5. 풀이 코드를 보지 않고 코드를 작성해본다. 당연하게도, 초보자라면 높은 확률로 에러가 나오거나 틀린다. 한번에 해결한다면 좋겠지만... 다시 풀이 코드를 읽어본 후, 같은 과정을 반복한다. 이 과정을 통해 흐름을 이해하고, 손과 머리에 해결방법을 익힌다.
6. TIL에 처음 알게 된 개념들을 정리한다. 중요한 과정이니 가급적이면 생략하지 말자. 이거 미루다가 일요일이 사라질 수도 있다.
7. 다음 날, 시간이 허락하는 한 같은 문제들을 다시 한 번 풀어본다. 이 과정을 통해 지금까지의 과정이 단기기억에서 장기기억으로 넘어가게 된다.

 

물론 이 방식이 한번에 몸에 익숙해진다면 좋겠지만 오랜 기간이 걸릴 수도 있다. 최대한 이 방식을 지켜가면서 습관화 시켜보자!

 

문제풀이

[leetcode] 49. 그룹 애너그램 (Group Anagrams)

[leetcode] 49. 그룹 애너그램 (Group Anagrams)

나오는 개념 - collections.defaultdict()

 

 

[leetcode] 5. 가장 긴 팰린드롬 부분 문자열 (Longest Palindromic Substring)

[leetcode] 5. 가장 긴 팰린드롬 부분 문자열 (Longest Palindromic Substring)

나오는 개념 - 투포인터

 

 

[leetcode] 15. 세 수의 합 (3sum)

[leetcode] 15. 세 수의 합 (3sum)

나오는 개념 - 투포인터, 다중할당

 

 

[leetcode] 561. 배열 파티션 I (Array Partition I)

[leetcode] 561. 배열 파티션 I (Array Partition I)

 

---

마치며

사실 TIL이 13일인데 업로드 날짜가 15일인 이유는 공부하느라 미룬 TIL정리를 몰아서 했기 때문이다. 미루지 말고 제때제때 써야하는데 공부하는게 빡세서 자꾸 미루게된다... 시간 조절의 중요성을 다시한번 깨달은 날이다.

 

---

참고

빅오 표기법 (big-O notation) 이란