본문 바로가기

전체 글

 (160)
[백준 2243] 사탕상자 세그먼트 트리 문제다. 수정이 빈번하게 일어나는 구간 쿼리 문제는 대부분 세그먼트 트리로 해결할 수 있는 것 같다. 구간 값 update 함수는 일반적인 세그먼트 트리와 같고 query 함수를 조금 신경 쓸 필요가 있다. 문제에서 요구하는 것은 특정 구간 합 그 자체가 아니라, 꺼내야 하는 사탕의 맛 값이다. 따라서 왼쪽 자식 노드 값, 그러니까 현재 구간 중에서 앞쪽 절반 구간에 존재하는 사탕 수 합이 쿼리하는 값 이상이라면, 해당 구간에 대해 쿼리를 이어나가면 된다. 반대로 앞쪽 절반 구간에 존재하는 사탕 수가 불충분하다면, 당연히 오른쪽 자식을 이용해야 한다. 이때, 주의해야 할 것은 쿼리하는 값을 그대로 사용하면 안 된다는 것이다.  전체에서 b번째 맛을 꺼내야 하므로, 앞쪽 구간의 사탕 수만큼을..
[백준 15824] 너 봄에는 캡사이신이 맛있단다 조합론과 분할 정복 기반 거듭제곱을 응용한 문제다. Large 케이스에서 N이 최대 300,000까지 들어올 수 있고, 모든 조합을 하나하나 고려한다면 지수시간에 해당하는 시간 복잡도를 가지기 때문에 브루트 포스는 사용할 수 없다. 하지만, 문제를 잘 생각해 보면 알 수 있듯이 주헌고통지수라는 것은 특정 조합에서의 최댓값과 최솟값만 있어도 구해낼 수 있다. 그리고 모든 메뉴를 스코빌 지수 기준으로 정렬해 둔다면, 어떤 메뉴가 최댓값이 되는 경우와 최솟값이 되는 경우를 바로 구해낼 수 있다.   만약 예제 2번의 경우에서, 6이 최댓값이 되는 경우를 생각하면 위처럼 생각할 수 있다. 6은 조합에 포함되어야 하고, 10은 포함되어서는 안 된다. 그리고 나머지 더 작은 수들에 대해서는 조합 내 포함여부가 6이..
[백준 16565] N포커 수학에 기반한 문제이다. N이 최대 52까지 들어올 수 있으므로 완전 탐색과 백트래킹을 사용하는 것은 불가능하다. 러프하게 잡아도 52! 회의 탐색 과정이 필요하고, 최적화하더라도 52C26 회의 탐색은 필요하기 때문이다.  처음에는 대수적으로 일반화시킬 수 있는 식이 존재하지 않을까 싶어서, 방정식을 찾으려 애쓰다가 그건 찾지 못해서 조합론을 사용하기로 했다. 구해야 하는 것은 플레이어가 이기는 수이므로, 그 조건인 포카드의 형성을 달성하는 조합만 찾아 모두 더하면 된다. 가령 5장을 뽑았을 때, 플레이어가 이기는 수를 생각하자면 포카드 형성에 소모되는 4장을 제외하고 남은 모든 카드 중에 1장을 고르는 경우가 된다. 이때, 포카드가 A부터 K까지 13종류가 형성될 수 있으므로 결국 13 * 48C1이..
[백준 17401] 일하는 세포 분할 정복으로 행렬의 거듭제곱을 구하는 문제. 문제를 유심히 보다 보니, 예전에 풀었던 본대 산책2 문제와 상당히 비슷했다.  [백준 12850] 본대 산책2  [백준 12850] 본대 산책2수학과 분할 정복을 이용하는 문제. D의 크기가 최대 1,000,000,000이기 때문에 O(n)인 DP로 해결하려고 해도 시간초과가 날 것이다. 그래서 다른 방법을 생각해보아야 한다.  먼저 특정 건물 i에서winterry.tistory.com  물론 이번에는, 인접 행렬이 특정 사이클에 따라 바뀐다는 것이 달랐지만 큰 틀에서는 달라질 게 없었다. 특정 노드 i에서 j로 이동할 수 있는 경우의 수가 결국 행렬 곱 matrix[i][j]를 구한 것과 같다는 점에서 시작한다. 따라서 두 행렬의 곱을 구하는 함수를 만들..
[백준 30805] 사전 순 최대 공통 부분 수열 구현 문제다. 그리디나 완전 탐색이라고 생각해도 될 것 같다. N과 M의 범위가 상당히 작기 때문에 어떻게 풀어도 풀린다. 처음엔 DP스럽게 접근하려고 배열만 이용해서 풀었는데, 조건 처리가 많아서 지저분해 보이는 것이 마음에 안 들었다.  원리는 간단한데, 핵심 부분은 O(n^2)인 LCS 알고리즘과 유사하다. 배열 A를 선형 탐색하는 루프 내에서 배열 B를 선형 탐색한다. 이때, 값이 일치하는 경우를 찾았다면 lcs 배열을 앞에서부터 선형 탐색하며, 현재 일치하는 값보다 작은 배열 원소가 있는지 확인한다. 그런 원소가 있다면 현재 일치하는 값으로 갱신해 주고, 아니라면 lcs 배열 끝에 붙일 수 있는지 확인해서(마지막 원소에서 사용한 배열 B 인덱스보다 현재 일치된 값을 가지는 배열 B 인덱스가 큰 ..
[백준 13334] 철로 자료 구조 문제다. 잊을만하면 접하게 되는 유형인데, 처음에 우선순위 큐가 아닌 일반 큐를 사용했다가 가차 없이 틀렸습니다를 받아서 좀 당황했다. 이후 우선순위 큐로 바꾸고 바로 통과할 수 있었다.  입력받는 데이터의 양을 보면 알 수 있듯이, 모든 좌표를 시작점으로 해서 탐색해 보는 브루트 포스를 이용하면 시간 초과가 난다. 하지만 조금 생각해 보면 굳이 모든 지점을 확인할 필요는 없음을 알 수 있다. 정수 쌍이 많아봐야 100,000개고 그 정수 쌍에 나타나는 필요한 좌표들만 확인하면 되는 문제다.  먼저 기준점 하나가 고정되면 철로의 길이를 이용해서 유효한 범위는 확정할 수 있으므로, 기준점을 정해 데이터셋을 정렬한 다음에 기준점이 변경될 때마다 그에 맞게 처리하면 되겠다고 생각할 수 있다. 나는 ..
[백준 11438] LCA 2 LCA(Lowest Common Ancestor, 최소 공통 조상) 문제. 어제 풀었던 것보다 좀 더 심플한 유형으로, 순수하게 LCA만 쿼리한다.   노드의 수가 최대 100,000개까지 입력될 수 있고, 쿼리 또한 100,000개까지 들어올 수 있기 때문에, LCA 탐색에는 O(log N)인 알고리즘을 사용해야 한다. 어제처럼 Sparse Table을 사용하여 풀었는데, Sparse Table을 생성하는 dfs 내부의 로직을 조금 변경했다. 크게 보면 로직은 같은데, 어제의 경우처럼 테이블에 여러 데이터를 저장하는 게 아니므로 좀 더 심플하게 바꿀 수 있었다.  원리는 어제 설명했듯이, LCA를 찾아나갈 때 부모 노드를 통해 일일이 찾아가는 것이 아니라, 각 노드 별로 2^k번째 조상을 모두 저장해 ..
[백준 1761] 정점들의 거리 LCA(Lowest Common Ancestor, 최소 공통 조상) 문제다. 모든 노드에 대해서 조상 노드들까지의 거리를 전처리 해두고, LCA를 찾아 그 거리를 합하면 될 것이라고 쉽게 생각할 수 있다. 대신에 Biased Tree일 경우, 트리의 깊이가 N이 될 수 있고 그렇게 되면 LCA를 찾아내는 알고리즘이 O(트리 높이)인 경우, 전체 시간복잡도가 O(NM)이 되어 시간초과가 발생할 것이다. 풀고 나서 찾아보니까 테스트 케이스가 잘못되었는지 O(N)인 LCA 알고리즘으로도 풀린다고 하지만 문제의 의도와 맞지 않는 풀이라고 생각한다.  LCA를 O(log N)만에 찾을 수 있는 알고리즘은 Sparse Table을 사용하는 것이다. n번째 노드라는 것은 이진수를 떠올리면 알 수 있듯이, 2^k 조합..

티스토리툴바