본문 바로가기

Dev

 (90)
[백준 1922] 네트워크 연결 최소 스패닝 트리 문제. 가장 심플한 형태의 MST 문제라서 포스팅을 작성하지 않으려다가, 그래도 MST를 처음 접하는 사람들에겐 연습하기 좋은 문제인 것 같아서 들고 왔다.  각각의 컴퓨터를 노드로 생각하고, 무방향 가중치 그래프의 부분 그래프로 모든 노드가 연결되도록 했을 때 그 간선 비용의 총합이 최소가 되어야 한다. 이런 유형의 문제는 대부분 MST 문제인 경우가 많다. MST는 Kruskal 알고리즘이나 Prim 알고리즘으로 해결하게 되는데 간단하게 차이를 정리하면 아래와 같다.  Kruskal 알고리즘- 모든 간선을 비용 기준으로 정렬하여, 사이클이 되지 않도록 간선을 하나씩 스패닝 트리에 추가하는 방법.- 사이클에 대한 판정은, 새로 추가하려는 간선의 두 노드가 스패닝 트리 내에서 이미 하나..
[백준 14428] 수열과 쿼리 16 최근에 프로그래머스 문제들을 몰아서 푸느라 백준에서는 매일 간단한 문제만 하나씩 풀었는데, 오랜만에 좋은 문제를 만났다. 문제를 읽으면 바로 느껴지겠지만 세그먼트 트리 문제다. 다른 부분은 일반적인 세그먼트 트리를 이용한 문제와 다를 바가 없지만, 주의해야 하는 부분은 쿼리의 결과로 최솟값이 위치한 인덱스를 출력해야 한다는 것이다. 따라서 세그먼트 트리에 값으로 최솟값만 저장할 게 아니라 최솟값이 위치한 인덱스를 함께 저장하는 방법으로 접근했다. 그리고 문제 조건에서 최솟값이 구간 내에 여러 개 있을 경우 가장 작은 인덱스를 출력하도록 되어있으므로, C++ 기준 pair를 이용하되 {최솟값, 인덱스} 순서로 배치해서 비교 연산을 수월하게 했다.  위 내용을 토대로 세그먼트 트리를 초기화, 업데이트, 쿼리..
[백준 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개고 그 정수 쌍에 나타나는 필요한 좌표들만 확인하면 되는 문제다.  먼저 기준점 하나가 고정되면 철로의 길이를 이용해서 유효한 범위는 확정할 수 있으므로, 기준점을 정해 데이터셋을 정렬한 다음에 기준점이 변경될 때마다 그에 맞게 처리하면 되겠다고 생각할 수 있다. 나는 ..

티스토리툴바