devbelly

문제 https://www.acmicpc.net/problem/1777 알고리즘 세그먼트 트리 풀이 Inversion counting 문제입니다. 각 숫자의 inversion의 개수가 주어졌을 때, 원래 순열을 구하는 문제입니다. 예제 입력에서 주어지는 inversion의 개수를 풀어서 설명하자면, 나보다 작은 숫자가 뒤에 몇 개나 있느냐를 의미합니다. 순열의 총 크기를 안다면, 나보다 작은 숫자가 앞에 몇 개가 있는지 또한 구할 수 있습니다. 이는 $k$번째가 어디에 위치한 지를 묻는 쿼리와 동등합니다. 이때 여러전략을 선택할 수 있지만, 숫자를 올바른 곳에 배치했다면 해당 인덱스를 제외해야 하므로 삭제 연산 또한 가능한 펜윅트리를 사용했습니다. 시간 복잡도는 $O(NlogN*logN)$입니다. 코드 ..

문제 https://www.acmicpc.net/problem/1655 알고리즘 우선순위 큐 풀이 유명한 우선순위 큐를 활용하는 문제입니다. $N$개의 숫자들이 차례대로 주어질 때, 한 개씩 주어질 때마다 중앙값을 계속해서 출력하는 문제입니다. 여러 가지 풀이를 통해 해결 가능 하지만 우선적으로 생각나는 풀이는 트립을 활용하는 것입니다. 문제에서 요구하는 핵심 쿼리인 원소의 추가와 $k$번째 원소(여기서는 중간) 값을 찾는 쿼리를 $O(logN)$에 해결 가능하기 때문입니다. 하지만 구현이 복잡하므로 다른 풀이를 생각해보도록 합시다. 수열이 주어진 상태에서 반을 나누어 작은값부터 중간까지는 최대 힙에 중간부터 가장 큰 값까지는 최소 힙에 담도록 합시다. 이렇게 한다면 수열이 반으로 나뉜 상태긴 하지만 계..

문제 https://www.acmicpc.net/problem/9426 알고리즘 세그먼트 트리 풀이 $N$초동안 온도를 기록하는데 최근 $K$초의 중앙값들을 모두 더하는 것을 요구하는 문제입니다. 이 문제의 경우는 이전의 값을 삭제하는 연산 없이 계속 추가한 후 중앙값만 처리하면 되므로 최대 힙, 최소 힙 두 개로 $O(NlogN)$에 해결 가능했으나, 가장 최근$K$초의 중앙값만을 계속 구해야 하므로 최근 K초를 제외한 온도를 삭제할 수 있는 자료구조인 세그먼트 트리를 활용하겠습니다. 문제에서 요구하는 핵심쿼리는 중앙값 처리입니다. 트리에서의 인덱스는 온도를 의미합니다. 온도의 개수를 누적시킨다면, 인덱스에 따라 값들이 오름차순으로 정렬되어 있으므로, 이분 탐색을 통해 중앙값을 빠르게 처리할 수 있습니..

문제 https://www.acmicpc.net/problem/1493 알고리즘 분할정복, 그리디 풀이 박스를 큐브로 채워나갈 때, 필요로 하는 큐브의 갯수를 최소화 하는 문제입니다. 단 큐브의 사이즈는 2의 제곱형태로만 주어지는 제약이 있습니다. 큐브길이가 2의 제곱형태로만 주어지는 점부터 살펴봅시다. 만약 이렇지 않았다면, 모든 큐브를 일일히 넣어보는 완전탐색을 해야합니다. 하지만 모든 길이가 배수와 약수 관계를 유지할 때, 무조건 큰 길이부터 넣는 그리디한 전략을 사용할 수 있습니다. 큰 길이의 큐브를 넣어야만 갯수를 최소화 할 수 있고, 예를들어 4x4x4큐브를 사용했다면 굳이 2x2x2큐브들로 그 자리를 대체할 이유가 없죠. 살펴보아야 할 점 중 또 한가지는 큐브길이는 제곱형태로 주어지지만 박스..

문제 https://www.acmicpc.net/problem/3108 알고리즘 Union-Find 풀이 좌표평면 위 사각형들이 주어졌을 때, (0,0)에서 시작하여 PU명령을 몇 번 해야 하는지 묻고 있습니다. 거북이는 (0,0)에 펜을 내리고 있는 상황입니다. 문제에서 주어진 예제를 그려본다면 (5,0) 과 (8,3)으로 이루어진 사각형을 제외하고는 모든 사각형이 이어져있음을 알 수 있습니다. PU명령이 필요할 때는 이어져 있지 않은 사각형을 그리러 갈 때입니다. 즉 사각형들이 이어져 있다면 하나의 그룹으로 카운트를 할 수 있는 유니온파인드를 사용합시다. 이중 포문을 통해 모든 사각형들이 겹치는지 안겹치는지를 확인하는 과정에서 겹친다면 유니온을 진행합니다. 유니온의 기준은 인덱스 번호가 큰 쪽으로 유..

문제 https://www.acmicpc.net/problem/2104 알고리즘 분할정복 풀이 유명한 분할정복 문제입니다. $N$제한을 고려하지 않은 채 문제를 풀어보도록 합시다. 이중 포문을 통해 모든 i, j에 대하여 문제에서 요구하는 값을 $N^2$에 해결할 수 있습니다. 하지만 이 문제의 $N$제한은 100000이므로 제곱을 하게 되면 시간초과를 면할 수 없습니다. 문제 제한을 통해 log임을 느낄 수 있습니다. $O(NlogN)$은 시간제한 1초 안에 들어올 수 있는 복잡도입니다. 분할정복으로 해결해보도록 합시다. 분할정복을 처음 접할 때 가장 어려운 부분 중 하나는 재귀를 다루는 부분입니다. 재귀함수를 작성할 시 아직 함수를 다 작성하지 않았음에도 불구하고 작동할 것이라는 믿음을 갖고 작성해야..

문제 https://www.acmicpc.net/problem/9202 알고리즘 트라이 풀이 격자판에서 주어진 문자열을 조건에 따라 찾아야 하는 문제입니다. 최대 점수, 찾은 단어의 개수, 가장 긴 단어를 구하기를 원하고 있습니다. 단어의 개수를 찾는 과정에서 최대 점수와 가장 긴 단어 또한 해결 가능하므로 단어를 찾는 것에 집중합시다. 격자판 위에서 단어를 탐색해야 하므로 DFS를 통해 일차적인 접근이 가능합니다. DFS연산량만 어림짐작해보면 (주어지는 보글의 수) X (4x4 격자판에서 DFS시작 가능한 위치의 개수) X (DFS의 깊이에 해당하는 단어의 길이) X (각 알파벳마다 가능한 선택지의 수) 이고, 이는 대략 3천만에 가까운 숫자입니다. 즉 단어를 선형 시간 안에 찾지 않게 되면 시간 초과..

문제 https://www.acmicpc.net/problem/5009 알고리즘 2-SAT, 이분탐색 풀이 우리가 결정해야 할 것은 아이들의 호감리스트를 반영한 아이들의 반 배정입니다. 언뜻 보면 선생님이 3명이여서 아이들이 결정해야할 선생님이 세 사람 같아 보이지만 실제론 두 사람입니다. 이유는 작년에 담당했던 선생님은 선택사항이 아니기 때문입니다. 문제 조건중 "반에 속하는 모든 학생은 학생들이 좋아하는 순서에서 상위 T위 안에 있어야 한다."는 달리 말해서 T위를 초과하는 학생과는 다른 반이 되어야 함을 의미합니다. 다른 반으로 배정하기 위해선 두 학생의 이전 선생님이 누구인지 알아야 하며, 이에 따라 반배정을 진행해주면 됩니다. 각 선생님 번호가 0 , 1 , 2라고 할 때, T(x)는 이전 선생..