Algorithm
-
백준 13164번: 행복 유치원 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 17. 08:46
https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 접근 우선 근처에 있는 원생들의 키 차이를 알아야 한다. 그래야 어떻게 원생 그룹을 나눴을 때, 가장 많은 차이가 나는지 알 수 있기 때문이다. 바로 옆 원생들끼리의 차이를 구해 따로 리스트를 만든다. 이제 해당 리스트들을 오름차순으로 정렬한다. 이때 이 정렬을 기준으로 원생들의 키를 나눌 수 있다. 가장 차이가 많이 나는 원생들을 기준으로 나누는 건 피하고 나머지 원생들을 기준으로 더해준다..
-
백준 12904번: A와 B (Python/Java)Algorithm/Algorithm Problem 2022. 1. 16. 22:47
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 접근 문제 조건을 잘 살펴보면 어렵지 않게 그 힌트를 얻을 수 있다. 한번 연산이 수행될 때마다 글자 맨 뒤에 A가 되었건, B가 되었건 글자가 붙는다. 이 얘기는 한번 연산이 수행될 때마다 무조건 글자 수가 늘어난다는 것이다. 그리고 한번 연산을 할 때마다 뒤에 A 혹은 B가 붙기 때문에 바로 직전에 어떤 연산을 통해 해당 글자가 출력되었는지 확인할 수 있다..
-
백준 3055번: 탈출 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 15. 17:11
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 접근 문제 설정이나 출력 예시만 조금 다를 뿐, 백준 5427번 불(https://www.acmicpc.net/problem/5427)과 아예 똑같은 문제다. 백준 5427번 풀이를 작성한 적이 있으니(https://codestation.tistory.com/14) 참고하면 될 것이다. 풀이 Python from collections import deque upDown = [-1, 1, 0, 0] leftRi..
-
백준 16206번: 롤케이크 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 14. 23:23
https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 접근 최소 칼질 횟수로 길이가 10인 롤케이크를 최대한 많이 만들기 위해선 10으로 나누어 떨어지는 롤케이크를 잘라야 한다. 예를 들어 확인해보자. 길이가 30인 롤케이크와 35인 롤케이크가 있다고 하자. 길이가 30인 롤케이크는 10 / 10 / 10 두 번의 칼질을 통해 길이 10 롤케이크를 세 개 만들 수 있다. 반면 35인 롤케이크는 10 / 10 / 10 / 5 이렇게 세 번..
-
백준 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문이, ..