[자료구조, 알고리즘 스터디] 코딩 테스트 준비하기

1. 어떤 알고리즘으로 풀어야 할까?

1) 시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는

주어진 문제를 해결하기 위한 연산 횟수를 말한다

 

일반적으로 수행 시간은 1억번의 연산을 1초의 시간으로 간준하여 예측한다

 

시간 복잡도 유형

- 빅 오메가 : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법

- 빅 세터 : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법

- 빅 오 : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

코딩 테스트에서는 빅 오 표기법을 기준으로 수행 시간을 계산하는게 좋다

 

실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다

 

작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만

합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다

 

 

2) 시간 복잡도 활용하기

예를들어 버블 정렬과 병합 정렬의 시간복잡도를

각각 O(n^2), O(nlogn) 이라는것을 알고있다고 해보자

 

이때 시간 제한이 2초이고 절대값이 1,000,000 보다 작거나 같은 정수

라는 문제가 주어졌다고 했을때

 

시간 제한이 2초이니까 연산 횟수가 2억번 이하인 알고리즘을 찾아야한다

 

연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

 

버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 > 200,000,000

 

병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000

 

이로써 병합 정렬이 더 적합하다는것을 알 수 있다

 

2. 코드의 논리 오류를 어떻게 잡을까?

1) 디버깅은 왜 중요할까?

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

 

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

 

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

 

디버깅 하는방법

1) 코드에서 디버깅 하고자 하는 중에 중단점을 설정한다

중단점은 여러개 설정할 수 있다

 

2) IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나

다음 중단점 까지 실행할 수 있다

이 과정에서 추적할 변숫값도 지정할 수 있다

이 방법으로 변숫값이 자신이 의도한 대로 바뀌는지 파악한다

 

3) 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있다

 

볏숫값을 추적하는 방법 : 이클립스의 Expressions 기능을 활용한다

 

 

2) 디버깅 활용 사례 살펴보기

오류 1. 변수 초기화 오류

변수 초기화 로직에서 초기화를 제대로 하지 않은 경우

 

오류 2. 반복문에서 인덱스 범위 지정 오류

반복문에서 인덱스 범위를 잘못 지정한 경우

 

오류 3. 잘못된 변수 사용 오류

출력 부분이나 로직 안에서 사용해야 하는 변수를 다른 변수와 혼동하여 잘못 사용하는 경우

 

오류 4. 자료형 범위 오류

데이터 계산 도중 계산된 값을 변수에 저장할 때 변수에 지정한 자료형 범위를 넘어가는 경우

 

Tip. 자료형은 처음부터 long 형으로 선언하자

코딩 테스트에서 계산되는 값들은 long형 안에서 표현할 수 있어

변수를 선언할 때는 처음부터 long형으로 선언하기를 추천한다

 

참고

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