섹션 0. 코딩테스트 준비하기

Do it! 알고리즘 코딩테스트

위의 책을 읽고 공부한 내용입니다. 

 

시간 복잡도

문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택

 

시간복잡도 표기법

C++에서는 일반적으로 1억번의 연산을 1초의 수행 시간으로 예측

 

시간복잡도 정의하는 유형은 3가지

 

빅 오메가 : 최선일때의 연산 횟수를 표현

빅 세타 : 보통일때의 연산 횟수를 표현

빅 오 : 최악일때의 연산 횟술르 나타낸 표현

 

코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다.

다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하기 떄문이다.

알고리즘 선택의 기준으로 사용할 수 있다.

ex) 버블 정렬 O(n^2), 병합 정렬 O(nlogn)

 

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 n 값에 데이터의 최대 크기를 대입하여 도출

 

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로 사용할 수 있다. 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.

 

시간 복잡도 도출 기준

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

요약

1. 시간 복잡도는 최악의 케이스 빅오를 사용
2. 시간 복잡도 도출할떄
   1. 상수는 무시
   2. 가장 많이 중첩된 반복문을 기준
3. 시간복잡도 사용할때
   1. 알고리즘 선택기준
   2. 시간초과시 내 비효율적 코드가 어딘지 판단할때 사용

디버깅

코드의 논리 오류를 잡기 위한 가장 뛰어난 오류 탐색 방법, 디버깅

 

프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅

문법 오류는 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않는다.

논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생

 

ex) index 범위 1개 차이, 예외 처리 하나 빠트림

 

코딩 테스트에서 필요한 기술이고, 그냥 알아 두어야하는것이 아닌 반드시 해야 하는 과정

1. 디버깅을 함으로써 컴퓨터 프로세스가 어떻게 동작 되는지 알게됨
2. 알고리즘의 동작원리를 이해하는데 도움이 됨

VS 기준 디버깅 방법

1. 디버깅하고자 하는 줄에 중단점을 설정, 중단점을 여러개 설정 가능
2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행 가능, 추적할 변수 값도 지정 가능
3. 변수 값 이외에도 원하는 수식을 입력해 논리 오류 파악 가능

변수 값 추적은 VS의 로컬(Local), 자동(Auto), 조사식(Watch) 창을 활용

1. 변수 초기화 로직을 놓치기 쉽다. ex) 변수 재사용 전 초기화 확인
2. 반복문에서 인덱스 범위 지정 오류 ex) 0빼기, 비교연산자 실수
3. 잘못된 변수 사용 오류 ex)코딩을 하는 중 변수 혼동
4. 자료형 범위 오류 ex) long long

tip) 음수가 나올 수 없는 경우 음수가 나오면 → 자료형 범위 확인