[코딩테스트] 코딩테스트 및 관련 알고리즘의 개요

바쁜 일정에 공부를 하다보면 포스팅까지 옮겨 적지 않고 혼자만 공부하고 보관하게 되는 경우가 많은 듯 하다.

그 점이 아쉬워서, 조금 정리가 잘 되지 않더라도 블로그에 포스팅을 다시 해 보기로 했다.

 

최근에는 동빈나님의 이것이 코딩 테스트다, 일명 이코테 유튜브를 보면서 코딩테스트 준비를 시작해보기로 했다.

코딩테스트란 기업에서 문제 해결 역량을 평가하기 위해 활용하는 시험으로, 여러 온라인 저지 사이트가 있지만

나는 컴퓨터공학 지식이 없기 때문에 우선 프로그래머스의 레벨0부터 차근차근 문제를 풀어볼 생각이다.

 

알고리즘 문제를 위한 알고리즘 코드를 깃헙 등에 많이 올리기도 하지만,

나는 개인적으로도 다시 보고 싶고, 기초 알고리즘 지식도 정리를 하고 싶어 블로그에 업로드를 해 보기로 했다.

먼저 코딩테스트 및 관련 알고리즘의 개요에 대해서 짚고 넘어가고자 한다.

 

가장 출제 빈도가 높은 알고리즘 유형

-그리디

-구현

-DFS/BFS를 활용한 탐색

- 그 외에도 정렬 알고리즘, 이진 탐색, 다이나믹 프로그래밍, 최단 경로 알고리즘, 그래프 이론 등도 출제됨.

 

알고리즘 성능 평가

복잡도 : 알고리즘의 성능을 나타내는 척도.

시간 복잡도 : 특정 크기 입력에 대한 알고리즘의 수행 시간 분석

공간 복잡도 : 특정 크기 입력에 대한 알고리즘의 메모리 사용량 분석

*복잡도가 낮을수록 좋은 알고리즘이다.

 

코드가 복잡하다는 것과는 다르다. 성능적인 측면에서의 복잡도를 의미한다.

 

 

빅오 표기법

가장 빠르게 증가하는 항만을 고려하는 표기법으로, 함수의 상한(차수가 가장 큰 항)만을 나타낸다.

좋은 것부터 나쁜 것까지 나열하자면

O(1) : 상수 시간

O(logN) : 로그 시간

O(N) : 선형 시간

O(NlogN) : 로그 선형 시간

O(N²) : 이차 시간

O(N³) : 삼차 시간

O(2ⁿ) : 지수 시간

 

1. 시간 복잡도 계산해보기

array=[3,5,1,2,4]

summary =0

for x in array:

    summary +=x

print(summary) 

 

#모든 데이터를 하나씩 확인하며 합계를 계산하므로, 수행시간은 데이터의 개수 N에 비례한다.

시간 복잡도 : 선형 시간 O(N)

 

2. 2중 반복문 이용시, 보통 N제곱의 시간이 소요되지만 항상 그런 것은 아니다.

for i in array:

    for j in array:

        temp = i*j

        print(temp)

 

연산 횟수가 5억을 넘어감.

1초에 2천만번의 연산만 처리할 수 있다고 생각하고, 또 채점 컴퓨터 성능에 따라 다르므로 유의하라.

 

문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)

시간제한이 1초인 문제를 만났을 때, 시간 복잡도가 각각 아래와 같은 알고리즘을 설계해야 문제를 풀 수 있다.

N의 범위가 500인 경우: 시간 복잡도가 O(N³) 

N의 범위가 2,000 : O(N²)

N의 범위가 100,000 : O(NlogN)

N의 범위가 10,000,000 :O(N)

 

알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

핵심 아이디어를 잘 캐치한다면 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제하므로, 스스로에게 확신을 가지고 생각을 충분히 한 다음 소스를 짜기

 

*수행시간 측정 코드도 문제를 푸는동안 활용해보자.

import time

start_time = time.time()

end_time = time.time()

print("time:",end_time - start_time)