이것이 코딩테스트다

1

그리디 알고리즘

• 현재 상황에서 지금 단장 좋은 것만 고르는 방법

• 일반적인 상황에서 그리지 알고리즘은 최적의 해를 보장할 수 없을 떄가 많은데, 코테에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 함ㄴ

크루스칼, 다이스크라

<문제> 거스름 돈

<뮨재> 1이 될때까지

구현

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

• 구현 유형의 에시

  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

  • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

  • 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제

  • 적절한 라이브러리를 찾아서 사용해야 하는 문제

• 요구사항대로 충실히 구현하면 되는 문제

<문제> 시각

• 완전 탐색 (BRute Forcing) : 가능한 경우의 수를 모두 검사해보는 탐색 방법

<문제> 왕실의 나이트

• 시뮬레이션

• 2차원 리스트, 2차원 배열

<문제> 문자열 재정렬

• 문자열이 입력되었을 때 문자를 하나씩 확인

  • 숫자인 경우 따로 합계를 계산

  • 알파벳의 경우 별도의 리스트에 저장

• 결과적으로 리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력

2

탐색(Search)

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있음

스택

• LIFO

큐

• FIFO

재귀 함수

• 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수

DFS (Depth-First Search)

• 깊이 우선 탐색

• DFS는 스택 자료구조(혹은 재귀 함수)를 이용함

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함

  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

BFS(Breadth-First Search)

• 너비 우선 탐색

• BFS는 큐 자료구조를 이용함

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함

  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

<문제> 음료수 얼려 머긱

• 연결 요소 찾기

<문제> 미로 탈출

3

정렬 알고리즘

• 정렬이란 데이터르 특정한 기준에 따라 순서대로 나열하는 것

• 일밙거으로 문제 상황에 따라 적적ㄹ한 정렬 알고리즘이 공식처럼 사용

선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

• 선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 선택정렬보다 효율적임

• 시간복잡도

  • O(n^2)

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

• 가장 기본적인 퀵 정렬은 첫 번째 데이터(피벗)를 기준 데이터로 설정

• 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할이라고 함(Divide)

• 시간복잡도

  • O(NlogN)

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

정렬 알고리즘 비교

정렬 알고리즘	평균 시간 복잡도	특징	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 경우 가장 빠름
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합, 충분히 빠름
계수 정렬	O(N + K)	O(N + K)	데이터의 크기가 한정되어 있는 경우에만 사용 가능, 매우 빠름

<문제> 두 배열의 원소 교체

4

이진 탐색 알고리즘

순차 탐색

• 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진 탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반식 좁혀가며 데이터르 ㄹ탐색

• 파라메트릭 서치 : 최적화 문제를 결정 문제(’예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법

<문제> 떡볶이 떡 만들기

5

다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함

• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됨

• 다이나믹 프로그래밍은 동적 계획법이라고도 부름

  • 일반적인 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법

  • 반면 다이나믹 프로그래밍에서 ‘다이나믹’은 별다른 의미 없이 사용된 단어

다이나믹 프로그래밍의 조건

1. 최적 부분 구조(Optimal Substructure)

   1. 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

2. 중복되는 부분 문제(Overlapping Subproblem)

   1. 동일한 작은 문제를 반복적으로 해결

상향식 (보텀업)

• 아래쪽에서 부터 작은 문제를 하나씩 해결하여 먼저 해결한 문제의 값을 활용하여, 그 다음 문제도 해결 (반복문)

• 결과 저장용 리스트는 DP테이블이라고 부름

하향식 (탑다운)

• 구현과정에서 재귀함수를 이용, 큰 문제를 해결하기 위하여 작은 문제를 재귀적으로 호출하여, 작은 문제가 해결되었을때 큰 문제가 해결됨

• 메모이제이션

  • 다이나믹 프로그래밍을 구현하는 방법 중 하나

  • 한 번 계산한 결과를 메모리 공간에 메모하는 기법 (이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미)

    • 같은 문제를 다시 호출하면 메모햇던 결과를 그대로 가져옴

    • 값을 기록해 놓는다는 점에서 캐싱이라고도 함

• 다이나믹 프로그래밍의 조건

  1. 최적 부분 구조(Optimal Substructure)

     1. 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

  2. 중복되는 부분 문제(Overlapping Subproblem)

     1. 동일한 작은 문제를 반복적으로 해결

• 피보나치 수열

<문제> 개미 전사

<문제> 1로 만들기

<문제> 효율적인 화폐 구성

<문제> 금광

<문제> 병사 배치하기

6

최단 경로 알고리즘

• 가장 짧은 경로를 찾는 알고리즘

• 다양한 문제 상황

  • 한 지점에서 다른 모든 지점까지의 최단 경로

  • 한 지점에서 다른 모든 지점까지의 최단 경로

  • 모든 지점에서 다른 모든 지점까지의 최단 경로

• 각 지점은 그래츠에서 노드로 표현

• 지점 간 연결된 도로는 그래프에서 간선으로 표현

다익스트라 최단 경로 알고리즘

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산

• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작

• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류

  • 매 사왕에서 가장 비용이 적은 노드를 선택

동작과정

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

5. 위 과정에서 3, 4번을 반복

특징

• 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

• 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음

  • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있음

• 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드 까지늬 최단 거리 정보가 저장

  • 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 함

성능 분석

• 전체 시간 복잡도는 O(V^2)

우선순위 큐 (Priority Queue)

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

힙 (Heap)

• 우선순위 큐를 구현하기 위해 사용하느 자료구조 중 하나

• 최소 힙과 최대 힙이 있음

• 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

폴로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

• 폴로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행

  • 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음

• 2차원 테이블 에 최단 거리 정보를 저장

• 다이나믹 프로그래밍 유형에 속함

<문제> 전보

<문제> 미래 도시

7

서로소 집합

• 공통 원소가 없는 두 집합을 의미

신장 트리

• 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미

  • 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함

최소 신장 트리

• 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때

크루스칼 알고리즘

• 간선의 개수가 E 개일 떄, O(ElogE)의 시간 복잡도를 가짐

• 크루스칼 알고리즘에서 가장 많은 시간을 요구하는 곳은 간선을 정렬을 수행하는 부분

위상 정렬

• 사이클이 없는 방향 스래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미

• 예를 들면, 선수 과목을 고려한 학습 순서 결정

• 진입차수와 진출차수

  • 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수

  • 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 알고리즘

• 큐를 이용하는 위상 정렬 알고리즘의 동작 과정

  1. 집입차수가 0인 모든 노드를 큐에 넣는다

  2. 큐가 빌 때까지 다음의 과정을 반복

     1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

     2. 새롭게 진입차수가 0이 된 노드를 큐에 넣음

  → 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과

위상 정렬의 특징

• 위상 정렬은 순환하지 않는 방향 그래프

• 위상 정렬에서는 여러 가지 답이 존재할 수 있음

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있음

• 스택을 활용한 DFS(Direct Acyclic Graph)를 이용해 위상 정렬을 수행할 수도 있음

8

소수

• 소수 판별 알고리즘

• 약수의 성질

에라토스테네스의 체 알고리즘

투 포인터

• 리스트에 순차적으로 접근해야 할 떄 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

구간 합 빠르게 계산하기

9

개발형 코딩 테스트

HTTP REST API

JSON