책 정리 내용(이것이 코딩 테스트다)

코딩 테스트 준비를 돕는 다양한 서비스

알고리즘 공부할 때

• Part 02를 이해한다.
• Part 03 관련 문제를 푼다.
• 백준 온라인 저지에서 관련 문제 50개를 푼다.

 

백준 온라인 저지 : 삼성 SW 역량테스트 대비 문제집 제공

프로그래머스 : 카카오 공채 문제집 제공

삼성전자 : DFS/BFS를 활용해야 하는 탐색과 시뮬레이션 문제 유형을 자주 출제한다. (상시 SW 역량테스트 A형 문제와 유사하게 출제 된다.)

 

복잡도

알고리즘의 성능을 나타내는 척도

시간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
• 알고리즘을 위해 필요한 연산의 횟수
• 빅오 표기법을 사용한다. (가장 빠르게 증가하는 항만을 고려하는 표기법)

int arr[5] = [3,5,1,2,4];
int summary = 0;

// 모든 데이터를 하나씩 확인하며 합계를 계산
for(int i=0;i<5;i++){
    summary += i;
}

// 결과 출력
printf("%d",summary);

N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램이다.
위 예에서는 5개의 데이터를 받아 차례로 5회 더해준다.
이때 연산 횟수는 N에 비례하는 것을 알 수 있다.
시간복잡도 : O(N)이다.

int a = 5;
int b = 7;
printf("%d",a+b);

a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 이 소스코드의 연산 횟수는 1이다.
시간복잡도 : O(1)이다.

int arr[5] = [3,5,1,2,4];
int summary = 0;

// 모든 데이터를 하나씩 확인하며 합계를 계산
for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
        summary += i*j;
    }
    
}

// 결과 출력
printf("%d",summary);

데이터의 개수가 N개일 때, O(N^2)의 시간 복잡도를 가진다.
소스코드가 내부적으로 다른 메서드를 호출한다면 내부 메서드의 시간복잡도까지 고려해야 한다.

• 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하다.

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

• 시간 복잡도에서 연산은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다.
• 이차 시간, 삼차 시간 : 다항 시간에 해당 된다.
• 연산 : 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다.
• 범위
  • N의 범위가 500인 경우 : 시간 복잡도 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 2,000인 경우 : 시간 복잡도 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 100,000인 경우 : 시간 복잡도 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 10,000,000인 경우 : 시간 복잡도 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

공간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
• 알고리즘을 위해 필요한 메모리의 양
• 빅오 표기법을 이용한다.
• int a[2000][2000] 16KB
  • 만약 리스트의 크기가 1,000만 단위 이상이라면 자신의 알고리즘을 잘못 설계한 것이 아닌지 고민해봐야 한다.

 

알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.

 

 

최신 출제 경향과 준비 방향

코딩 테스트에서는 주로 기초 알고리즘에 기반하는 문제가 출제된다.

가장 출제 빈도가 높은 문제 : 그리디, 구현, DFS/BFS를 활용한 탐색 문제이다.

출제되더라도 난이도가 높지 않은 경향이 있는 문제 : 다이나믹 프로그래밍, 그래프 이론 문제

 

일반적으로 알고리즘 코딩 테스트는 2 ~ 5 시간 가량의 제한된 시험 시간에 8개 이하의 문제를 푸는 형태로 출제된다.

 

 

---

참고 자료

• 이것이 취업을 위한 코딩 테스트다 with 파이썬