이것이 취업을 위한 코딩테스트다 With 파이썬
(코드는 Swift 기준으로 작성함)
let array = [1,2,3,4,5] // 5개의 데이터 (N=5)
var summary = 0
for x in array{
summary += x
}
print(summary) // 15
let a = 5
let b = 7
print(a+b) // 12
a+b
한번만 이뤄짐let array = [3,5,1,2,4]
var temp: Int
for i in array {
for j in array{
temp = i*j
print(temp)
}
}
Big-O 표기법 | 명칭 |
---|---|
O(1) | 상수 시간 |
O(㏒𝑵) | 로그 시간 |
O(𝑵) | 선형 시간 |
O(𝑵㏒𝑵) | 선형 시간 |
O(𝑵²) | 이차 시간 |
O(𝑵³) | 삼차 시간 |
O(𝟤ⁿ) | 지수 시간 |
시간 복잡도 알고리즘 | N=1,000 기준 연산 횟수 |
---|---|
O(𝑵) | 1,000 |
O(𝑵㏒𝑵) | 10,000 |
O(𝑵²) | 1,000,000 |
O(𝑵³) | 1,000,000,000 |
능숙한 숙련자들은 문제를 해석하기 전 조건(N의 범위)을 먼저 보고 사용할 알고리즘을 결정하기도 함
N의 범위가 클수록 알고리즘은 빠른 알고리즘으로 설계한다
문제의 조건을 확인한 뒤 사용할 수 있는 알고리즘을 좁혀 나가는 전략 예시
<조건(𝑵의 범위)별 설계 알고리즘 예시>
𝑵의 범위 | 설계할 알고리즘 |
---|---|
500 | O(𝑵³) |
2,000 | O(𝑵²) |
100,000 | O(𝑵㏒𝑵) |
10,000,000 | O(𝑵) |
시간 복잡도와 똑같이 Big-O 표기법을 이용
시간 복잡도가 1초라는 절대적 제한이 있는 것 처럼, 메모리는 MB 단위로 사용량 제한
예시) 시간 제한 1초, 메모리 제한 128MB
대부분 코딩테스트에서는 메모리 사용량을 128~512MB로 제한
⇒ 일반적으로 데이터의 개수가 1,000만 단위가 넘어가지 않도록 설계해야 함
let startTime = CFAbsoluteTimeGetCurrent() // 측정 시작
/* 코드 구현 */
let endTime = CFAbsoluteTimeGetCurrent() // 측정 종료
let durationTime = endTime - startTime // 경과 시간
print("경과 시간: \(durationTime)") // 경과 시간 출력
import Foundation
// 배열에 10,000개의 정수 삽입
var array = [Int]()
for _ in 0..<10000 {
array.append(Int.random(in: 1...100)) // 1에서 100까지 무작위 정수
}
// 선택 정렬 프로그램 성능 측정
var start_time = CFAbsoluteTimeGetCurrent()
// 선택 정렬 실행
for i in 0..<array.count {
var min_index = i // 가장 작은 원소 인덱스
for j in i+1..<array.count {
if array[min_index] > array[j] {
min_index = j
}
}
var temp: Int
temp = array[min_index]
array[min_index] = array[i]
array[i] = temp
}
var end_time = CFAbsoluteTimeGetCurrent()
print("선택 정렬 성능 측정: \(end_time-start_time)")
// 기본 정렬 위해서 배열 초기화
array = [Int]()
for _ in 0..<10000 {
array.append(Int.random(in: 1...100)) // 1에서 100까지 무작위 정수
}
// 기존 정렬 라이브러리 성능 측정
start_time = CFAbsoluteTimeGetCurrent()
// 기본 정렬 라이브러리 실행
array.sort()
end_time = CFAbsoluteTimeGetCurrent()
print("기존 정렬 성능 측정: \(end_time-start_time)")
선택 정렬 성능 측정: 15.769272923469543
기존 정렬 성능 측정: 0.036099910736083984
=> 선택 정렬은 시간이 15초가 넘게 걸리고, 기본 정렬 라이브러리는 1초도 걸리지 않을 만큼 짧은 시간이 걸림