2023학년도 2학기 대학교에서 파이썬 프로그래밍 수업을 듣고, 어느 정도의 이론은 차있으나 실제 문제나 프로그램의 코드를 짜려고 하면 겁부터 난다. 어떤 문법과 알고리즘을 사용해야 하는지, 왜 사용하는지 나를 포함하여 코딩 입문을 했는데 코딩을 못하는 사람이라면 다 공감할 것 같다. 우연히 파이썬을 Do it! 교재로 시작하였는데 너무 좋았어서 이번 겨울 방학때 Do it! 알고리즘 코딩 테스트 <파이썬 편> 으로 공부를 하고, 여기에 기록해 볼 예정이다.
교재 구매는 Do it! 알고리즘 코딩 테스트: 파이썬 편 | 김종관 - 교보문고 (kyobobook.co.kr) 여기서 하였고
이렇게 생긴 책이다. 하얗게 생겨서 파란색과 빨간색이 들어간 디자인도 참 마음에 든다! 헷갈리는 것들이 있으면 몇몇의 책은 저렇게 유튜브로 지원도 해준다. 링크는 옆에 같이 걸어둘테니 참고해보면 좋을 것 같다!
알고리즘 코딩테스트 문제풀이 강의 - 1 숫자의 합 구하기 (백준 11720) (youtube.com)
우선, 설명에 앞서 꾸준하게 필자가 티스토리를 작성하려면 디자인과 필력에 스트레스를 받지 않고 써야 꾸준하게 쓸 것 같아 양해를 부탁드린다는 점...^^ (단순 기록용)
p.15
코딩 테스트에서 매우 중요한 부분은 "시간 복잡도" 와 "디버깅"
p. 16
어떤 알고리즘으로 풀어야 할까? - 알고리즘 선택의 기준이 되는 시간 복잡도
p. 17, 18
01-1 <시간 복잡도 표기법 알아보기>
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
시간 복잡도 유형
- 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
- 빅-세타 : 보통일 때의 연산 횟수를 나타낸 표기법
- 빅-오 : 최악일 때의 연산 횟수를 나타낸 표기법
코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.
빅-오 표기법 관련 사이트 : [자료구조] 빅오 표기법(Big-O notation)이란? (tistory.com)
[자료구조] 빅오 표기법(Big-O notation)이란?
빅 오 표기법(Big-O notation)의 정의Big-O(또는 Big-Oh) notation은 알고리즘의 시간 복잡도를 나타내는 표기법이며, O(f(n))으로 나타낸다. 알고리즘의 시간 복잡도알고리즘의 복잡도를 판단하는 척도로는
holika.tistory.com
p. 19, 20, 21, 22
01-2 시간 복잡도 활용하기
예시로, 백준 온라인 2750번 문제에 어떤 정렬 알고리즘을 사용하여 문제를 푸는가?
정렬에는 여러 정렬들이 있다. 버블 정렬의 시간 복잡도 O(n^2), 병합 정렬의 시간 복잡도 O(nlogn), ...
근데 문제에 데이터의 크기가 주어져 있고 이것을 n에 대입해보면 시간 제한에 알맞는 정렬의 시간 복잡도를 선택할 수 있다.
연산 횟수 계산 방법
- 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 생각한다.
- 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출
그럼 이 문제에 알맞는 정렬은 '병합 정렬' 인 것을 알 수 있다.
이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다. 즉, 데이터의 크기(N)를 단서로 사용해야 알고리즘을 추측해 볼 수 있다.
시간 복잡도를 바탕으로 코드 로직 계산하기 !
시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.
시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외한다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
p. 23
02 코드의 논리 오류를 어떻게 잡을까? - 가장 뛰어난 오류 탐색 방법, 디버깅
p. 24, 25, 26, 27, 28, 29
디버깅 : 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정
디버깅 하는 법 : 코드에서 디버깅하고자 하는 줄에 중단점 (BREAK POINT) 을 설정하고, IDE의 디버깅 기능을 실행해 진행하면 된다.
디버깅 방법
- 코드에서 디버깅하고자 하는 줄에 중단점을 설정한다. 이때 중단점은 여러 개 설정할 수 있다.
- IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서 추적할 변숫값도 지정할 수 있다. 이 방법으로 변숫값이 자신이 의도한 대로 바뀌는 지 파악한다.
- 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있다.
오류 예시
1. 변수 초기화 오류 찾아보기
2. 반복문에서 인덱스 범위 지정 오류 찾아보기
- 배열 인덱스가 0부터 시작한다는 걸 잊지 말자
- 반복문을 N까지 반복을 해야하는 것인지, N-1까지 반복을 해야하는 것인지 꼭 확인 하자
3. 잘못된 변수 사용 오류 찾아보기
4. 파이썬 자동 형 변환 조심하기
- 파이썬에서의 나누기는 / 연산자와 // 연산자 2가지 이다.
- / 연산자 : 나눗셈을 한 결괏값을 float형으로 출력하며 소수점의 결과까지 보여준다.
- // 연산자 : 나눗셈을 한 결괏값을 int형으로 출력하며 몫의 결과만 보여준다.
- % 연산자 : 나눗셈을 한 후 나눈 나머지 값을 보여준다.