'Algorithm/알고리즘 문제 해결 전략'에 해당되는 글 2건

  1. 2015.02.08 알고리즘 문제 해결 전략2 study 정리
  2. 2015.02.08 알고리즘 문제 해결 전략1 study 정리
[5] 기초 자료 구조
16. 비트마스크

17. 부분 합
배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열

18. 선형 자료 구조
18.2 동적 배열(dynamic array)
- 배열의 크기를 변경하는 resize() 연산이 가능. 이 동작을 수행하는 데는 배열의 크기 N에 비례하는 시간이 걸림
- 주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원. 이 동작을 수행하는 데는 상수 시간이 걸림
- 배열의 용량이 꽉 찼을 때 이것을 어떻게 증가시키느냐, 어떻게 줄이느냐가 배열의 효율성에 영향을 미침

18.3 연결 리스트
배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제를 상수 시간에 할 수 있게 해줌
특정 위치의 값을 찾는 데 드는 시간은 리스트의 길이에 선형 비례함

18.4 동적 배열과 연결 리스트 비교
삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 하면 될 경우에는 동적 배열이 거의 항상 더 좋은 성택
임의의 원소에 빠르게 접근할 수 있을 뿐더러, 원소들이 메모리에 연속해 배치되어 있다는 점이 CPU 캐시 효율을 높여줌

19. 큐와 스택, 데크 - 모두 O(1) 에 Push와 Pop이 이루어져야함
(1) 큐 : FIFO. 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있음
(2) 스택 : 한쪽 끝에서만 자료를 넣고 뺄 수 있음. 함수 문맥 관리용으로 사용
(3) 데크 : 양쪽 끝에서 자료를 넣고 뺄 수 있는 자료 구조

19.2 큐와 스택, 데크의 구현
(1) 연결 리스트를 통한 구현
(2) 동적 배열을 이용한 구현
- 스택은 바로 구현 가능
- 큐, 데크는 환형 버퍼(Circular buffer) 이용

20. 문자열
(1) 문자열 검색 문제를 위한 KMP(knuth,orris_Pratt) 알고리즘
(2) 접미사 배열(suffix array)
자세히 한번 볼것 ~!!

[6] 트리
21. 트리의 구현과 순회
* 자료구조
(1) 추상형 자료 구조
a. 스택
b. 큐
(2) 탐색형 자료 구조
a. 해시
b. 트리
- 이진탐색트리, 구간트리, 힙

(3) 트리의 구성 요소
node, edge, parent, child, sibling, ancestor, descendant,
root, leaf

22. 이진 검색 트리(binary search tree)
AVL트리, 레드 블랙 트리

22.6. 균형 잡힌 이진 검색 트리: 트립
(1) 트립의 조건(자세히 한번 볼것~!!)
a. 이진 검색 트리의 조건 : 모든 노드에 대해 왼쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 작고, 오른쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 큽니다.
b. 힙의 조건 : 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같습니다.

23.1 우선순위 큐와 힙
- 우선순위가 가장 높은 자료가 가장 먼저 꺼내짐
(1) Heap : 가장 큰 원소를 찾는 데 최적화된 형태의 이진 트리로, 힘을 사용하면 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행 가능
우선순위와 실제 자료의 쌍을 담는 힙을 만들고, 대소 관계를 비교할 때는 우선순위를 비교하도록 함

24. 구간 트리: 구간에 대한 질문 대답하기
특정 구간의 최소치를 찾는 문제
각 구간의 합을 트리로 구현
(1) 구간 최소 쿼리(RMQ) : 특정 구간의 최소치를 찾는 문제
(2) 펜윅 트리(Fenwick Tree, binary indexed tree)

25. 상호 배타적 집합(disjoint set)
유니온-파인드(Union-Find) 자료 구조 : 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조
(1) 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화
(2) 합치기(union) 연산 : 두 원소 a, b가 주어질 때 이들이 속한 두 집합을 하나로 합칩니다.
(3) 찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환합니다.

26. 트라이
문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있음
집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리
한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있는데 두 노드는 부모 자식 관계로 연결됨

26.4 : 트라이를 이용한 다중 문자열 검색
* 실패 함수(failure function) : 대응에 실패했을 때 어디로 가서 검색을 계속해야할지 알려주는 함수
* 아호-코라식(Aho_Corasick) 문자열 검색 알고리즘 : 각 노드의 실패 함수를 전처리 과정에서 만든 뒤, 짚더미 문자열의 글자를 순회하면서 트라이의 상태들을 서로 오가면 모든 바늘 문자열들에 대해 동시에 KMP알고리즘을 수행하는 것과 같은 효과를 얻을 수 있음
- 긴 문서에서 많은 문자열을 동시에 찾아야 하는 검색 엔진 등에서 특히 유용함

[7] 그래프
27. 그래프의 표현과 정의
그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조
(a) 방향 그래프
(b) 가중치 그래프
(c) 다중 그래프 : 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프
(d) 루트 없는 트리 : 부모 자식 관계가 없을 뿐, 간선들의 연결관계만 보면 트리와 같은 무향 그래프, 간선들의 연결 관계가 트리와 같다는 말은, 간선을 통해 두 정점을 잇는 방법이 딱 하나밖에 없다는 의미
(e) 이분 그래프 : 색이 같은 정점들 간에는 간선이 없는 그래프. 남성과 여성의 그래프로 보면 남성과 여성끼리만 이어져 있음
(f) DAG(Directed acyclic graph) : 사이클 없는 방향 그래프

28. DFS (깊이 우선 탐색 depth-first search)
그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
Ex1) 두 정점이 서로 연결되어 있는가 확인하기
Ex2) 연결된 부분집합의 개수 세기
28.2 위상 정렬 - 고대어 사전 문제(Dictionary)
그래프에 사이클이 있는지 확인하고, 없다면 위상 정렬 결과를 반환
28.4 오일러 서킷
- 종이에서 펜을 떼지 않고 주어진 도형의 모든 선을 정확히 한 번씩 그리고 시작점으로 돌아오는 한붓 그리기 문제
- 모든 정점들이 짝수점이어야만 오일러 서킷이 존재할 수 있음
28.4 오일러 트레일
시작점과 끝점이 다른 경로
28.6 해밀토니안 경로
그래프의 모든 정점을 정확히 한 번씩 지나는 경로

29. BFS (Breadth First Search(너비 우선 탐색))
최단 경로 풀 때 주로 사용됨
29.2 Sort Game

30. 최단 경로 알고리즘
가중치가 있는 그래프 위에서의 최단 경로

(1) 음수 사이클이 있는지 확인
(2) 단일 시작점 알고리즘과 모든쌍 알고리즘
단일 시작점 알고리즘 - 하나의 시작점에서 다른 모든 정점까지 가는 최단 거리
모든쌍 알고리즘 - 모든 정점의 쌍에 대해 최단 거리 (V*V 크기 배열)
- 플로이드의 최단 경로 알고리즘
(3) 방향 그래프와 무방향 그래프

30.2 (dijkstra)다익스트라의 최단 경로 알고리즘
가중치가 있는 그래프의 시작 정점s에서부터 다른 정점들까지의 최단 거리를 계산함
- 기본적으로는 우선순위 큐를 사용함
- 정점의 수가 적거나 간선의 수가 매우 많은 경우에는 아예 우선순위 큐를 사용하지 않고 구현






Posted by 공놀이나하여보세
,
[1]. 문제 해결 시작하기


[2] 알고리즘 분석


[3] 알고리즘 설계 패러다임
6. 무식하게 풀기
6.2. 중첩 반복문 대체하기(Recursive)

7. 분할 정복
주어진 문제를 둘 이상의 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

8. 동적 계획법 - Memoization (캐쉬에 저장)
처음 주어진 무제를 더 작은 문제들로 나눈뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 냄
답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로서 속도 향상을 꾀할 수 있음
*Memoization 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법

10. Greedy method
재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 같음
하지만, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만들 선택
1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우
2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어려울 때 근사해를 찾는 것으로 타협함

11. 조합 탐색( combinatorial search)
- 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘
(1) 가지치기(pruning) - 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냄

12. 최적화 문제 결정 문제로 바꿔 풀기
최적화 문제를 결정 문제(decision problem)로 바꾼 뒤, 이것을 이분법을 이용해 해결
결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제

[4] 유명한 알고리즘들
13. 수치 해석
직접 풀기 힘든 수학 문제를 근사적으로 푸는 알고리즘과 이들의 수치적 안정성, 오차의 범위등을 연구하는 전산학의 한 분야

13.2 이분법(bisection method)
주어진 범위 내에서 어떤 함수의 값이 0이 되는 지점을 수치적으로 찾아내는 기법

14 정수론
14.2 소수
주어진 수가 소수인지 확인하는 것

14.2 소인수 분해
- 한 합성수를 소수들의 곱으로 표현하는 방법
- 에라토스테네스의 체

15. 계산 기하(computational geometry) ( 하는 일과 관련이 있으니 꼭 다시 볼 것!!!!)
점, 선, 다각형과 원 등 각종 기하학적 도형을 다루는 알고리즘을 계산
- 대회에서는 대부분 2차원 기하학
(1) 벡터의 구현
(2) 점과 직선, 선분의 표현
(3) 벡터의 내적과 외적
15.3. 교차와 거리, 면적



Posted by 공놀이나하여보세
,