본문 바로가기

Dev/BOJ

 (63)
[백준 1507] 궁금한 민호 그래프 이론 문제다. 처음 문제를 가볍게 읽었을 때는 최소 스패닝 트리 문제인 줄 알았다. 하지만 문제를 꼼꼼하게 읽다 보니 개성 있는 문제라고 느꼈는데, 각 노드에서 목적 노드 별 최단 거리가 주어지고 최소 간선으로 그 그래프를 만들었을 때 간선의 비용 총합을 추측하는 문제였다.  먼저 시도했던 방법은, 최소 스패닝 트리를 만들듯이 간선들을 우선순위 큐에 넣고 비용이 작은 간선을 우선해서 그래프를 만들어 나가는 방법이었다. 이 방법으로 구현하다가 결국에는 다른 노드를 경유해서 만들어질 수 있는 최단 거리 문제 때문에 중간에 지워버렸다. 매 간선을 추가하려고 할 때마다 DFS가 필요할 테니까.  그다음으로 이용한 방법은, 플로이드-워셜 알고리즘을 이용한 방법이었다. 문제에서 주어지는 입력값은 결국 어떤 ..
[백준 1365] 꼬인 전깃줄 LIS 문제다. 문제를 잘 해석해 보면, 꼬임이 발생하지 않는 경우는 왼쪽 전봇대와 연결된 오른쪽 전봇대의 번호가 계속해서 증가하는 형태로 나타날 때임을 알 수 있다. 따라서 LIS의 길이를 구하고, 전봇대의 개수에서 그만큼을 빼준다면 잘라내야 하는 전선의 수가 될 것이다. LIS 자체를 출력할 필요도 없기 때문에, 역추적을 위한 추가 처리 등이 전혀 필요하지 않다. 이런 간단한 형태의 LIS 문제에 대한 설명은 이전에 풀었던 아래 문제를 참조하면 좋을 것 같다. 거의 같은 유형.https://winterry.tistory.com/102 [백준 12015] 가장 긴 증가하는 부분 수열 2아마 알고리즘을 따로 공부했거나, 학부 과정에서 컴퓨터 알고리즘 과목을 수강했다면 익숙할 LIS 문제이다. 대표적인 D..
[백준 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]를 구한 것과 같다는 점에서 시작한다. 따라서 두 행렬의 곱을 구하는 함수를 만들..

티스토리툴바