코딩 테스트 요약본

코딩 테스트 준비하면서 핵심 요약

 

파이썬으로 준비합니다.

 

많은 부분을 나동빈님 저자,

이것이 취업을 위한 코딩 테스트다 with Python 를 참고하였습니다.

 

외워야할 것 들

 

import sys

input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit( LIMIT )

from collections import deque
from itertools import combinations, permutations
import math

math.ceil()
math.floor( NUMBER + 0.5 ) # 반올림

import heapq

q = []
heapq.heappush(q, NUMBER)
n = heapq.heappop(q)

arr = ARRAY
heapq.heapify(arr)

INF = int(1e9)

문자열.isdigit()

 

문제를 보면서 확인할 것들

 

입력의 크기

어떤 유형의 알고리즘

입력의 경계에서 생각

최악의 상황

가장 간단하게 해결해보고 개선

 

본격적인 알고리즘

 

그리디

당장 좋은 것을 골라서 해결

위 방법으로 실행하여도 정답을 보장할 수 있도록 검증하여야 함

문제를 해결할 수 있는 가장 좋은 방법이 아니더라도 개선하면서 해결할 수 있다.

 

구현

시뮬레이션

dx, dy 혹은 steps

DFS, BFS와 같은 완전 탐색과 다른 동작의 시뮬레이션 문제일 수 있다.

 

DFS, BFS

노드 관계를 표현하는 방법: 행렬, 리스트

방문한 노드를 따로 저장한다.

 

DFS

스택으로 구현

스택에 추가되는 경우: 현재 노드에서 방문하지 않은 노드 중에 다음 방문예정인 노드

스택에서 빠지는 경우: 주변 노드들이 다 방문했을 때

 

BFS

큐로 구현

큐에 추가되는 경우: 현재 노드에서 방문하지 않은 노드 전부

큐에서 빠지는 경우: 방문하면서 빠진다

 

정렬

선택: 순서대로 작은 원소를 찾아서 앞으로 배치

삽입: 인덱스를 앞에서부터 하나씩 옮기면서 정렬한다. 앞부분은 정렬이 되채로 유지되게 하고 인덱스가 가리키는 원소가 정렬을 유지하게끔 삽입한다.

퀵: pivot을 이용하여 좌, 우를 pivot보다 작은 원소들 그리고 큰 원소들로 정렬한다. 분할 정복한다.

머지: 퀵과 유사하나 분할 정복 후 다시 합치는 과정이 있고 최악의 경우에도 NlogN을 보장

버블: 2개씩 비교하며 자리를 바꾸는 것을 반복한다.

 

이진탐색

정렬을 전제로 한다.

입력크기가 상당히 크다면(10억 이상) 생각해본다.

 

DP

메모리를 더 써서 빠르게 해결하는 방법

큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 정답이 큰 문제에서도 동일할 경우에 사용한다.

DP의 핵심은 점화식으로 표현하는 것이다.

수학처럼 문제에서 요구하는 내용을 점화식으로 표현하고 도식화하여 직접 실행해본다.

바텀업과 탑다운 방식이 있고 탑다운 방식은 재귀적으로, 바텀업은 반복적으로 해결하는 것이다.