dh_0e

Strongly Connected Component (백준 2150번) Strongly Connected Component(강한 연결 요소) 알고리즘 기본 문제. 모르고 풀이를 떠올렸을 때, dfs로 비슷하게까지는 생각했는데, 알아보니 타잔 알고리즘이나 코사라주 알고리즘을 사용해야 했고, 비교적 간단한 타잔 알고리즘을 사용해 풀었다. id를 사용해서 깊이만큼 초기값을 가지는 것, 다음 vertex의 id값을 받아서 내 parent 값보다 작으면 갱신한다는 부분이 킥이었다.아래 블로그에 두 알고리즘을 자세히 설명되어있다. SCC - 강한 연결 요소 찾기강한 연결 요소 (SCC, Strongly Connected Component) 란, 유향 그래프에서 정점의 부분집합이 부분집합 내의 다른 모든 정점에 대해..

거의 최단 경로 (백준 5719번) 다익스트라로 최단 거리를 구하면서 경로를 역추적해서 최단 거리의 간선들을 모두 삭제한 뒤, 다시 다익스트라로 두 번째 최단 거리를 구하는 문제. 구현과 반례 찾는데에 꽤나 어려움을 느꼈고, 결과도 틀렸습니다, 시간 초과가 아닌 메모리 초과가 나와서 콜 스택이 터진건지 내가 모르는 메모리 관리 방법이 있는건지 디버깅 하다가 결국엔 로직 오류를 찾아서 해결했다.. 풀이 과정 다익스트라로 최단 거리를 구하면서 before_node에 해당 node로 최단 거리만에 갈 수 있는 node들을 저장해준다. 이때, 새로운 최단 거리가 나오면 before_node를 clear한 뒤, 다시 node를 저장한다. 최단 거리로 도착할 수 있는 node가 중복으로 나온다면 해당 node 또한..

도로 네트워크 (백준 3176번) LCA 2(백준 11438번)처럼 희소 배열을 이용한 최소 공통 조상(Binary Lifting) 알고리즘을 활용한 문제. [PS] LCA 2 / C++ (백준 11438번)희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfdh-0e.tistory.com구현이 꽤 복잡하지만 설계를 잘 하고, LCA를 적절하게 구현하면 쉽게 풀 수 있다. #include#include#includeusing namespace std;vector> vec[100001];int depth[100001],..

LCA 2 (백준 11438번) 희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfs()함수로 트리를 만들며 각 node들의 parent 정보를 희소 배열에 저장하는데 이때, 희소 배열을 2차원으로 parent[i][j]=i번째 node에서 $2^j$번째 부모를 저장하는 방식으로 만들어준다. N 2. depth 배열을 만들어 각 node들의 깊이 또한 저장해준다. 주요 식은 다음과 같다.parent[i][j]=parent[parent[i][j-1]][j-1]; 3. 다음 입력받은 두 노드의 깊이를 맞춰준다. 이때, 2..

수열과 쿼리 16 (백준 14428번) 읽자마자 세그먼트 트리가 떠올랐던 문제. 값이 아닌 인덱스를 출력하는 문제이기 때문에 세그먼트 트리를 적절히 변형하여 풀어야 한다. 풀이 과정 값과 인덱스 모두 저장해야 하기 때문에 tree[] 배열을 pair로 선언해주고, 모든 함수 또한 return 값을 pair로 하여 세그먼트 트리를 구현해주면 된다. pair init(int start, int end, int node): 세그먼트 트리를 만드는 함수로 기존 세그먼트 트리 로직에 최솟값과 그 인덱스를 pair로 가져오게끔 수정하면 된다. 이때, 최솟값이 같을 경우 인덱스가 작은 것을 출력하기 때문에 조건문은 if(left_node.firstright_node.first)tree[node]=left; 가 된다..

교수님은 기다리지 않는다 (백준 3830번) 분리 집합을 떠올리는데는 큰 어려움은 없었지만 가중치 관리하는 수식을 세우기가 조금 힘들었던 문제 풀이 과정 분리 집합 알고리즘을 구현한 뒤 경로 압축을 해준다(find_root() 함수). _union() 함수에 알맞은 수식을 넣어 가중치를 갱신하게끔 하면 된다. find_root(node): node의 최종 root를 찾은 뒤, 경로 압축으로 최적화 실행_union(a, b, w): a에서 b로 가는 가중치가 w라고 했을 때, a의 최종 root(pa_a)와 b의 최종 root(pa_b)를 각각 구하여 가중치를 갱신parent[pa_a.first] = pa_b.first; // a의 최종 root(pa_a.first)의 최종 root(parent[pa_a...

컨닝 (백준 1014번) dfs로 풀면 시간 초과 이므로, 다른 풀이를 떠올려야 하는데 그 부분이 너무 막막했던 문제. 풀이과정 비트필드를 이용한 dp로 풀면 된다.m(가로) 길이에 맞게 자리에 앉을 수 있는 모든 경우의 수를 비트 마스크로 생성한다.{0, 1}, {0, 1, 10}, {0, 1, 10, 100, 101}, {0, 1, 10, 100, 101, 1000, 1001, 1010}과 같이 피보나치 수열로 증가세를 띄며, 가로 길이가 최대인 10일 경우 144가지 경우의 수가 있다.이를 b_mask에 저장하고 점화식을 'dp[i][j]=i번째 줄에서 b_mask[j]의 비트 값으로 앉을 때, 최대로 앉을 수 있는 인원'으로 세운다.첫 줄의 dp 값은 b_mask의 1의 개수로 저장한다.두 번째 ..

콘서트 (백준 34056번) UCPC 예선 E번 문제로 느린 세그먼트 트리로 풀어야할 것 같은데 남은 시간 안에 구현할 엄두가 안 났던 문제. 풀고 나서야 O(NQ)는 절대 시간초과라는 편견을 안 하게 되었던 교훈적인 문제였다. 풀이과정놀랍게도 N, Q가 200,000이지만 $O(NQ)$만에 해결이 가능하다. 방음벽이 소음을 모두 흡수하지 못하면 방음벽의 성능이 2배가 된다. 하지만 소음의 최대 크기가 $10^9$이기 때문에, 어림잡아 $2^{30}$ 이하라는 소린데 이는 한 방음벽이 30번 정도만 흡수를 못 해도 이후엔 모든 소음을 흡수할 수 있게 된다는 소리이다. Q가 200,000이라 평균적으로 탐색 로직이 500번 이하로 나오면 시간안에 Ac가 나올 수 있는데, 이 문제에선 평균 탐색 길이가 지수..

연산 추가하기 (백준 34055번) UCPC 예선에서 팀원이 푼 문제로 당시 팀원이 설명한 발상을 그대로 가져갔고, 마지막에 누적합, 이진 탐색 처리식을 다르게 풀었다. 풀이 과정각 구간들을 제외한, 연산이 추가될 수 있는 연속된 사이클 수를 모두 구해놓고 이를 정렬한 뒤, 누적합을 구해놓는다. 예제 1을 예로 들면 연산이 추가될 수 있는 부분은 (1~4), (9~11), (24~30) 3구간이며 각각 4, 3, 7 사이클이다. 이를 정렬한 뒤, 누적합을 구하면 3, 7, 14가 된다. 각 시나리오에 대한 정답은 정렬한 배열에서 이분 탐색으로 Qi 이상의 값이 처음 나오는 index를 구해서(lower_bound) 다음 식을 사용하면 구할 수 있다. cy[i]: 구간별 연속된 사이클들을 정렬한 배열v[i..

로봇 청소기 (백준 34060번) UCPC 예선에서 발상을 잘못해서 다 구현해놓고 실수로 분리 집합을 빼먹어서 시간 내에 풀지 못했던 문제.대회 끝나고 처음부터 다시 풀어보는데 union-find를 함수 없이 구현해보려다 몇 번 틀렸다. 풀이 과정 오염 영역의 최댓값은 n이 200,000까지이고 격자의 크기가 $10^9$x$10^9$이기 때문에 n값을 그대로 출력해주면 되며, 오염 영역의 최솟값만 구하면 되는 문제이다. 최솟값을 구하는 로직을 greedy하게 생각하면, d[i]가 d[i-1]보다 크다면 다음 줄로 넘기지 않고, d[i-1]보다 작거나 같을 때만 다음 줄로 넘기게끔 하면 항상 오염 영역을 가장 많이 줄일 수 있다. prevQue: 이전 줄의 index들 저장하는 QueuerecQue: 현..

1의 개수 세기 (백준 9527번) A, B가 $10^{16}$까지 이므로 $O(logn)$에 해결해야 한다.$O(n)$은 무조건 시간초과. 풀이 과정2진수에 나타나는 1의 개수를 구해보면 패턴을 찾을 수 있다.1{1}, 2~3{1, 2}, 4~7{1, 2, 2, 3}, 8~15{1, 2, 2, 3, 2, 3, 3, 4} 까지만 봐도 패턴이 보인다.d[i] = $2^i$ ~ $2^{i+1}-1$에서 1의 개수라고 했을 때 점화식은 $d[i]=d[i-1]*2+2^{i-1}$로 구할 수 있으며 이를 각 구역으로 봤을 때, 각 구역별로 절반씩 나눠보면 똑같은 패턴인 것이 확인된다.8~15{1, 2, 2, 3, 2, 3, 3, 4}를 반으로 나누면 8~11{1, 2, 2, 3}, 12~15{2, 3, 3, 4}..

후위 표기식 (백준 1918번) stack, vector를 사용해서 문제를 적절히 구현하면 되는 자료구조 문제(((A+B)))같은 식은 안 나올 줄 알고 처리를 안 해놨다가 런타임 에러 받자마자 직감하고 처리해줬다. 풀이 과정중위 표기식에 괄호 씌우기*, / 먼저 찾아서 수식의 위치를 make_pen 함수에 매개변수로 보낸다.+, - 도 찾아서 똑같이 make_pen 함수를 돌려준다.make_pen()은 찾은 수식의 위치를 매개변수로 받아 좌, 우로 식을 찾는다. 식은 알파벳 하나 또는 괄호로 이루어진 식으로 좌, 우의 식에 양 옆에 괄호가 이미 있다면 return, 한쪽이라도 괄호가 없다면 괄호를 삽입한다.수식과 대응되는 괄호 찾아 후위 표기식으로 만들기'('는 st_op 스택에 위치를 저장알파벳은 p..

공항 (백준 10775번) 문제를 읽고 생각해 보면 greedy 문제라는 것은 쉽게 알 수 있다. 하지만 매번 gi~1까지 빈 출구를 찾으면서 greedy 하게 도킹하게 되면 G, P 풀이 과정분리 집합을 사용하여 그리디하게 출구들을 도킹시키면 $O(N)$만에 풀 수 있다. 도킹이 끝난 출구들이 연결되어 있을 때 한 집합으로 보고 연결해 준다.i번 출구를 도킹시켰을 때, i-1 출구가 비어있으면 새로운 집합(i-1이 도킹할 수 있는 가장 큰 번호의 출구인 집합)을 만들어준다.i-1 출구가 비어있지 않다면, i-1 출구의 집합에 포함시킨다.1번 출구가 포함된 집합은 더 이상 포함될 집합(i-1이 0이기 때문)이 없기 때문에 1번 출구에 -1을 저장해 주고, union_find에서 이미 도킹된 1번 출구까..

뱀과 사다리 게임 (백준 16928번) BFS로 풀 수 있는 간단한 문제greedy 방식이 왜 항상 최적의 값을 찾을 수 없는지 알려주기 좋은 문제같다. #include#include#includeusing namespace std;int d[101], vi[101];queue> que;int f(int cur, int c) { for (int i = 1; i pa = que.front(); que.pop(); if (pa.first == 100) { printf("%d\n", pa.second); break; } f(pa.first, pa.second); } return 0;}

너 봄에는 캡사이신이 맛있단다 (백준 15824번) 조합론이 기본이 되는 문제로 계산식 발상에 좀 애먹은 문제결론적으로 메뉴들을 맵기 순으로 정렬하면, 메뉴마다 가장 높은 수치, 낮은 수치일 경우의 수가 정해져 있으므로 각각의 메뉴마다 경우의 수를 조합론으로 구해 계산해주면 된다. 풀이과정한 메뉴가 포함되는 조합의 수는 총 $2^{n-1}-1$가지이다.하지만 스코빌 수치가 이용되는 경우만 따지면 되기 때문에 i번째 메뉴가 가장 높은 스코빌 수치일 때와 가장 낮을 때만 구해주면 된다. 식으로 나타내면 다음과 같다. (i가 0~n-1일 때)가장 높은 스코빌 수치일 경우 >> $2^i-1$가장 낮은 스코빌 수치일 경우 >> $2^{n-i-1}-1$i번째 메뉴보다 높거나 낮은 스코빌을 선택할 때 모두 선택하지 ..

박성원 (백준 1086번) 비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 .. 시행 착오 vector > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다. 해결 방안갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장ten_mod에 10^l 들을 k..

두 배열의 합 (백준 2143번) 누적 합과 이분 탐색으로 쉽게 풀 수 있는 문제lower_bound, upper_bound 오랜만에 직접 구현해보다가 결국 귀찮아서 라이브러리에 있는 거 썼다.. 풀이 과정누적 합으로 A, B 배열의 부 배열의 합이 될 수 있는 경우의 수를 모두 vector에 저장해준다. (최대 500500 경우의 수)둘 중 하나를 sort 해준다.upper_bound - lower_bound로 target(t - vec_a[i])이 몇 개나 있는 지 구해서 dap에 더해준다.dap은 int 범위를 넘을 수 있으므로 long이나 long long으로 처리해준다.못 찾았을 경우 up, lo 모두 end() 저장소의 위치를 가르키므로 예외처리 안 해줘도 0을 더한다. #include#inc..

GCD(n, k) = 1 (백준 11689번) 1~$10^{12}$ 범위인 N과 서로수인 수의 개수를 구하는 문제 깡으로 하면 무조건 시간 초과이므로 오일러 피 함수의 성질을 이용해서 풀 수 있다. 시행 착오에라토스테네스의 체로 소수를 모두 구별하여 N을 소인수분해 한 뒤, 오일러 피 함수의 성질을 이용하여 답을 도출하는 식으로 구상했지만, $10^{12}$ 이하의 가장 큰 소수가 999999999989이므로 당연히 메모리 초과가 나왔다. 풀이 과정사실 2부터 시작해서 N의 값을 나눌 수 있을 때까지 나누면 소수를 따로 구할 필요없이 소수로만 나눌 수 있다.나눌 때마다 오일러 피 함수의 성질을 이용하여 변수를 지정해 곱해놓으면 답을 구할 수 있다. ※ N=99처럼 sqrt(N)보다 N의 약수(11)가 ..

철로 (백준 13334번) 정렬과 priority queue만 적절히 사용할 줄 알면 쉽게 풀리는 문제 사람들의 집과 사무실의 위치는 바뀌어도 상관 없으므로 first 값이 작도록 설정한 뒤, second 값을 기준으로 오름차순 정렬해줌 (second 값이 같을 경우 first 값 오름차순으로)차례대로 우선순위 큐 top에 있는 사람을 기준으로 범위 안에 들어가는 지 확인O: 우선순위 큐에 i번째 사람 추가, 범위 안에 있는 사람 수가 max인 지 확인X: 범위 안에 들어갈 때까지 top에 있는 사람을 pop해줌 #include#include#includeusing namespace std;pair d[1000001];priority_queue > prique;bool cmp(const pair & a..

N포커 (백준 16565번) 조합론의 포함 배제의 원리를 사용하여 포카드가 나올 경우의 수를 구하는 문제dp[N][K] = N장의 카드를 뽑을 때, K개의 포카드 세트가 나올 수 있는 경우의 수를 저장하는 형식으로 1~N까지 차례로 구하며 dp로 풀 수 있을 것 같아서 5시간 동안 점화식을 찾았다... 풀이 과정결론적으로 이 전의 경우의 수는 관계 XN개의 카드를 뽑을 때, K개의 포카드 세트가 나왔다고 고정한 뒤, 나올 수 있는 경우의 수를 구한다.식: $cmp = {_{13}C_K} + {_{(52 - k \times 4)}C_{(N - K \times 4)}}$K를 1~N/4까지 구해준 다음, 포함 배제의 원리에 의해서 홀수번째는 더해주고, 짝수번째는 빼주면 N개의 카드를 뽑을 때 포카드가 나올 경..