Python
-
백준 14499번: 주사위 굴리기 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 13. 22:21
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 접근 굳이 다른 알고리즘을 쓰지 않더라도 풀 수 있는 구현 문제로, 조건에 맞춰 코드만 잘 작성하면 된다. 나 같은 경우는 주사위를 굴리고 또 아래, 위를 찾는 것이 조금 귀찮고, 머릿속에서 바로 그려지지 않았다. 때문에 그냥 따로 코드를 짜서 움직이는 방향과 주사위 상태만 넣으면 굴러간 주사위를 만들어주게끔 만들었다. 덕분에 위는..
-
백준 5427번: 불 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 12. 23:47
https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 접근 너비 우선 탐색을 통해 빠른 경로를 탐색할 때는 보통 배열을 비롯한 각자만의 방식으로 자신이 갔던 경로를 체크하고 넘어가는 방식을 쓴다. 여기서 키포인트는 내가 한번 접근했던 경로, 즉 체크된 경로는 다시 접근하지 않는다는 점이다. 이미 접근했던 곳이라면 지금 방법보다 더 빠르게 접근할 수 있는 방법이 있다는 뜻이니 과감하게 넘어가도 된다. 이 문제의 키포인트는 총 두 가지로, 이 두 가지만 염두에 두면..
-
백준 18513번: 샘터 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 11. 22:03
https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 접근 이 문제에서 물어보는 것은 불행도의 합이 가장 적은 방법으로 집을 위치시키고, 불행도를 구하라는 것이다. 문제만 읽어봐도 알 수 있듯이 말만 불행도라고 했지, 결국 샘터와 가장 가까운 집들의 거리합을 구하는 문제다.(애초에 문제에서 집의 불행도는 샘터와의 거리로 정의된다고 적어놨다) 가장 가까운 거리의 합을 구하는 전형적인 너비우선탐색 문제라고 볼 수 있다. 그..
-
백준 1092번: 배 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 10. 23:47
https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 접근 굉장히 단순한 문제다. 어렵게 생각할 것 없이, 우선 입력받은 정보를 목록을 만들고 내림차순으로 정렬해준다. 그 뒤, 가장 무거운 무게를 들 수 있는 크레인과 가장 무거운 무게의 박스를 하나씩 확인해보며 걸리는 시간을 구하면 된다. 여기까지는 누구나 쉽게 생각할 수 있는 부분이다. 내가 생각하는 이 문제의 진짜 핵심은 구현 방식이라고 생각한다. while문 속에 for문이, ..
-
백준 1461번: 도서관 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 9. 21:46
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 접근 처음 풀려고 했던 방식은 가장 거리가 먼 구역을 한 번만 가도록, 즉 가장 마지막에 갈 곳만 생각했다. 그래서 그냥 간단하게 구역을 한 번에 옮길 수 있는 책의 개수로 묶고, 가장 먼 곳을 마지막에 가게끔 구현했다. 하지만 그렇게 풀면 절대 최소 거리가 나올 수 없다는 것은 금방 눈치챌 수 있었다. 예제 1번을 기준으로 생각해보자. 구역을 책의 개수 2개로 나눠보자. 물론 거리가 음수인 구역과 양..
-
백준 2212번: 센서 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 8. 16:07
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 접근 어느 한 곳에 집중국이 설치되면 그 주위에 있는 센서들의 자료를 모은다. 현재 설치해야 하는 집중국의 개수를 모두 활용해야 한다. 이 말은 즉, 집중국의 개수만큼 영역을 나누라는 뜻이다. 집중국 개수만큼 구역을 나누어주고, 구역마다 바로 옆 센서와의 거리를 구한 뒤, 해당 거리들의 합을 구하면 된다. 예제 1번의 경우를 살펴보자. 위치가 1, 6, 9, 3, 6, 7..
-
백준 12845번: 모두의 마블 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 7. 08:35
https://www.acmicpc.net/problem/12845 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 접근 현재 가장 많은 골드를 얻을 수 있는 선택이 최종적으로도 가장 많은 골드를 얻을 수 있는 방법이 된다는 점을 통해 그리디 알고리즘 문제라는 것을 파악할 수 있었다. 그렇다면 현재 선택에서 가장 많은 골드를 얻을 수 있는 방법이 뭘까? 복잡하게 생각할 것 없이 내가 지금 가지고 있는 카드의 구성을 떠나서 가장 높은 레벨의 카드에 그것보다 작은 레벨의 카드들을 덧붙여준다면 현재 받을 수 있는 골드..
-
백준 20413번: MVP 다이아몬드 (Easy) (Python/Java)Algorithm/Algorithm Problem 2022. 1. 6. 21:12
https://www.acmicpc.net/problem/20413 20413번: MVP 다이아몬드 (Easy) 입력된 MVP 등급을 달성하기 위한 최대 누적 과금액을 만원 단위로 출력한다. www.acmicpc.net 접근 누적 결제 금액이 최대가 되려면 너무 당연하게도 매번 결제할 때마다 결제할 수 있는 최대의 금액을 결제해야 한다. 첫 번째 달부터 현재 결제할 수 있는 금액이 얼마인지 확인하고 거기에 맞춰 최대 결제 금액을 맞춰주면 된다. 예제를 통해 설명해보겠다. 문제에 본격적으로 들어가기 앞서 주어진 조건들을 사용하기 쉽게 배열로 만들었다. 실버, 골드, 플레티넘, 다이아의 기준 금액은 30, 60, 90, 150이다. 이를 배열에 순서대로 넣어줬다. 상민이의 등급은 'BSG'이다. 이 또한 이..