정렬 (25) 썸네일형 리스트형 [C++] 33118번 ICPC Provincial https://www.acmicpc.net/problem/33118 25/01/05 간단한 그리디 문제다. 이전에 해결했던 물정 수열과 비슷한 느낌을 받았다. 문제 접근 방식: 2025.01.04 - [알고리즘/백준 문제 풀이] - [C++] 26648번 물정수열 [C++] 26648번 물정수열https://www.acmicpc.net/problem/26648 25/01/04 그리디적으로 생각하면 해결할 수 있는 문제다. 그리디적으로 접근하기 위한 한 가지 핵심적인 관찰이 필요하다. 문제 접근 방식: 한 가지 핵심적인 관lighter.tistory.com이것도 중앙값에 대한 관찰을 해야하는 문제였다. 핵심 관찰은 중앙값을 조절해야 한다는 점이었다. 여기 문제는 길이 $3N$의 수열이 주어질 때 이.. [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] 28464번 Potato https://www.acmicpc.net/problem/28464 24/04/16 아주 간단한 그리디 문제다. 문제 접근 방식: 편의 상 박 모씨를 A, 성우를 B라고 부르겠다. 문제에서 요구하는 것은 A가 감자튀김을 최대한 많이, B가 감자튀김을 최대한 적게 가져가도록 하는 것이다. A가 먼저 감자튀김을 가져간다고 했다. 상식적으로 생각해보면, A가 감자튀김을 최대한 많이 가져가기 위해서는 감자튀김의 양이 가장 많은 접시부터 순서대로 가져가는 것이 이득일 것이다. 마찬가지로 B가 감자튀김을 최대한 적게 가져가도록 하기 위해서는 감자튀김의 양이 가장 적은 접시부터 순서대로 가져가는 것이 이득일 것이다. 따라서, 주어진 배열을 오름차순으로 정렬하여, 배열의 절반은 A가, 배열의 절반은 B가 가져가도록.. [Python] 31531번 공들의 리듬게임 https://www.acmicpc.net/problem/31531 24/03/10 풀이 아이디어가 제법 알려져 있는 문제로, 이전에 비슷한 문제를 해결했다면 쉽게 해결 할 수 있는 애드혹 문제다. 문제 접근 방식: 이 문제의 아이디어는 아래 문제에서 얻을 수 있다.https://www.acmicpc.net/problem/4307또는 아래 문제에서도 얻을 수 있다.2023.09.02 - [알고리즘/백준 문제 풀이] - [Python] 13249번 공의 충돌 [Python] 13249번 공의 충돌https://www.acmicpc.net/problem/13249 13249번: 공의 충돌 무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다. 오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공.. [Python] 30912번 위잉위잉 https://www.acmicpc.net/problem/30912 24/05/11 각도 정렬을 "잘" 구현해야 되는 문제이다. 문제 접근 방식: 처음으로 접근했던 방식은 파이썬 math모듈의 atan2함수를 이용한 정렬이다. 파이썬 공식 도큐먼트에 나와있는 atan2함수의 설명은 다음과 같다.math.atan2(y, x)Return atan(y / x), in radians. The result is between -pi and pi. The vector in the plane from the origin to point (x, y) makes this angle with the positive X axis. The point of atan2() is that the signs of both inp.. [Python] 30961번 최솟값, 최댓값 https://www.acmicpc.net/problem/30961 30961번: 최솟값, 최댓값 수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $N$인 수열 $A$가 주어질 때, 이 수열에서 길이가 $1$ 이상인 모든 부분수열 각각의 힘을 구하여 모두 XOR한 값을 구하여라. www.acmicpc.net 24/03/18 XOR의 성질을 이용한 간단한 수학 문제다. 문제 접근 방식: 문제의 요구 사항은 수열 $A$가 주어졌을 때, $A$의 부분 수열 $B$의 최댓값과 최솟값을 곱한 값을 $C$라고 하면, $A$의 모든 부분 수열에서 나오는 $C$의 값을 모두 XOR한 값을 구하는 것이다. 즉, 다음과 같은 수식으로 나타낼 수 있다. $$\bigoplus_{B \subset A} ( \max .. [Python] 26260번 이가 빠진 이진 트리 https://www.acmicpc.net/problem/26260 26260번: 이가 빠진 이진 트리 김소마는 최근에 포화 이진 트리에 대해 배웠다. 포화 이진 트리란, 이진 트리에서 리프 노드를 제외한 모든 노드가 두 자식 노드를 가지며, 모든 리프 노드가 채워진 것을 말한다. 아래의 그림 www.acmicpc.net 24/02/16 업다운 랜디를 하다가 만난 문제로, 처음 보고 뇌 정지가 와서 잘 해결하지 못했던 문제다. 이후 다시 풀게 되었고, 생각보다 간단한 해결 방법이 있어 글을 쓴다. 문제 접근 방식: 문제의 요구 조건은, 포화 이진 트리이면서 이진 검색 트리인 트리가 주어졌을 때, 특정 부분을 제거하고 다시 새롭게 썼을 때 바뀌는 트리의 후위 순회 결과를 출력하는 것이다. 처음에 보고 정석.. 이전 1 2 3 4 다음
