사풀이 (4) 썸네일형 리스트형 백준 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 기법인데, 이는 즉 문제를 절반으로 쪼개어.. 이전 1 다음
