본문 바로가기

Probelm Solving42

BOJ1777 순열복원 1777번 순열복원 순열의 길이 N과 inversion sequence가 주어지면 이를 복원하여 원본 순열을 찾는다. inversion sequence의 i번째 원소 = 원본 수열에서 i보다 뒤에 위치하고 i보다 작은 수의 개수 i보다 작은 수의 개수를 알고 있으니, 큰 수부터 원본 수열에서의 위치를 찾아주면 된다. 주어진 예시로 파악해보자 (inversion sequence = 반전 수열이라고 하자) N=8, 반전 수열 = 0 1 0 2 2 1 2 0 1. 반전 수열의 여덟 번째 원소 0이 의미하는 바는 원본 수열에서 8보다 뒤에 위치하고 8보다 작은 수는 0개라는 뜻 따라서 원본 수열에서 8은 가장 마지막 위치에 있는, 여덟 번째 원소이다. ⇒ 원본 수열 = _ _ _ _ _ _ _ 8 2. 이제 반.. 2022. 8. 18.
BOJ2020 부분 염기서열 2020번 부분 염기서열 주어진 염기서열을 문자열로 볼 때, 문자열의 모든 부분 문자열에 대해 m번 이상 나타나는 부분 문자열의 개수를 구하고 1)길이 2)사전식 으로 나열했을 때 k번째의 부분 문자열을 구한다. 두 가지 방법이 있다. 1. BFS 2. Suffix, Prefix 활용 두 방법 모두 길이 순으로 부분 문자열을 찾는다는 게 그나마의 공통점인 듯 1. BFS 길이가 len인 어떤 문자열 s가 m번 이상 등장한 경우 문자열 s를 prefix로 하고 길이가 len+1인 문자열 s'를 찾아 탐색하면서 길이가 짧은 순으로 문자열을 탐색할 수 있다. 아래 두 자료구조를 사용한다. queue Q; map M; 먼저 길이가 1인 부분 문자열을 찾아야 한다. for (int i = 0; i < n; i++.. 2021. 8. 25.
2021 카카오 채용연계형 인턴십 ① #3 표 편집 간단해 보이나 효율성을 통과하기 위해 배열 외의 자료구조를 선택해야 했음 set을 이용한 풀이도 가능하지만 fenwick tree로도 풀 수 있다해 풀어봤다. 은근히 이분탐색에서 헷갈렸던;; 어떤 L을 찾는지 명확히 해야 헷갈리지 않는다. 시험 볼 당시에는 set을 활용하려 했으나 iterator 활용을 잘 못해 실패했던 것 같다... fenwick tree와 이분탐색을 이용함. 더보기 #include #include #include using namespace std; int N; stack S; int fen[1000001]; void upd(int idx, bool add) { if (add) while (idx 2021. 8. 18.
Lazy Propagation Lazy Propagation 배열의 구간 쿼리, 구간 합을 빈번하게 수행할 때 비교적 적은 횟수로 쿼리를 수행하는 방법 Segment Tree, Fenwick Tree 활용의 연장선에 있다. 배열 X에서 구간 쿼리를 수행하고 구간 합을 구할 때 한 개의 트리만 사용할 경우 구간의 길이만큼 쿼리를 수행해야 한다. 이때 추가적인 트리를 사용하면 쿼리를 적은 횟수 수행하고 두 트리를 모두 사용해 구간 합을 구할 수 있다. 0으로 초기화된 배열 X에서 다음 구간 쿼리를 수행한다고 하자. [4,9]에서 +6 [3,6]에서 -2 두 세그먼트 트리/펜윅 트리 a, b를 아래와 같이 이용할 수 있게 update하자. 구간 [1,4]의 합을 구하는 경우, [1,4] 내에서 6은 X[4]에, -2는 각각 X[3], X[.. 2021. 8. 13.
ETT 오일러 경로 테크닉, 근데 이제 펜윅을 곁들인 Euler Tour Technique 오일러 경로 테크닉 트리의 한 간선을 양방향 간선(or 반대 방향의 간선 두 개)로 생각한 뒤 루트에서 출발해 루트로 도착하는 그래프(트리)의 오일러 사이클을 찾는 것으로 트리를 표현하는 방식이다. * 오일러 사이클은 시작점=종점인 한붓그리기로 이해하면 됨 이렇게 144125566788997233 255667889972144133 255799887662331441 등... 트리가 주어지고 다음과 같은 쿼리가 주어진다고 하자. 1. i번 노드의 모든 하위 노드(자식, 자식의 자식...)의 값을 w만큼 증가한다. or i번 노드의 모든 상위 노드(부모, 부모의 부모...)의 값을 w만큼 증가한다. 2. i번 노드의 값을 출력한다. DFS로도 가능이야 하지만 트리의 깊이가.. 2021. 8. 5.
BOJ7812 중앙 트리 7812번 중앙트리 트리와 각 간선의 가중치가 주어질 때 한 꼭짓점에 대해 모든 꼭짓점과의 거리 합이 최소일 때의 그 값을 구한다. 즉 중앙 정점과 모든 꼭짓점과의 거리 합을 구한다. DFS, DP 당연히 모든 점에 대해 거리를 다 계산해볼 순 없고 트리이므로 DFS, 중앙 정점이 될 수 있는 점을 DP로 찾아가며 푼다. 처음에 DFS 두 번에 푸는 방법으로 해결했는데, 한 번만으로도 충분했다. 일단 간선은 벡터 E에 간선을 { 자식 노드 , 가중치 } 로 저장한다. DFS 두 번 하는 방법: 트리 먼저 만들고, 중심을 옮길지 말지 결정 0을 기준으로 모든 정점의 거리 합을 계산한 후 0보다 하위인 정점이 중앙 정점이 될 수 있는지 판단 1. 0에서 DFS, 모든 정점과 0사이의 거리 합 계산 이때 각 .. 2021. 7. 30.
BOJ2549 루빅의 사각형 2549번 루빅의 사각형 4×4 격자판이 있다. 행을 한 개 골라 아래쪽으로 k번(1≤k≤3) 움직이거나 열을 한 개 골라 오른쪽으로 k번(1≤k≤3) 움직이는 것을 한 번 움직인다고 한다. 격자판의 숫자가 주어질 때, 최소 횟수로 격자판을 움직여 1부터 16까지 순서대로 배열된 격자판으로 만드는 횟수(≤7)와 방법을 출력한다. 일단은, 되는대로 BFS를 돌려봤지만 역시 메모리 초과로 통과할 수 없었다. 한 번 움직이는 경우의 수는 8(행/열 개수)*3(k 개수)였고 아무리 정답이 7번 이내로 나온다 해도 24^7개의 경우를 확인하려니 당연히,, 몇 가지 최적화로 가짓수를 줄여봤지만 그래도 메모리초과였다. 방법 1. BFS + 양방향 탐색 + map BFS로 찾되 양방향으로 탐색하기로 했다. 주어진 상태.. 2021. 7. 25.
BOJ3830 교수님은 기다리지 않는다 3830번 교수님은 기다리지 않는다 1번부터 N번까지의 샘플에 대해 두 샘플의 무게 차이 정보가 주어질 때 교수님이 요구한 두 샘플의 무게 차를 구할 수 있으면 출력하고 구할 수 없으면 UNKNOWN을 출력한다 Disjoint Set Union & Find를 이용하는 문제인데 edge에 cost가 있다. 분리집합 문제는 여러 개 풀었었는데 가중치가 있는 건 처음 풀어봐서 꽤 헷갈리고 오래 걸렸다. scanf,printf보다 cin,cout이 훨씬 빠르고 편했다. par[N] N개 샘플의 부모 (set number) w[N] N개 샘플의 set 내 무게 (부모 무게를 0으로 했을 때의 무게) ! a b c : b가 a보다 c그램 무겁다. a와 b를 union한다. 1. a,b의 부모 para,parb를 구.. 2021. 6. 19.
BOJ1949 우수 마을 1949번 우수 마을 N개의 마을로 이루어진 트리 형태의 나라에서 우수 마을인 두 마을이 인접하지 않고 우수 마을이 아닌 마을은 적어도 한 우수 마을과 인접해야 할 때 우수 마을로 선정된 마을 주민 수의 최댓값을 구한다. Tree + DP 2535번과 비슷하다. 다만 2535번에서는 v가 선택될 때/아닐 때 두 가지만 고려하면 됐는데 여기서는 v의 자식노드까지 생각해야 한다. 좀 더 상위버전인 듯. 우수마을을 선정하는 조건을 파악하자 1. 우수 마을인 두 마을이 인접하지 않는다. v가 우수마을이면 v의 모든 자식 노드는 우수 마을이 될 수 없다. 2. 우수마을이 아닌 마을은 적어도 한 우수 마을과 인접하다. v가 우수마을이 아니라면 v의 자식 노드 중 하나가 우수 마을이거나, v의 부모 노드가 우수 마을.. 2021. 6. 10.
DP (1) Dynamic Programming 다이나믹 프로그래밍 BOJ1028 다이아몬드 광산 R*C 크기로 주어진 광산에서 가장 큰 ◇ 모양의 다이아몬드의 크기(한 변의 길이)를 구한다. ↖,↗ 방향으로 연속한 1의 개수를 구하고 다이아몬드의 아래 꼭짓점을 기준으로 최대 다이아몬드 크기를 구한다. dp[ i ][ j ][ 0 ] ( i , j )기준 ↖방향으로 연속한 1의 개수 dp[ i ][ j ][ 1 ] ( i , j )기준 ↗방향으로 "" 이때 아래 꼭짓점이 ( i , j )이고 크기가 k+1인 다이아몬드가 존재하려면 아래 조건을 만족해야 한다. dp[ i ][ j ][ 0 ] > k dp[ i ][ j ][ 1 ] > k dp[ i-k ][ j-k ][ 1 ] > k dp[ i-k ][ j+k ][ 0.. 2021. 6. 10.

티스토리툴바