알고리즘

알고리즘 왜 공부하는가?

구현을 잘할 수 있게 된다.

알고리즘 어떻게 공부하는가?

원리 이해
추상화하기 (시간 복잡도)
현실 문제를 알고리즘으로 변환하는 연습하기 → 알고리즘 문제 풀기
현실 문제 알고리즘으로 변환하기, 추상화하기 > 원리 이해 (물론 이것도 중요함)

배열 정렬 : Sort 함수로 이미 구현되어 있음. Sort 함수가 어떻게 작동하는지 그냥 알고 가져다 쓰면 되는 것.

알고리즘 공부 순서?

그딴 거 없다. 대부분의 알고리즘은 의존성이 없다. 기초적인 것(제어 구조, 재귀적 사고)만 할 줄 알면 내가 원하는 것들, 필요한 알고리즘부터 공부해도 된다. 재귀로 문제를 해결하는 것이 매우 편하다. Json 같이 트리 구조로 되어 있는 자료를 접근하는 코드는 재귀적으로 작성하는 것이 좋다. 자료구조를 잘 사용해야 한다. Linked List, 배열, List, Queue, Stack, Heap, Dictionary ….

기초

제어 구조, 재귀적 사고
자료구조
수학(순열과 조합), 탐색(이진 탐색, BFS, DFS), 메모라이제이션(동적 계획법 Dynamic Programming)

이 이후는 기초를 활용해서 문제 풀이법을 만들어낸 알고리즘들이므로 알아서 찍먹하면 된다.

알고리즘 풀이 관련 미세 팁

문자열 처리

a~z : ‘a’ - ‘a’ 이런식으로 빼서 숫자로 바꾸기 편함.

A~Z : ‘A’-’A’ 이런 식으로 빼서 숫자로 변환 가능~

입출력

StreamReader, StreamWriter

Console.Read, Write는 매번 파일을 읽고 쓰는 것이라서 비용이 비쌈. StreamReader, Writer는 한번에 읽어오고 나중에 한번에 적어서 비용이 적음.

시간 복잡도

왜 중요할까?

많은 시험이 시간복잡도를 계산할 수 있는지 물어보는 문제를 많이 냄
- 구현 여부 : 이 문제를 해결할 수 있는 코드를 구현할 수 있는가?
- 효율성 : 이 문제를 효율적으로 해결하는 코드를 구현할 수 있는가?
시간 복잡도만 계산해도 어떤 알고리즘을 사용할지 결정할 수 있음.

시간 복잡도란?

알고리즘이 가장 느리게 돌아갔을 때 걸리는 최악의 속도
Big-O notation으로 표기
N개의 데이터가 있을 때 N번 돌면 O(N)
일반적으로는 Big-O notation에는 상수 표시하지 않음.
- N개의 데이터가 있을 때 $O(5N^2)$번 돈다면 $O(N^2)$
더 낮은 시간 복잡도는 고려하지 않는다.
- O(N^2+N) = O(N^2)
비용
- O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N)< O(N!)
1초는 1억번 연산 (C++)
- 일반적으로 문제는 1초 안에 해결할 수 있게끔 나옴
입력 크기를 보면 어떤 시간복잡도 알고리즘을 사용해야 하는지 알 수 있다.
- O(NlogN)
- O(2^N) 최소 입력 11 ~ 최대 입력 25, 자주 출제되는 N 5~15

자료구조

자료구조의 핵심은 추가/삭제/검색

배열 시간 복잡도

	추가	삭제	검색 (index 알고 있을 때)
맨앞	O(N)	O(N)	O(1)
맨뒤	O(1)	O(1)	O(1)
중간	O(N)	O(N)	O(1)

배열 추가는 맨앞이 아닌 맨 뒤에 해야할 것
배열 내용 삭제는 맨 뒤에서부터 하는 것이 좋을 것

Linked List

Head에서부터 뒤로 찾아가야 하므로
- 맨앞 추가, 삭제, 검색만 O(1)이고
- 중간이나 맨뒤 추가, 삭제, 검색은 O(N)
- 그래서 일반적으로 Double Linked List를 사용해서 앞뒤 추가 삭제 등이 O(1), 중간에 있는 원소를 알고 있다면 중간 검색, 삭제도 O(1)이 나올 수 있게 함.
추가 삭제 검색

맨앞 O(1) O(1) O(1)

맨뒤 O(N) O(N) O(N)

중간 O(N) O(N) O(N)

Stack

Last In, First Out
위에만 추가, 위에 있는 것만 삭제 가능하므로 추가 O(1), 삭제 O(1)
ArrayList로 구현 가능
크기 4인 배열이 꽉 차 있을 때 5번째 원소를 추가하면 원래 크기의 2배 크기로 만듦

Queue

First In, First Out
넣고 빼고 규칙 정해져 있으므로 추가 O(1), 삭제 O(1)
링크드 리스트로 구현함.

Tree

Leaf (자식 없는) 끝 노드
Level 과 Depth
Linked List로 구현 가능. Left 자식, Right 자식 가리키고 자신의 데이터 가지고 있는 상태.
특별한 트리
- 이진 검색 트리
- 완전 이진 트리 : 배열로 만들 수 있는 유일한 트리.
  - 왼쪽 자식의 depth = 부모의 depth*2
  - 오른쪽 자식의 depth = 부모의 depth*2 +1

Tree 순회하기

        A
    B      C
  D   E       F
G  H         I  J

함수 콜 스택과 비슷함.
접근 순서 A-B-D-G-H-E-C-F-I-J
A가 B, C 호출 → B가 D, E 호출 → D가 G, H 호출 → G 리턴 → H 리턴 → D 리턴 → E리턴 → B 리턴 → C가 F 호출 → F가 I, J 호출 → I 리턴 → J 리턴 → F 리턴 → C 리턴 → A리턴

DFS (깊이 우선 탐색)

위의 트리 순회 방식. Stack 활용하면 좋다.
탈출 조건
할 일
자식 노드 순회 (재귀)

BFS 넓이 우선 탐색

Queue로 짜면 편하다.

root = A;
A 추가 //A
A 빠지고 B, C 추가 // BC
B 빠지고, D, E 추가 // CDE  // B 자식 추가
C 빠지고, F 추가 // DEF     // C 자식 추가
D 빠지고 G, H 추가 // EFGH  // D 자식 추가
E 빠지고
F 빠지고 I, J 추가  //GHIJ  // F 자식 추가
G 빠지고
H 빠지고
I 빠지고 
J 빠지고

저작자표시 비영리 변경금지 (새창열림)

개발하는 심리학자

알고리즘 특강 정리