두 포인터 (7) 썸네일형 리스트형 [Python] 8094번 Canoes https://www.acmicpc.net/problem/8094 24/11/29 간단한 정렬 + 두 포인터 + 그리디 문제다. 문제 접근 방식: 간단하게 문제를 요약하면 다음과 같다. 카누 한 대에는 최대 사람을 두 명 태울 수 있다. 문제에서 카누 한 대의 최대 중량 제한 $W$를 주고, $N$명의 사람들의 몸무게를 준다. 모든 사람을 카누에 태우려고 할 때, 필요한 카누의 최소 대수를 구하는 것이다. 가장 무거운 사람과 가장 가벼운 사람을 짝지어서 태우는 방법을 먼저 생각했다. 예를 들어 무게 제한이 $100$이라면, $90$과 $10$을 짝지어서 태울 수 있을 것이다. 만약 그게 불가능 하다면, $90$만 먼저 태우고, $10$은 그 다음으로 무거운 사람과 짝지어서 태우면 될 것이다. 그래서 .. [Python] 11728번 배열 합치기 https://www.acmicpc.net/problem/11728 24/11/25 단순히 배열 두 개를 합쳐서 정렬하는 문제다. 문제 접근 방식: 파이썬에서 그냥 나이브하게 합쳐서 정렬하면 된다. 근데, 그러면 너무 재미 없으니까, 두 포인터로 푸는 방법도 알아보자. 이미 정렬된 상태로 주므로, 배열 A와 배열 B를 가리키는 포인터 두 개($i$와 $j$)를 선언하고, $A[i] 시복도는 $\mathcal{O}(N+M)$이 된다. 반면, 두 리스트를 나이브하게 합치고 정렬하는 방법은 $\mathcal{O}(N+M \log(N+M))$의 시복도가 든다. 근데 실제로 실행해보면 두 리스트를 나이브하게 합치고 정렬하는 방법이 시간이 더 적게 소요가 되는데, 이는 정답 배열에 append를 하는 연산의 .. [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$는 두 지점의 위치를 나타낸다. 예제 입력을 통해 왜 투 포인터를 써야하는지에 대한 이야기를 해보자.예제 입력에 대한 그림을 그리면 다음과 같다.빨간 지점에서 시작하여 빨간 지점과 가장 멀리 떨어져 있는 곳을 반시계 방향 순으로 찾아보자.그림을 보면 확인할 수 있듯이, 빨간 지점과 가장 멀리 떨어진 지점을 찾을 때까.. [Python] 31235번 올라올라 https://www.acmicpc.net/problem/31235 31235번: 올라올라 길이가 $N$인 수열 $A$가 주어질 때, $N$ 이하의 양의 정수 $k$에 대하여 길이가 $N-k+1$인 수열 $B$를 다음과 같이 정의하자. $$B_{i}=\max_{i \le j \le i+k-1}A_j$$ 수열 $B$가 감소하지 않도록 하는 $k$의 최솟값 www.acmicpc.net 24/03/19 두 가지 방법으로 풀 수 있는 좋은 문제다. 그리디 + 스택으로도 풀 수 있고, 슬라이딩 윈도우+이분 탐색으로도 풀 수 있다. 개인적으로 전자가 더 쉽게 떠올릴 수 있다고 생각하지만 구현하는 데에 조금 실수가 생길 수 있고, 후자는 조금 더 어렵지만 구현하는 것이 그다지 어렵지 않아서, 어느 쪽으로 푸나 난이도.. [Python] 9024번 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 24/02/12 이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다. 문제 접근 방식: 특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다. 투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다. 나는 두 가지 경우로 분리해서.. [Python] 5526번 ダーツ (Darts) https://www.acmicpc.net/problem/5526 5526번: ダーツ (Darts) この例では，15 点の部分に 3 本，3 点の部分に 1 本の矢が刺さった場合にあなたの 得点は最大になり，その得点は 48 点である． www.acmicpc.net 23/12/29 중간에서 만나기(MITM) 연습 문제로 아주 적절한 문제이다. 첫번째 문제 접근 방식: 문제를 해석하자면 아래와 같다. 화살을 과녁을 향해 네 자루 던질 수 있다. 반드시 4개를 다 던질 필요는 없으며, 하나도 던지지 않아도 된다. 과녁은 $N$개의 부분으로 구분되어 있으며, 각 부분에는 점수 $P_1, P_2, \cdots , P_N$이 쓰여있다. 화살이 꽃힌 곳의 점수를 모두 합한 값 $S$가 기본 점수가 된다. 만약 $S$가 미리 정해.. [Python] 7453번 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 23/12/25 중간에서 만나기(Meet in the middle) 알고리즘 대표 문제이다. 그룹 연습문제를 풀기 위해서 기본 문제를 풀었다. 알고리즘 이름이 왜 중간에서 만나기인지 모르겠는데, 아직 문제를 덜 풀어서 그런가 그냥 분할 정복처럼 느껴진다. 문제 접근 방식: 1. 나이브한 접근 방식 나이브하게 저 조건을 만족하도록 $a, b, c, d$쌍을 찾기 위해선 $\math.. 이전 1 다음
