정렬 (25) 썸네일형 리스트형 [Python] 9024번 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 24/02/12 이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다. 문제 접근 방식: 특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다. 투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다. 나는 두 가지 경우로 분리해서.. [Python] 9007번 카누 선수 https://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net 23/12/27 중간에서 만나기(MITM) 연습 문제로 풀었던 문제이다. 문제 접근 방식: 전체적인 사고 방식은 이전에 풀었던 중간에서 만나기 기본 문제인 7453번 문제와 같다. 이 문제에 대한 해설은 아래와 같다. 2024.01.02 - [알고리즘/백준 문제 풀이] - [Python] 7453번 합이 0인 네 정수 [Python] 7453번 합이 0인 네 정수 https:.. [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.. [Python] 23843번 콘센트 https://www.acmicpc.net/problem/23843 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 23/09/09 그리디적으로 생각하면 쉽게 풀 수 있는 문제다. 문제 접근 방식: 먼저 첫 번째 예제부터 살펴보자. 첫번째 예제는 $N = 5, M = 2$로 주어져 있고, $1 \ 4 \ 4 \ 8 \ 1$로 각 기기 별 충전 시간이 주어져 있다. 최소 시간은 $9$이다. 가장 오래 걸리는 $8$시간 짜리 기기를 첫 번째 콘센트에 꽂아 놓은 상태에서 $4$시간 짜리 기기 2개를 두 번째 콘센트를 통해 충.. [Python] 23740번 버스 노선 개편하기 https://www.acmicpc.net/problem/23740 23740번: 버스 노선 개편하기 서강 나라에서는 일직선 도로를 따라 $N$개의 버스 노선을 운영 중이다. 필요할 때마다 노선을 새로 만든 탓에 겹치거나 중복되는 노선이 많다. 복잡한 버스 노선에 지친 시민들을 위해 버스 노 www.acmicpc.net 23/09/02 스위핑 기초를 다질 수 있는 문제로, 2170번 선 긋기 문제의 응용 버전 문제라고 생각할 수 있다. 문제 접근 방식: 문제 접근 방식은 다음과 같다. 1. $N$개의 입력 $S, E, C$를 $S$를 중심으로 내림차순 정렬한다. 2. 이후 리스트에서 마지막 원소(시작 지점이 가장 작은 버스)를 뽑아 새로 만드는 버스 노선의 시작 지점, 도착 지점, 비용($\textrm{.. [Python] 1092번 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 23/09/03 그리디적으로 접근하면 풀리는 문제로, 구현이 살짝 까다로웠다. 문제 접근 방식: 생각한 방법은 다음과 같았다. 1. 크레인과 박스가 있으면 두 리스트를 모두 내림차순 정렬한다. 2. 만약 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인의 무게제한을 비교했을 때, 가장 무거운 박스가 더 무겁다면 어떻게 하더라도 그 박스는 옮길 수 없으므로, $-1$을 출력.. [Python] 6068번 시간 관리하기 / 1263번 시간 관리 / 7983번 내일 할거야 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1 [Python] 24838번 배열 구간합 놀이 https://www.acmicpc.net/problem/24838 24838번: 배열 구간합 놀이 각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 www.acmicpc.net 23/08/04 내가 있는 스터디 그룹에서 이번 주 주간 문제로 다룬 문제 중 하나로, 구간 합을 적절히 이용한 재미있는 문제이다. 단점이라고 하면, 지문이 너무 길다는 것... 이 글에서는 지문을 전부 이해하고 있다는 가정 하에서 글을 쓸 것이다. 문제 접근 방식: 문제에서 주어진 예제를 잘 이해해 보자. 예제에서는 결론적으로, $1000$을 $2$번 더하고, .. 이전 1 2 3 4 다음