프로그래머스, 백준에서 처음보는 유형의 문제에 해답이 일일이 뭔지 찾아보며 공부하셨습니까,

네, 빡대가리였던 저는 그랬습니다.

여태까지 구현하고 문제풀기만 바빴지 내가 지금 뭘 어떻게 풀고있는지는 공부해본적이 없습니다.

알고리즘 그게 뭔데, 한 번 알아봅시다.

👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 시간복잡도

시간복잡도는 아래 세가지 방법으로 표기합니다.

• 빅-오메가(Ω(n)): best case의 연산 횟수
• 빅-세타(Θ(n)): average case의 연산 횟수
• 빅-오(O(n)): worst case의 연산 횟수

그런데, 세 가지 중 우리가 신경써야할 것은 빅-오(O)입니다.

아래의 그래프는 빅-오 표기법으로 표현한 시간복잡도 그래프입니다. 각각의 시간복잡도는 데이터의 크기가 증가함에 따라 성능이 천차만별로 달라집니다.

가장 빠른 경우든 평균의 경우든 고려하는 것은 좋지만,
결국 최악의 경우 수행시간이 무한히 늘어나는 것을 가장 우선으로 경계해야 합니다.

1-1. 코드 로직 개선

시간 복잡도에 대한 이해를 가지고 있다면, 그리고 시간복잡도를 도출해낼 수 있다면, 앞으로 비효율적인 로직을 개선하여 코드를 짤 수 있게됩니다.

시간복잡도를 도출하는 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

2. 디버깅

문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅이라고 합니다.

다행히 문법 오류는 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않지만,
논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며, 다양한 형태로 발생합니다.

1. 반례, 예외처리: 예외인 경우를 찾지 못해 올바른 처리 방식을 구현하지 않았을 경우
2. 변수 오류: 변수의 혼동 등으로 변수 선언 또는 변수 초기화가 제대로 되지 않았을 경우
3. 반복문 범위 지정 오류: 반복문에서 비교연산자를 잘못 사용하는 경우 등
4. 형 변환 오류: 문제에서 요구하는 값의 형태(float, int, str...)를 맞추지 못하였을 경우

---

*파이썬에서는 배열과 리스트를 구분하지 않는다.

일반적으로 CS에서는 배열과 리스트가 명확하게 구분되는 자료구조이지만,
파이썬의 리스트는 리스트의 특징은 물론, 배열의 특징까지도 모두 가지도록 구현되었습니다.

이 때문에 코딩테스트에서 이러한 파이썬의 구현 특징을 잘 활용하면 다른 언어보다 조금 더 쉽게 정답 코드를 구현할 수 있습니다.