Do it! 알고리즘 코딩테스트 파이썬편 교재와
하루코딩 님의 Do it! 알고리즘 코딩테스트 유튜브 강의를 바탕으로 정리한 내용입니다.
유튜브: https://www.youtube.com/@codingtest
1. 시간복잡도
시간복잡도는 알고리즘 선택 기준이 될 수 잇음
1️⃣ 시간복잡도란
주어진 문제를 해결하기 위한 연산 횟수
2️⃣ 시간 복잡도 유형
빅오메가: 최선일 때의 연산 횟수를 나타낸 표기법
빅세타: 보통일 때의 연산 횟수를 나타낸 표기법
빅오: 최악일 대의 연산 횟수를 나타낸 표기법
코딩 테스트에서는 빅오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.
즉, 빅오 상황에서의 연산횟수를 기준으로 알고리즘 적합도를 판별할 줄 알아야 한다.
(연산횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출)
3️⃣ 시간복잡도를 바탕으로 코드 로직 개선하기
시간 복잡도 도출 기준
1) 상수는 시간 복잡도 계산에서 제외한다. (N 이나 3N 정도는 같은 시간 복잡도로 간주한다.)
2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
즉, 중첩된 부분을 어떻게 개선할 수 있을지 고민하는 것이 핵심일 수 있다.
2. 디버깅
오류는 문법오류와 논리 오류가 존재
문법오류는 컴파일러가 잡아주기 때문에 우리가 신경써야할 것은 바로 논리오류이다.
이러한 논리오류를 가장 뛰어나게 탐색할 수 있는 방법이 바로 디버깅이다.
디버깅: 프로그램에서 발생하는 논리 오류를 찾아 바로잡는 과정
1️⃣ 디버깅 하는 방법
코드에서 디버깅하고자 하는 줄에 중단점을 설정하고 IDE의 디버깅 기능을 실행해 진행하면 된다.
1) 코드에서 디버깅하고자 하는 줄에 중단점을 설정한다. 이때 중단점은 여러개 설정 가능
2) IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있다.
3) 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있다.
pycharm의 variables 기능 활용
2️⃣ 논리 오류의 유형 4가지
1) 변수 초기화 로직 누락
2) 반복문에서 인덱스 범위 지정 오류
3) 잘못된 변수 사용 오류
4) 파이썬 자동 형 변환 조심
댓글