알고리즘/유형별 정리 (10) 썸네일형 리스트형 10.dp 동적 프로그래밍 문제의 크기를 변화하면서 정답을 계산 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘 + memoization 1. 문제가 원하는 정답을 찾기 위해 가장 먼저 완전탐색 접근을 시도 2. 완전탐색과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될것같다 3. 모든 경우를 빠르게 탐색하는 방법으로 dynamic programming접근을 시도해본다 -> 규격화된 문제 풀이 순서를 외워서 훈련하..? 풀고싶은 가짜 문제 정의 -> 가짜 문제를 풀면 진짜 문제를 풀 수 있는가? -> 초기 값은? -> 점화식 구해내기 -> 진짜 문제 정답 출력 상태 공간의 정의와 상태 파악.status 반복되는 상태공간이라면 고려해볼만하다. 또한, 무엇의 상태에 따라 변화되는지 파악.. 9. 최단거리 알고리즘 그래프 시작점에서 다른 지점까지의 최단거리 이름 간선의 가중치 시작점 도착점 시간복잡도 BFS 모두 1 한정점 모든정점 O(V+E) Dijkstra >=0 한 정점 모든정점 O(ElogV) Floyd-Warshall 제약없음 모든정점 모든정점 O(V^3) Bellman-ford 제약없음 한정점 모든정점 O(V*E) SPFA 제약없음 한정점 모든정점 O(V*E) A* >=0 한정점 한 정점 O(b^d) bfs 최소이동횟수 계산 가능 Dijkstra dist[i] 시작점에서 i번정점까지 가능한 최단거리 왜 음수 간선이 안되는가 1. cycle 2. minimum + minimum (확장 불안정성) = edge relaxation 계산 오류 가능성 3. 회피시의 시간 복잡도 (ex PQ사용) 8. 위상정렬(Topological sort) Directed Acyclic Graph(DAG) 간선에 방향성이 있고, cyclic이 없는 graph(V +E) 차수 Degree, InDegree와 outDegree로 구별 정점들을 위상에 맞춰 정렬한다. 제일 먼저 올 수 없는 정점이 들어오는 간선이 없는 정점임에 집중할 수 있다. 하나씩 정렬시키면서 그래프에서 삭제하자. 정리 정점들의 indegree 계산하기 들어오는 간선이 0 개인 정점들을 찾아서 Queue에 넣고 Queue가 빌 때 까지 1. 원소X를 꺼내서 "정렬" 시키기 2. graph에서 정점 X 제거하기 3. 새롭게 정렬 가능한 점 찾아서 D에 넣기. Indegree계산은 O(|E|) 총 시간 복잡도는 O(|V| + |E| ) 방향성에 따라 어떻게 그래프를 구성하고 설계할것이냐가 중요한.. 7. 트리 트리는 그래프의 special case N개의 정점에 대해 N-1개의 간선이 주어짐. child, parent, sibling, depth, leaf, root 등 트리의 terminology가 있음. 트리의 특징이라고 하면 사이클이 존재하지 않는다. N개의 정점에 대해 N-1개의 간선이 있다는 것으로 활용 가능함. 한 노드에서 다른 노드로 가는 최소 경로가 하나로 정해진다. 연결 그래프이다. 구현의 경우 인접 리스트 또는 인접 행렬로 한다. A와 B 간선 존재 여부 인접행렬 인접리스트 A와 B를 잇는 간선 존재 여부 확인 O(1) O(min(deg(A), deg(B)) A와 연결된 모든 정점 확인 O(|V|) O(deg(A)) 공간 복잡도 O(|V^2|) O(|E|) 탐색 방법 - 2진 트리일 경우 전.. 6. 그래프 - 그래프의 탐색 bfs, dfs 격자형 - 최소 스패닝 트리 추천 문제 https://www.acmicpc.net/problem/1197 (백준 1197번 최소 스패닝 트리 Gold IV) https://www.acmicpc.net/problem/4386 (백준 4386 별자리 만들기 Gold IV) https://www.acmicpc.net/problem/1647 (백준 1647 도시 분할 계획 Gold IV) - 접근 방법 상태 공간(dp처럼 생각할 수 있는) 5. 투포인터 정답을 찾기 위해 봐야하는 범위에서 볼 필요 없는 부분을 제외하고 봐야하는 부분만 본다. 화살표 두개에 의미를 부여하여 탐색 범위를 압축하는 방법 1. 1차원 배열 위에 2개의 포인터를 만드는 경우 1.1 2개의 포인터가 왼쪽에서 시작해서 같은 방향 1.2 2개의 포인터가 양 끝에서 서로를 향해 이동. 2. 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 표현하는 경우 투포인터는 O(N)으로 확인할 수 있다는 큰 장점이 있다. 그래서 연속된 부분합에서 어떠한 값을 확인하는데에도 많이 사용된다. 추천 문제) - 백준 부분합 https://www.acmicpc.net/problem/1806 - 소수의 연속합 https://www.acmicpc.net/problem/1644 꿀팁 - 1차원 ㅐ열에.. 4. 이분탐색(Binary search) 탐색을 통해 풀어내는 문제의 종류는 세가지가 존재함 1. X가 존재 하는지 2. X[이하, 미만, 이상, 초과] 의 원소가 몇 개 있는지? 3. X랑 가장 가까운 원소는 무엇인지. 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 '이분' 하면서 탐색하는 방법. O(NlogN) 실수 1. 정렬되어 있지 않다. 2. L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우 3. L,R 범위 잘못 설정, Result 초기값 잘 못 설정. https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8.. 이전 1 2 다음