정렬 (25) 썸네일형 리스트형 [Python] 25635번 자유 이용권 https://www.acmicpc.net/problem/25635 25635번: 자유 이용권 자유 이용권은 놀이공원의 모든 놀이기구를 횟수의 제한 없이 마음껏 이용할 수 있는 이용권이다. 준원이는 ANA 놀이공원의 자유 이용권을 구매했고, 최대한 많이 놀이기구를 이용할 생각이다. www.acmicpc.net 22/11/18 전형적인 그리디 문제로, 그리디 문제 특성상 태그를 안 까면 접근할 때 방황할 수 있기 때문에, 이 문제를 어떻게 접근했는지 알아볼 필요가 있다. 문제 접근 방식: 연속해서 같은 놀이기구를 탈 수 없다는 조건을 보고, 서로 다른 놀이기구를 교대로 타면 많이 탈 수 있을 것이라고 처음에 막연하게 생각했다. 예제 입력 1을 보고, 제일 먼저 타야되는 놀이기구는 이용 횟수가 제일 많이 남.. [Python] 2036번 수열의 점수 / 1744번 수 묶기 https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 22/11/20 / 22/11/23 두 문제는 $N$의 크기만 다르고 솔루션이 완전히.. [Python] 17430번 가로등 https://www.acmicpc.net/problem/17430 17430번: 가로등 2차원 공간 위에 가로등이 N개 배치되어 있다. i번째 가로등의 위치는 (xi, yi)이고, 각 좌표는 정수이다. 서로 다른 가로등의 위치가 같은 경우는 없다. 두 가로등 i와 j(i < j)가 있을 때, (xi, yj)와 (xj www.acmicpc.net 22/11/22 예전에 해결하려다가 실패하여 오랫동안 북마크란에 있었던 문제로, 드디어 해결하였다. 개인적으로는 왜 기하학 문제인지 잘 모르겠고, 오히려 정렬 문제에 가까운 문제라고 생각한다. 문제 접근 방식: 문제 자체는 정말 간단하다. 2차원 공간 위에 가로등이 $N$개 배치되어 있다. $i$번째 가로등의 위치는 $(x_i, y_i)$이고, 각 좌표는 정수이.. [Python] 21344번 Hot Spring https://www.acmicpc.net/problem/21344 21344번: Hot Springs Output a rearrangement of the sequence satisfying the given requirement. If no solution exists, output "impossible". If there are multiple valid solutions, you may output any one of them. www.acmicpc.net 22/11/15 실랜디를 하다가 만난 문제로, 내가 전형적으로 약한 알고리즘이어서 문제를 접근하기가 조금 힘들었었다. 문제 접근 방식: 외국어 문제이기 때문에, 번역을 하자면 다음과 같다. 아이슬란드는 나라 전체의 열과 전력의 대부분을 공급해주.. [Python] 2212번 센서 / 13164번 행복 유치원 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 22/10/06 두 문제는 문제 설명과.. [Python] 1246번 온라인 판매 https://www.acmicpc.net/problem/1246 1246번: 온라인 판매 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다. www.acmicpc.net 22/09/10 연습에서 풀었던 문제로, 문제 읽는 게 조금 시간이 걸렸던 문제이다. 이런 문제가 실전에서 나온다면 당황했을 것이다... 문제 접근 방식: 경래가 수익을 최대로 올리고 싶다고 했고, 한 고객에게 1개만 달걀을 팔기로 했다. 각 고객들이 제시한 최대 지불 금액 P가 리스트로 주어지고, 이 금액을 넘지 않는 선에서 고객들은 금액을 낼 수 있다고 했다. 또한, 달걀은 최대 M명까지만 살.. [Python] 2381번 최대 거리 2381번: 최대 거리 (acmicpc.net) 2381번: 최대 거리 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다. www.acmicpc.net 22/09/03 그룹 연습에서 풀었던 문제이다. 이 문제는 애드혹 태그에 속하는데, 발상이 골드 3에 걸맞은 발상이라고 생각한다. 나 같은 경우 이 문제의 해답의 일부분을 어딘가에서 봤던 기억이 났기 때문에 풀 수 있었다. 문제 접근 방식: 이 문제의 시간제한은 1초이고, 파이썬 시간제한을 기준으로 하면 3초인데, 만약 그냥 두 점을 비교하는 방식으로 푼다면 입력의 크기가 50000*50000 = 25억이기 때문에 절대로 시간 내에 풀지 못한다. 따라서 시간 .. [Python] 1015번 수열 정렬 1015번: 수열 정렬 (acmicpc.net) 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 22/08/30 이 날은 피곤해서 한 문제밖에 못 풀었던 날이다. 그 문제는 1015번 수열 정렬. 이전에 한 번 잠깐 보고 무슨 말인지 몰라서 패스했던 문제였는데, 나중에 예제를 보니 무슨 말인지 알 것 같아서 바로 풀어보았다. 접근 방법: 주어진 원래 수열이 있다고 해보자. 이를 수열 1이라고 칭하자. 그리고 수열 1을 오름차순(비내림차순)으로 수열을 정렬했.. 이전 1 2 3 4 다음
