본문 바로가기

전체 글

 (30)
백준 27092 - 생물 연구 문제를 요약하자면, 크기가 2 이상이면서 동일한 높이이며, 최소 공통 조상이 전부 동일한 정점의 집합의 개수를 세는 것이다. 정해를 읽어봤는데 생각과는 달라서 작성하게 되었다. 우선, 제곱 풀이를 생각해볼 수 있다. tree dp를 돌리면서, 어떤 서브트리의 루트를 최소 공통 조상으로 하는 집합의 개수를 세는 것이다. 만약 각 서브트리가 특정한 깊이를 가진 정점의 개수를 들고 있다면, 한 서브트리에서 문제의 답에 더해주어야 할 것은 각 높이에 대해, 각 서브트리가 가진 정점의 개수를 전부 곱한 값(그 높이의 정점이 존재하는 서브트리가 2개 이상인 경우에 한하여)을 전부 더해주면 된다는 사실을 직관적으로 알 수 있다. 다음과 같은 경우에, 1번 정점을 기준으로 카운팅해보자. 2번 정점을 루트로 하는 서브트..
백준 7936 - N의 존재 7936번: N의 존재 (acmicpc.net) 문제 자체가 워낙 간결해서 굳이 문제를 요약할 필요는 없을 것 같다. 우선, 정수론적인 사전지식이 몇가지 필요하다. 원시근과 이산로그에 대해 알고 있다면 해당 문제의 풀이를 이해하는데에 지장이 없을 것이다. 만약 p에 대한 원시근을 하나 찾는다면 문제가 해결되었다고도 할 수 있다. n을 p씩 올리는 행동을 n^m 항에는 어떤 영행도 미치지 않지만, n^n항에서는 지수가 정확히 1 늘어난 효과를 보여준다. 따라서 원시근을 일단 찾고 나면, n^n === a-n^m(mod p)인 문제를 해결하게 된다. 이때 n을 p씩 늘린다고 하였기 때문에, 그 원시근을 거듭해서 곱해주는 효과가 나타난다. 이 방법을 통해 특정한 값에 도달할 수 있는가는 이산로그 문제를 해결함..
백준 19702 - 친구 문제를 요약하자면, 자신의 양 옆에 친한 학생들만이 존재하도록 원탁에 학생들을 배치할 수 있는 방법을 출력하라는 것이다. 해당 사진에는 나와있지 않지만, 직접 링크를 타고 들어가보면 친한 학생들의 명수에 대한 조건이 주어진다. 19702번: 친구 (acmicpc.net) 19702번: 친구 선린인터넷고등학교에는 $N$명의 학생들이 있다. $N$명의 학생들 가운데 일부는 서로를 좋아한다. 신기한 사실이 있는데, 학생들 간에 일방적으로 좋아하는 경우는 없고, 반드시 서로 좋아하거나 www.acmicpc.net 이 문제는 조합론적으로 어떤 아이디어를 잘 적용해서 풀 수 있는 문제이지만, 본 글에서는 조금 다른 방법을 설명하고자 하는데, 바로 dlas를 사용하는 것이다. dlas같은 경우에는 이전의 squid ..
백준 1557 - 제곱 ㄴㄴ 문제를 요약하자면, k번째 무승수를 구하는 것이다. 원래는 포함 배제 원리를 통해 해결하는 풀이가 있는 것으로 알고 있지만, 본 글에서는 다른 방식으로 해결하는 방법을 서술할 것이다. 우선, 해당 문제를 알아야 한다. 특정 구간이 주어졌을 때 그 내부에 있는 무승수의 개수를 구하는 것이다. 이 문제의 제한은 1
백준 23575 - Squid Game 문제를 요약하자면, 세 개의 물통중 두 물통을 골라 양이 더 적은 물통의 양을 2배하고, 반대쪽 물통에서는 그만큼 물을 뺄 때 한 물통의 양을 0으로 만들어야 한다는 것이다. 원래대로라면 수학적으로 깔끔한 풀이가 있지만, 본 글에서는 다른 방법을 적용하였다. 본 글에서는 해당 문제를 dlas로 해결하였다. dlas는 특정한 상태를 정의하여 그 최적해를 구하는 기법으로, 본 글에서 자세히 소개하지는 않겠다. 우선, 아주 간단하게 랜덤으로 물의 양을 바꾸기만 해도 그 크기가 적당히 작아지는 것을 기대할 수 있다. 물론, 이 경우 수 분이 걸리기 때문에 실제 풀이로 적용 가능할지는 잘 모르겠다. 핵심은 이러한 랜덤을 dlas로 발전시키는 것이다. 해당 문제에 대한 상태를 시행을 적용하는 방법의 배열로 정의하자..
백준 7577-탐사 문제를 간단히 요약하자면, 특정 구간과 그 내부에 있는 표시의 개수가 여러개 주어졌을 때 이를 만족하는 해를 아무거나 출력하거나, 혹은 그러한 것이 존재하지 않는다고 출력하는 것이다. 해당 문제는 한국정보올림피아드 기출문제로, 일반적으로 그래프 이론의 알고리즘들을 사용하여 해결할 수 있는 것으로 알려져있다. 그러나, 해당 글에서는 정풀이와는 조금 다른 방법으로 문제를 해결하였다. 우선, n의 크기가 매우 작다는 것을 관찰하자. 만약 n이 20정도로 충분히 작았다면 브루트포스 알고리즘을 통해 해를 찾기만 하면 충분했을 것이다. n이 이보다 조금 더 클때, 즉 약 40정도일 때 브루트포스 알고리즘을 사용하기 위해 주로 사용하는 것은 meet in the middle 기법인데, 이는 즉 문제를 절반으로 쪼개어..

티스토리툴바