본문 바로가기

알고리즘

 (368)
[Python] 30959번 앙상블할래? https://www.acmicpc.net/problem/30959 24/05/14  간단한 브루트포스 문제다. 파이썬은 이러한 문제에 있어서 쉽게 구현을 할 수 있어서 좋은 것 같다. 문제 접근 방식:  $N$의 제한이 $16$까지이고, 항상 홀수 개의 모델만 선택한다고 했으므로 전수조사를 해도 충분히 시간안에 들어올 수 있음을 생각할 수 있다. 하나의 조합을 통해 앙상블을 구성하는 것은 조합의 크기와 예측 항목의 개수를 곱한 크기에 비례함을 확인할 수 있다. 그 수가 그렇게 많지 않으므로, 모든 조합을 확인해보면 된다. 파이썬의 itertools 모듈의 combinations함수를 사용하면 n개 중 r개를 선택하는 모든 조합의 경우들을 확인할 수 있으므로, 이를 사용하여 쉽게 구현할 수 있다. 인덱스..
[Python] 31462번 삼각 초콜릿 포장 (Sweet) https://www.acmicpc.net/problem/31462 24/05/14  업다운 랜디를 하다가 만난 문제로, 간단하게 그리디적 발상 + 살짝 귀찮은 구현을 요구하는 문제이다. 문제 접근 방식:  그림을 잘 관찰해보면, 빨간색 모양의 초콜릿은 뾰족한 부분이 위에 올라와있고, 파란색 모양의 초콜릿은 뾰족한 부분이 밑으로 내려와 있음을 확인할 수 있다. 따라서 위에서부터 아래로, 왼쪽에서부터 오른쪽으로 탐색을 진행할 때, 아직 발견하지 않은 빨간색 초콜릿을 발견한다면, 이는 빨간색 초콜릿의 뾰족한 부분이라고 결론 지을 수 있다. 마찬가지로, 똑같은 방법으로 탐색을 진행할 때 아직 발견하지 않은 파란색 초콜릿을 발견한다면, 이는 파란색 초콜릿의 평평한 부분이라고 결론 지을 수 있다. 따라서, 배열을..
[Python] 15681번 트리와 쿼리 https://www.acmicpc.net/problem/15681 24/03/29  트리 DP를 연습할 수 있는 아주 좋은 문제다. 이전에 해결했던 문제를 복습하는 겸, 글로 작성해본다.  문제 접근 방식:  나이브하게 각 쿼리마다 위의 값을 일일히 구해서 내보내려고 한다면, 최악의 경우 $\mathcal{O}(QN)$이 소요된다. 각 쿼리마다 DFS를 한 번 진행할 것이고, 트리에서의 DFS는 $\mathcal{O}(N)$의 시간 복잡도가 소요되기 때문이다. 따라서, 한 번의 DFS를 진행하여, 그 결과를 저장해야한다. 즉, DP를 진행하는데, DFS를 진행하며 DP를 진행하면 된다. 탑다운 DP의 구현 방식과 비슷한데, 트리 DP는 서브 트리 별로 문제를 분할하는 것이 핵심이다. DP 점화식을 다음..
[Python] 28422번 XOR 카드 게임 https://www.acmicpc.net/problem/28422 24/04/10  간단한 DP문제다. 이 문제를 통해 파이썬의 bit_count라는 좋은 내장함수를 알 수 있었다. 문제 접근 방식:  문제를 요약하면, 쌓인 카드 더미에서 카드를 2장 혹은 3장씩만 가져갈 수 있는데, 카드에 쓰인 모든 숫자를 XOR하고 그 값을 이진수로 변환했을 때 1의 개수만큼 내가 점수를 획득할 수 있다고 한다. 그때, 이 게임에서 얻을 수 있는 최고의 점수를 구하는 것이 문제이다. 카드는 2장 혹은 3장 단위로만 가져갈 수 있으므로 마지막에 카드가 1장이 남는 상황이라면 모든 점수가 0이 된다. 다음과 같이 DP식을 세우자.$$DP[i] = i\text{장을 가져갔을 때 얻을수 있는 최고 점수}$$ 이 식에 따르..
[Python] 28464번 Potato https://www.acmicpc.net/problem/28464 24/04/16  아주 간단한 그리디 문제다. 문제 접근 방식:  편의 상 박 모씨를 A, 성우를 B라고 부르겠다. 문제에서 요구하는 것은 A가 감자튀김을 최대한 많이, B가 감자튀김을 최대한 적게 가져가도록 하는 것이다. A가 먼저 감자튀김을 가져간다고 했다. 상식적으로 생각해보면, A가 감자튀김을 최대한 많이 가져가기 위해서는 감자튀김의 양이 가장 많은 접시부터 순서대로 가져가는 것이 이득일 것이다. 마찬가지로 B가 감자튀김을 최대한 적게 가져가도록 하기 위해서는 감자튀김의 양이 가장 적은 접시부터 순서대로 가져가는 것이 이득일 것이다. 따라서, 주어진 배열을 오름차순으로 정렬하여, 배열의 절반은 A가, 배열의 절반은 B가 가져가도록..
[Python] 12850번 본대 산책2 https://www.acmicpc.net/problem/12850 23/03/21  예전에 이 문제에 대한 풀이 글을 작성한 것 같았는데, 지금 검색해보니 작성하지 않아서 오랜만에 작성하려고 한다. 그래프를 인접 행렬로 나타낼 수 있는지에 대한 지식과, 그 행렬을 거듭제곱하면 경로의 개수가 나온다는 지식을 요구하는 문제다.  문제 접근 방식:  본대 산책1이 있고 본대 산책2가 있는데, 둘은 제한만 다른 문제다. 본대 산책2는 본대 산책1에 분할 정복을 이용한 거듭제곱 태그가 들어가서 난이도가 더 뛰어버렸다. (사실 그 정도로 어려운가 싶지만, 그렇다고 하자.) 문제에서 주어진 그래프를 인접 행렬의 형태로 바꿔보자.matrix = [[0, 1, 1, 0, 0, 0, 0, 0], [1, ..
[Python] 2600번 구슬게임 https://www.acmicpc.net/problem/2600 24/05/13  단순한 님 게임의 변형으로 해결할 수 있는 문제다. 스프라그-그런디 정리를 배우면서 님버에 대한 개념을 익혔다면 쉽게 해결할 수 있는 문제다. 그 외에도 이차원 DP로도 해결할 수 있다. 문제 접근 방식:  나는 이 문제를 스프라그-그런디 정리를 공부하며 얻은 지식인 님버를 활용하여 문제를 해결했다. 결국 이 문제는 님 게임의 변형이고, 처음 두 통에 들어 있는 구슬의 수가 최대 $500$개로 제한되어있기 때문에 충분히 빠른 시간 안에 님버를 구할 수 있다. 또한, 내 차례 때 할 수 있는 행동의 가지 수가 최대 $3$가지이기 때문에 각 숫자 별로 구하는 님버가 최대 $3$까지임을 확인할 수 있다. 현재 게임 판의 님버를..
[Python] 2118번 두 개의 탑 https://www.acmicpc.net/problem/2118 24/05/14  간단한 누적 합 + 두 포인터 연습문제이다. 문제 접근 방식:  두 지점을 $i$와 $j$라고 하고, 편의 상 $i \leq j$라고 가정하자. 원의 둘레를 $T$라고 한다면, 두 지점 사이의 거리는 다음과 같이 정의된다. $$\text{min}(D[j]-D[i] , T-D[j] + D[i])$$ 여기서 $D$는 두 지점의 위치를 나타낸다. 예제 입력을 통해 왜 투 포인터를 써야하는지에 대한 이야기를 해보자.예제 입력에 대한 그림을 그리면 다음과 같다.빨간 지점에서 시작하여 빨간 지점과 가장 멀리 떨어져 있는 곳을 반시계 방향 순으로 찾아보자.그림을 보면 확인할 수 있듯이, 빨간 지점과 가장 멀리 떨어진 지점을 찾을 때까..

티스토리툴바