computer science/algorithm11 알고있으면 좋은 아이디어 BFS ✔️ BFS에서 방문 체크의 상태가 2차원 배열인 경우 map를 사용해 해시로 상태를 관리할 경우 메모리 초과와 시간 초과이다. 해결 아이디어는 2차원 배열 상태를 문자열로 변환하여 unordered_map의 키 값으로 사용해 방문 체크를 하면 된다. 관련문제 [BOJ 1525] 퍼즐 ✔️ 방문 제한 구역(정점(\(X\), \(Y\))을 기준으로 거리 \(D\) 이하의 정점들의 영역)이 있는 경우 다익스트라 알고리즘을 응용해 방문 제한 구역을 체크할 수 있다. 아이디어는 인접한 정점까지 더 늦게 방문 할 수 있도록 거리 배열을 최신화하여 최대한 방문하지 못하는 구역을 넓히는 것이다. while (!pq.empty()) { auto [d, x, y] = pq.top(); pq.pop(); if (d.. 2023. 4. 16. 퀵소트의 시간복잡도 Time complexity of quick sort 퀵소트는 피봇을 정하는 파티션 과정과 2번의 분할 과정으로 이루어져 있다. \(n\)개의 원소를 퀵소트로 정렬하는 데 걸리는 시간을 \(T(n)\)이라 할 때 \(T(n)\)은 \(m\)개와 \(n-m\)개로 분할된 원소를 정렬하는 시간과 \(n\)개의 원소 중 피봇을 정하는 파티션 과정으로 나눌 수 있다. 아래 식을 활용해서 퀵소트의 시간복잡도를 구할 수 있다. $$T(n) = T(m) + T(n-m) + C(n) $$ Best case time complexity 퀵소트는 피봇이 항상 배열을 균등하게 분할하여 분할의 횟수가 \(\log n\)번 실행되는 경우에 \(O(n\log n)\)에 동작한다. 최선의 방법으로 퀵소트를 할 때 걸리는 시간을 \.. 2023. 1. 4. 크루스칼 알고리즘 스패닝 트리 스패닝 트리란 무향 그래프의 모든 정점을 연결하는 부분 그래프이다. 간선의 개수는 \(V-1\) 개로 트리 구조이다. 그림 1은 7개의 정점을 6개의 간선을 이용해 연결하는 올바른 스패닝 트리이다. 반면에 그림 2는 0-1-2의 정점으로 이루어진 사이클이 있으며 2, 4번 정점은 연결되어 있지 않으므로 스패닝 트리가 아니다. 그림 1 그림 2 최소 스패닝 트리 최소 스패닝 트리란 가중치가 있는 무향 그래프의 스패닝 트리 중에서 가중치의 합이 최소인 스패닝 트리이다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 대표적이다. 크루스칼 알고리즘 가중치가 큰 간선과 가중치가 작은 간선 중 어떤 간선이 최소 스패닝 트리에 포함될 가능성이 높을까? 당연히 가중치가 작은 간선.. 2022. 8. 31. BFS에서 다익스트라 알고리즘까지 Single source shortest path unweighted graph → BFS weighted graph with nonnegative weights → Dijkstra weighted graph with negative weights → Bellman-ford, SPFA directed acyclic graph → topological sorting 용어 정의 경로의 길이 : 경로가 지나는 간선의 가중치의 합 정점 \(u\)에서 정점 \(v\)의 최단경로 : u에서 v로 가는 경로의 길이가 최소인 경로 간선의 완화(edge relaxation) : 정점 \(u\)에서 \(v\)로의 간선에 대해 dist[\(v\)] > dist[\(u\)] + weight(\(u, v\)) 만족하면 dist.. 2022. 8. 6. 그리디 알고리즘 증명1 - Greedy stays ahead 그리디 알고리즘(greedy algorithm) 완전 탐색, 동적 계획법처럼 답을 구하는 과정을 여러 개의 단계로 나누어 답을 만들어가는 과정은 비슷하지만, 각 단계에서 가능한 모든 답을 계산하여 전체적으로 가장 좋은 답을 선택하는 것이 아니라 각 단계에서 가장 좋은 답을 선택하는 점이 완전 탐색, 동적 계획법과 다른 점이다. 외판원 순회 문제에서 동적 계획법은 현재 정점에서 갈 수 있는 정점 중에 전체 거리를 최소화할 수 있는 정점을 고르지만, 그리디 알고리즘은 단순히 현재 정점에서 다음 정점까지의 거리를 최소화하는 정점을 고른다. 그리디 알고리즘은 "답을 도출하는 과정 중 매 순간 최고의 선택을 해서 결과적으로 최적의 해를 도출하자"로 표현할 수 있다. 그런데 매 순간 최고의 선택이 항상 결과적으로 .. 2022. 7. 29. 그래프에서 최장거리 그래프에서 최단거리는 경우에 따라 BFS, 다익스트라, 벨만 포드, 플로이드 와샬을 사용하여 구할 수 있다. 그렇다면 최장거리는 어떻게 구할 수 있을까? 사이클이 없는 무향 그래프(트리)에서 최장거리 트리에서는 어떤 두 노드를 선택해도 둘 사이의 경로가 항상 하나만 존재한다. 따라서 BFS을 이용하여 구할 수 있다. 사이클이 없는 유향 그래프에서 최장거리 일반적인 그래프에서 최장거리를 구하는 방법은 NP-Hard로 알려져 있다. 하지만 DAG(Directed Acyclic Graph)에서는 구할 수 있다. DAG에서 최장거리를 구할 수 있는 2가지 방법을 정리해보자. 동적 계획법 정점 $u$ → $v$의 최장거리를 구하는 점화식을 아래와 같이 세워보자. $$ D[i] = \text{정점 } i \text.. 2022. 7. 13. 좌표 압축 테크닉 좌표압축 입력으로 범위가 [0, 1000000000]인 값이 1,000개 들어올 때 입력 값을 인덱스로 하는 배열이 필요하다면 아래와 같은 방법을 사용할 수 있을까? 아니다, 배열의 메모리만 해도 4 * 10억 byte = 4GB로 메모리가 부족하다. int index[1000000000]; int main(){ for(int i = 0; i > var; index[var] = 1; } } 입력 값의 범위가 10억이지만, 입력의 개수는 1,000개 이므로 배열에 쓸모없는 공간이 너무 많다. 예를 들어 공차가 100인 값이 1,000개 들어온다고 해도 각 입력 값 사이의 빈 공간이 99개나 있는 격이다. 배열 사이의 빈 공간을 줄여서 값들에 새로운 인덱스를.. 2022. 6. 30. 오일러 투어 테크닉 오일러 투어 테크닉(euler tour technique) 오일러 투어 테크닉이란 DFS로 트리를 탐색하면서 임의 정점 \(v\)의 진입 시점과 탈출 시점을 기록하여 트리의 서브 트리를 일차원 배열로 관리하는 테크닉이다. 과정 1. 루트부터 DFS를 시작해 각 정점의 진입 순서를 left 배열에 기록하자. (0-base, 1-base 상관없다.) 2. 탈출 순서를 right 배열에 기록하자 3. 트리와 left, right 배열을 한 번에 보면, 정점 v를 루트로 하는 서브 트리에 속한 정점들의 방문, 탈출 순서가 모두 루트 정점에 진입, 탈출 순서 사이에 있다. 즉, 각 정점을 루트로 하는 서브 트리가 하나의 구간으로 나타난다. 구현 진입 순서와 탈출 순서를 어떻게 관리할까? 전역 변수를 이용하여 관리.. 2022. 6. 10. 이전 1 2 다음
