[이코테] 개인적인 정리 글 (1주차)

'이것이 취업을 위한 코딩테스트다'를 읽고 알고리즘 별로 정리하려는 계획을 세웠다.

책에 적힌 공부법을 보니 하루 3시간씩 한달에 걸쳐 공부하는 방법을 추천한다고 적혀있었다. 자바의 정석 때도 그랬지만 계획을 너무 타이트하게 잡아서 많이 후회하기도 했다. 그래도 일단 한번 다 읽고 다시 회독하겠다는 마음으로 우선 문제를 30분동안 고민해보고(원래는 30분안에 코드도 작성해야 한다.) 만약 못풀겠다 싶으면 다음 회독 때 풀 것을 기약하며 일단 넘어갔다. (그렇지 않으면 빠르게 완독하지 못할 것 같다.)

원래 예정은 알고리즘 별로 글을 따로 만들까 생각했지만 생각보다 책 내용이 개념적인 설명보다는 예제와 풀이 위주로 구성되어 있어서 책 내용만으로 별도의 글을 적을 경우 내용이 많이 부실하지 않을까 생각하여 일단 여기다 모아서 정리한다.

(문제의 경우 블로그에 쓰면 저작권 문제도 있을테니...)

---

◎ 그리디

- '현재 상황에서 지금 당장 좋은 것만을 고르는 방법'

- 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 넌지시 제시해준다.

- 최적해를 보장해주지 않는다. 따라서 해법이 정당한지 검토해야 한다.

- 바로 문제 유형 파악이 어렵다면 그리디 알고리즘을 의심해보자.

 

◎ 구현 

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

- 구현하기 어려운 문제

     ex1)  알고리즘은 간단한데 코드가 지나치게 길어지는 문제

     ex2) 특정 소수점 자리까지 출력해야 하는 문제

     ex3) 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등

     즉 사소한 조건 설정이 많은 문제일수록 구현하기 까다롭다.

- 보통 사소한 입력 조건 등을 문제에서 명시해준다.

- 코딩테스트에서 가장 난이도가 낮은 문제는 대부분 그리디 알고리즘이나 구현 문제이다.

 

※ 책에서는 구현 파트에서 '완전탐색'과 '시뮬레이션'을 다루고 있다.

완전탐색 : 모든 경우의 수를 다 계산하는 방법 - 그래서 시간 복잡도가 비효율적(데이터 수 100만 개 이하일 때 사용하면 적절)

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

※ C/C++ 자바의 경우 자료형의 크기를 고려해야 한다.

파이썬의 경우 프로그래머가 직접 자료형을 지정할 필요가 없다.

 

※ 리스트가 1000만 이상인 경우 메모리 용량 제한에 걸릴 수 있으나 이런 문제는 드물다. 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 정도만 기억하자.

 

※ 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

 

◎ 탐색

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

- DFS, BFS가 대표적

 

◎ 자료구조

- 데이터를 표현하고 관리하고 처리하기 위한 구조

- stack, queue, 연결리스트 등

 

◎ 스택

- 선입후출(First In Last Out)의 자료구조

- 파이썬에서는 기본 리스트에서 append()와 pop()메서드를 이용하면 스택 자료구조와 동일하게 동작

 

◎ 큐

- 선입선출(First In First Out)의 자료구조

- 파이썬에서는 Collections 모듈에서 제공하는 deque 자료구조를 이용

(deque 객체를 리스트 자료형으로 변경하려면 list() 메서드 이용. list(deque)

 

◎ 재귀함수

- 자기 자신을 다시 호출하는 함수. 반복문보다 간결하다(수학의 점화식을 그대로 옮겼기 때문)

- 반드시 종료 조건을 명시해야 한다. 그러지 않을 경우 함수가 무한 호출 될 수 있다.

- 재귀함수는 스택 자료구조를 이용한다. 가장 마지막에 호출된 함수가 먼저 수행되어야 그 앞의 함수 호출이 종료되기 때문

- 따라서 스택 자료구조를 이용하는 상당수 알고리즘은 재귀 함수를 통해 간편하게 구현될 수 있다.

 

◎ DFS

- 깊이 우선 탐색(Depth-First Search)

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택 자료구조를 기초로 한다.

- 그래프의 표현 방식

     인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현, 연결되지 않은 노드끼리는 무한의 비용이라고 작성

     인접리스트 : 리스트로 그래프의 연결 관계를 표현

     인접행렬과 인접리스트의 장단점 : 

     인접행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 낭비된다.

     반면 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다.

     반대로 인접리스트는 메모리를 효율적으로 사용하지만 정보를 얻는 속도가 느리다.

- DFS는 특정한 경로로 참색하다가 특정한 상황에서 최대한 깊숙히 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

- 동작 과정

1. 탐색 시작 노드를 스택에 쌓고 방문 처리를 한다.

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

3. 1~2의 과정을 반복한다.

- 시간복잡도 O(N)

 

◎ BFS

- 너비 우선 탐색(Breadth First Search)

- 가까운 노드부터 탐색하는 알고리즘

- 큐 자료구조를 기초로 한다.

- 큐 자료구조를 이용하여 구현

- 동작 과정

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

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

3. 1~2의 과정을 반복한다.

- 시간 복잡도 O(N)

- 일반적인 경우 DFS보다 수행시간이 좋은 편이다.

 

※ 코딩 테스트 중 2차원 배열에서 탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민해보자.

 

※ 정렬

- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

- 정렬 알고리즘으로 데이터를 정렬하면 이진탐색이 가능해진다.

 

◎ 선택 정렬

- 가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 두 번째 데이터와 바꾸는 과정 반복

- 매번 가장 작은 것을 선택한다는 의미

- 시간 복잡도 : O(n2)

- 데이터 수가 10000개 이상이면 정렬 속도가 급격히 느려진다.

 

◎ 삽입 정렬

- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입

- 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이다.

- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다 가정

- 삽입정렬은 두 번째 데이터부터 시작. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단

- 정렬이 이루어진 원소는 항상 오름차순을 유지

- 그래서 특정한 데이터가 삽입될 위치를 정할 때 삽입될 데이터보다 작은 데이터를 만나면 멈추면 된다.

- 시간복잡도 : O(n2), 최선의 경우 O(N)

- 퀵정렬과 비교했을 때 보통은 삽입정렬이 비효율적이나 거의 정렬 되어 있는 상황에서는 삽입정렬이 더 빠르다.

 

◎ 퀵 정렬

- 가장 많이 사용되는 정렬 알고리즘

- 기준(피벗 pivot) 을 설정한 후 기준보다 큰수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식

- 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러가지 방식 존재

- 호어 분할 방식 : 첫 번째 데이터를 피벗으로 정한다.

- 퀵 정렬이 끝나는 조건 : 현재 리스트의 데이터 개수가 1개인 경우

- 시간 복잡도 :  O(NlogN).

- 최악의 경우 시간 복잡도는 O(n2)이다. 이미 데이터가 정렬되어 있는 경우 느리게 동작

- 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 O(NlogN)이 되는 것을 보장할 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해준다.

 

◎ 계수 정렬

- 특정 조건(데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 경우)이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

- 최악의 경우에도 O(N+K)를 보장한다.

- 가장 큰 데이터와 가장 작은 데이터의 차이가 1000000을 넘지 않을 때 효과적이다.

- 앞선 정렬 방식들은 데이터 값을 비교한 뒤 위치를 변경하는 비교 기반 정렬 알고리즘이지만 계수 정렬은 그런 방식이 아니다.

- 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.

- 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

- 출력할 때는 해당 인덱스의 값만큼 출력시킨다.

- 현존하는 정렬 알고리즘 중에서 기수 정렬(계수 정렬에 비해 느리지만 처리할 수 있는 정수의 크기가 더 크다)과 더불어 가장 빠르다.

- 때에 따라서 메모리의 비효율성을 초래할 수 있다. ex)0,999999만 존재하는 데이터의 경우 0부터 999999의 리스트를 선언해야 한다

- 동일한 값이 여러 개 등장할 때 적합한 알고리즘이다.

- 이러한 조건들로 인해 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

 

※ 정렬 라이브러리는 최악의 경우에도 O(NlogN) 을 보장하므로 별도 요구 없이 단순히 정렬해야 하는 경우 정렬 라이브러리를 사용하고, 데이터 범위가 한정되어 있으며 더 빠르게 동작해야 하는 경우 계수 정렬을 사용하자.

 

※ 정렬 알고리즘 사용되는 경우 문제 유형

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제

2. 정렬 알고리즘의 원리에 대해 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 잇어야 풀 수 있다.

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없고, 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.