dh_0e

임계경로 (백준 1948번) DAG(방향 비순환 그래프)를 항상 만족하는 상황에서 최장거리를 구하는 문제. 풀이 과정처음엔 다익스트라 스타일로 최장 거리를 구하는 스타일로 풀어서 AC를 받았지만, 분명 $O(MlogN)$인데 시간이 너무 오래 걸렸다.다익스트라 느낌으로 prique를 써서 역방향 탐색하며 역추적을 위해 _next 벡터에 다음 node를 저장하면서 진행했는데, 생각해보니 어짜피 모든 간선을 탐색해야 하는데 굳이 prique를 써서 사용해야 하나 싶었다.이후, 위상정렬을 이용해 dp로 풀었더니 $O(M+N)$으로 시간을 많이 단축시킬 수 있었다. 다익스트라 스타일 ($O(MlogN)$)#include#include#include#includeusing namespace std;struct d..

오아시스 재결합 (백준 3015번) 보자마자 히스토그램 문제가 생각나서 스택으로 풀어보려다가 너무 뻔한 것 같아서 정렬, 이분 탐색으로 풀어봤다. 시간 초과 코드($O(n^2)$)vector의 insert 연산이 $O(n)$이라는 것을 까먹고 짰다가 시간 초과를 받은 코드키 순서대로 정렬한 다음 벡터에 이진 탐색으로 키와 index를 삽입하면서 좌, 우에 나보다 더 큰 수가 있으면 dap++ 해준다.똑같은 수가 연속적으로 삽입될 경우, 개수를 세어 "$kC2$ + $k$(왼쪽에 나보다 큰 수가 존재할 경우) + $k$(오른쪽에 나보다 큰 수가 존재할 경우)"를 더해주었다.제미나이를 사용해 이를 세그먼트 트리로 구현하여 $O(nlog^2n)$으로 줄여서 제출해 봤지만 시간 초과가 나왔다.n이 최대 500,..

전설 (백준 19585번) 총 13번의 오답을 받으며 오랜만에 머리 터질 정도로 시간 복잡도, 공간 복잡도 둘 다 생각하게 하는 문제였다. 풀이 과정Trie 자체를 최적화(재귀 >> 동적으로)하여 시간을 줄이면서, 동시에 Trie와 unordered_set을 함께 사용해서 시간, 메모리 둘 다 잡아 AC를 받을 수 있다. Trie를 잘 구현하여 최적화하고 set만 적절하게 사용하면 쉽게 풀리는 문제인데, 그 과정까지 시행 착오가 필요하다. 메모리 초과 코드 (Double Trie)#include#include#include#include#includeusing namespace std;stack st;struct Trie { bool finish; Trie* next[26]; Trie() :finish(..

벽 부수고 이동하기 4 (백준 16946번) dfs/bfs 기반으로 발상만 잘하면 쉽게 풀 수 있는 문제 풀이 과정먼저 빈 공간들을 분리하여 크기를 구한다(find 함수).vi 배열로 visit 체크해주는 동시에, 각 빈 공간들이 어떤 집합에 속했는지(set_num) 저장set_cnt 배열에 각 집합마다 빈 공간의 크기를 저장이후, 벽마다 상하좌우에 빈 공간이 있다면 해당 공간이 속한 집합의 빈 공간 크기(set_cnt)를 불러와 해당 벽이 부서졌을 때 만들어질 공간 크기(hap)에 저장한 후 출력한다(get 함수).빈 공간끼리 같은 집합에 속할 수 있기 때문에, set_vi 배열로 집합끼리 visit 체크를 해주어야 함hap % 10으로 출력할 것#include#include#includeusing n..

전깃줄-2 (백준 2568번) A or B 전봇대 중 하나를 기준으로 선택하여 정렬하고, 나머지 전봇대 배열의 LIS(가장 긴 증가하는 부분 수열)를 구하면 되는 문제. 발상이 생각보다 쉬워서 가장 긴 증가하는 부분 수열 5(백준 14003번)를 풀어봤다면 금방 해결 가능하다. 풀이 과정우선, n이 100,000 이하의 자연수이므로 LIS를 이분 탐색을 사용하여 $O(nlogn)$로 구현하여야 한다.if (vec[vec.size() - 1] vector를 만들어 다음 수가 vector에 들어있는 모든 값보다 크다면 수열의 맨 뒤에 추가해 준다.else{ .. }while(st그렇지 않다면 이분 탐색으로 해당 수보다 작은 수의 바로 다음 순서를 찾는다.vec[en]=d[i].first;다음 순서로 수열에..

아기상어 (백준 16236번) 오랜만에 푸는 생구현 문제(시뮬레이션). BFS로 탐색하면서 문제 조건을 모두 충족시켜야 한다.처음에 접근을 잘못해서 cost 값을 안 넣고 distance() 함수를 만들어 각 좌표의 거리 차이만큼을 cost로 이용하다가 잠깐 잊고 있던 "자신보다 큰 물고기는 지나가지 못한다는 조건"이 생각나서 2000자 이상 되는 코드에서 꾸역꾸역 cost를 집어넣어 수정했다. 역시 접근을 애초에 잘하거나 코드를 읽기 쉽게 짜지 않으면 디버깅이나 수정할 상황이 올 때 고생이다. bfs 돌리면서 문제 조건만 잘 구현해준다면 n 최댓값도 20이기 때문에 어렵지 않게 풀 수 있다.pair 남용을 하다가 이후에 구조체를 집어넣은 코드라 queue가 좌표 큐와 cost 큐로 분리되어 있다.. 오..

비숍 (백준 1799번) N-Queen 문제와 동일하게 백트래킹으로 해결해야 하는 문제지만 런타임을 더 줄여야 한다.모든 경우의 수를 탐색하면, k를 nxn 체스판에서 최대로 들어갈 수 있는 비숍의 개수라 놓고 시간 복잡도가 $O(2^k)$가 나올 것이라 예상했다. 10x10 체스판에 최대로 놓을 수 있는 비숍의 수(k)가 18개라 $2^{18}$은 10억을 넘지 않기 때문에 10초 안에 풀 수 있을 것 같았지만 발상 오류였다. 실제론 $O(2^{n*n})$ 풀이 과정결국 정해를 찾아보고 문제를 해결했다. 시간을 줄일 수 있는 방법은 $n$x$n$ 체스판을 흑, 백 2개의 $(n/2)$x$(n/2)$ 체스판으로 분할하여 각각 백트래킹을 수행하여 구한 최대로 놓을 수 있는 비숍의 개수를 합치는 것이었다. ..

피보나치 수 6 (백준 11444번) 문제를 해결하기 위한 수학 식을 만들고, 분할 정복으로 해결할 수 있는 문제로, 식을 만드는 과정에서 n이 짝수일 때, 홀수일 때로 나누는 방법을 떠올리기 쉽지 않았다. 풀이 과정다음과 같이 d[i]="i번째 피보나치 수"로 식을 세워서 변형해 보면 다음과 같은 규칙을 찾을 수 있다.이를 이분 탐색을 하며, n이 짝수일 때, 홀수일 때로 나누면 다음과 같이 2개의 식이 나온다.이를 분할 정복으로 구현하되 map을 활용하여 한 번 계산한 fib(n)의 값을 저장해준다. 이렇게 한 번 구했던 fib(n) 값을 중복으로 값을 구하는 상황을 없애주게끔 구현해 주면 이분 탐색 시간 복잡도 * map의 시간 복잡도 = $O(logn) * O(logn)$의 시간 복잡도로 풀 수 ..

골목길 (백준 1738번) 역시 벨만-포드 알고리즘이 기본이 되는 문제로, 1에서 n까지 가는 길에 양의 사이클이 포함되어 있는지 확인하면서 n까지 가는 경로를 출력하는 문제. 풀이 과정오민식의 고민(백준 1219번)의 풀이처럼 벨만-포드 알고리즘을 적절히 구현하여 나올 수 있는 경우의 수를 모두 구해본다.n까지 가는 경로 X: -1 출력n 도착: 경로 출력무한 증가: -1 출력 (무한 증가 사이클의 교차점들에서 n까지 가는 경로가 존재할 때)무한 감소: 무시dfs나 bfs로 무한 증가 사이클의 교차점들에서 n까지 가는 경로가 존재하는지 확인한다.이때, 인접 행렬을 사용하면 편하며, 한 번 방문한 node에선, n까지 도달했으면 이미 flag를 체크했을 것이기 때문에 visit 체크를 0으로 초기화하는 ..

오민식의 고민 (백준 1219번) 벨만-포드 알고리즘이 기본이 되는 문제지만, 도착 도시까지 가는 길에 사이클이 포함되어 있는지 확인하는 과정을 발상해야 하는 문제. 풀이 과정먼저, 벨만-포드 알고리즘을 적절히 구현하여 나올 수 있는 경우의 수를 모두 구해본다.도착 불가능: gg 출력무한 증식 가능: Gee사이클 없이 도착: 최대 액수 출력무한 음수값 가능: 무시1, 3, 4 상황은 벨만-포드 알고리즘과 문제에 대한 이해만 충분하다면 어려움 없이 구현할 수 있다. cost를 최단 경로가 아닌 최대 경로를 구하는 식으로 바꾸기만 하면 된다.$if(cost[end] "2. 무한 증식 가능"인 상황을 찾기 위해선 n번째 벨만-포드를 돌렸을 때, 이전 값보다 증가한 도시(증가 사이클에 포함된 노드)들에 대해 ..

타임머신 (백준 11675번)웜홀 (백준 1865번)음수 간선을 포함한 그래프의 최단 거리 혹은 음수 사이클을 찾고 싶을 때, 사용하는 벨만-포드 알고리즘에 대해 공부할 수 있었다.그래프에 음수 간선이 포함되어 있으면, 그리디하게 진행되는 다익스트라로는 최단 거리를 구할 수 없음. 플로이드 워셜은 가능은 하지만 $O(V^3)$이고, 벨만-포드는 $O(VE)$ 만에 해결할 수 있음 타임머신(11675)벨만-포드 알고리즘을 구현만 하면 되는 기초 문제.음수 사이클을 돌 때, 최악의 상황에서 -10,000을 500(최대 정점 수) x 6000(최대 간선 수)번 더할 수 있으므로 최대 -30억에 접근할 수 있도록 long long을 설정해줘야 됨#include#include#includeusing namespa..

다리 만들기 2 (백준 17472번) 문제 발상이나 각 알고리즘의 난이도는 쉬운편인데 구현이 복잡해서 실수하기 쉬운 문제.풀이 과정dfs나 bfs로 섬들의 번호를 매긴다. (Flood Fill)바다를 찾아 상하좌우로 만들 수 있는 다리를 전부 만든다. (Brute-force)만들어진 다리로 크루스칼이나 프림 알고리즘을 사용하여 모든 섬을 연결하는 최소 다리 길이를 구한다. (MST)#include#include#includeusing namespace std;int n, m, isl = 1;int d[11][11], bridge[11][11];int vi[11];void dfs(int y, int x, int num){ d[y][x] = num; if (y - 1 >= 0 && d[y - 1][x] =..

발전소 (백준 1102번) 비트필드를 이용한 dp 문제로 n이 16 이하의 자연수이기 때문에 $O(2^{n}*n^{2})$으로 해도 최대 16,777,216이 나오기 때문에, 시간초과가 나오지 않는다. 풀이 과정 dp 점화식을 dp[i][j] = 'i개의 발전소가 작동할 때, 발전소 상태가 j인 경우 드는 최소 비용' 으로 잡는다. 이때, j에 들어가는 값은 비트필드로 각 비트는 n(n-1)(n-2)...54321와 같이 내림차순으로 n~1번 발전소의 고장 여부를 나타낸다.(n이 5라고 가정했을 때, j가 10110이면 5, 3, 2번 발전소가 켜져있다는 뜻) 초기 dp 배열은 -1로 초기화하고, 작동중인 발전소들을 나타내는 값(: bit)을 구해서 dp[작동중인 발전소 수(: cnt)][bit]를 0..

LCA와 쿼리 2 (백준 15480번) 어떤 트리의 root를 계속해서 바꾸면서 LCA를 구하는 쿼리를 해결하는 문제로, LCA를 최대 100,'000번 구성하도록 코드를 짜면 무조건적으로 시간초과가 나온다. 수학적 패턴이나 조건 분기들을 따져야 하는 문제 같아서 계속 고민해 봤지만 발상이 쉽지 않았다. 풀이 과정 LCA(r, a)와 LCA(r, b), LCA(a, b)의 값을 비교하여 답을 쉽게 도출할 수 있다.LCA(r, a)와 LCA(r, b)가 같다면 LCA(a, b)가 root를 r로 바꾼 트리의 최소 공통 조상이 된다.이 경우엔, a부터 b로의 경로 중에 r이 없다는 뜻으로 root를 r로 바꾸어도 LCA는 그대로 LCA(a, b)가 된다.그렇지 않다면, LCA(r, a)와 LCA(r, b) ..

트리와 쿼리 2 (백준 13511번) 최소 공통 조상(LCA) 문제로 희소 배열, Binary Lifting을 사용하여 LCA를 $O(logn)$만에 구해야 한다. 풀이 과정 문제 설계는 여타 LCA 문제를 구현하듯이 하되, parent 배열에 비용, 정점 번호를 함께 저장한 뒤, LCA 함수를 약간 수정하고 문제 형식에 맞게 출력하면 된다. LCA 함수를 만들 때, u, v 정점에서 최소 공통 조상까지의 거리를 각각 cost에 더해주면서 합을 구해주고, 최소 공통 조상의 정점 번호를 함께 pair로 반환해준다. 반환한 값을 바탕으로 (1 u v) 형식의 쿼리는 그냥 cost 값을 출력해주면 되며, (2 u v k) 형식의 쿼리는 약간의 작업이 필요하다. 최소 공통 조상까지의 정점 갯수를 각각 LCA_u..

행성 터널 (백준 2887번) MST(Minimum Spanning Tree) 알고리즘 문제로 좌표상이 3차원이기 때문에 각 노드별로 간선을 만들어 풀면 $O(N^2)$으로 시간초과가 나온다. 풀이 과정 각 행성을 연결하는 터널(간선)을 만들 때 드는 비용이 $min(\lvert x_a - x_b \rvert,\; \lvert y_a - y_b \rvert,\; \lvert z_a - z_b \rvert)$ 이기 때문에, x, y, z를 기준으로 각각 정렬을 하여 인접한 행성들 간의 간선들만 만들어준다. 각 축을 기준으로 행성당 6개의 간선이 나오며 이 간선들의 비용을 오름차순으로 정렬하여 크루스칼 알고리즘으로 최소 스패닝 트리를 완성하는 총 비용을 구하면 된다. 본인은 priority queue를 활용..

아이돌 (백준 3648번) 2-SAT 문제에 상근(1번 참가자)이가 항상 합격할 수 있는 경우가 있는지를 찾는 문제. 풀이 과정상근이가 포함된 SCC 집합을 true로 만들고 각 SCC 집합 관계가 맞는지 확인하는 방식은 너무 복잡해짐.상근이가 항상 합격해야 한다는 심사위원의 평가를 하나 만들면 된다. vec[ch(-1)].push_back(1) → (1, 1) 의 평가를 하나 추가하여 1번 참가자가 무조건 합격하게끔 만드는 식으로 한정지어줌#include#include#include#include#includeusing namespace std;stack st;vector vec[2'001];bool vi[2'001];int p[2'001];int id = 0, scc = 0;auto ch = [](i..

2-SAT - 4 (백준 11281번) 2-SAT-3 에서 식을 true로 만들 수 있는 변수들의 값을 출력하면 되는 문제. 풀이 과정2-SAT 문제에서 변수 값을 정할 때 위상 정렬(Topological Sort) 순서를 거꾸로 따라감그래프에서 A → B 라는 건, A를 결정해야 B를 알 수 있다는 뜻이며 이게 위상 정렬 순서가 된다(A가 B보다 앞에 옴).근데 만약 우리가 A를 참(True)으로 정했는데, 이게 어찌어찌 흘러가서 A ⇒ ... ⇒ ¬A 라는 모순을 만들면 식이 성립할 수 없다.이런 모순을 피하는 가장 안전한 방법은, 함의 관계의 맨 끝, 즉 종착지부터 값을 정하는 것. 종착지는 위상 정렬 순서에서 가장 나중에 오므로, 위상 정렬의 역순으로 거슬러 올라가면서 값을 결정한다. 이렇게 하..

2-SAT - 3 (백준 11280번) SCC 알고리즘 문제를 풀다가 만난 또 다른 알고리즘인 2-SAT 기본 문제이다. 처음에 태그를 보지 않고, 2-CNF 식을 그래프로 만들어보려고 하루 이상을 고민했지만 비슷하게나마 접근하는데에 그쳤다. 2-SAT 문제에 대한 설명은 아래 블로그를 보고 공부했다. 2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)안녕하세요. 이번에 강의할 내용은 2-SAT(2-Satisfiability)이라는 좀 생소할 수 있는 내용입니다! 이...blog.naver.com먼저 명제를 단방향 간선들로 바꿔서 그래프를 만들어준 뒤, 타잔 알고리즘으로 SCC 구현을 한다. 이후, 각 변수에 대해 자신의 not 형 변수가 같은 SCC에 들어있으면..

도미노 (백준 4196번) 풀이 과정 SCC 변형 문제로 타잔 알고리즘으로 해결하였다.p배열을 구한 뒤, SCC 간 위상 관계를 생각해보면 사이클이 없는 트리처럼 생각할 수 있다. 이 트리의 root 개수를 구해주면 된다.타잔 알고리즘으로 각 연결 요소 집합(p배열) 구한다.각 vertex의 edge를 탐색하여 자신이 넘어뜨릴 수 있는 다른 도미노의 집합(B)이 자신의 집합(A)과 다르면 B는 다른 집합에 의해 넘어지는(root가 아닌) 도미노 집합임을 저장한다. (if (p[i] != p[next])vi_2[p[next]] = 1;)집합에 존재하는 모든 vertex가 다른 도미노에 의해 넘어지지 않는 집합(root)의 개수를 구한다. #include#include#include#include#inclu..