Cherry & Cherish

문제 : 자연수 N에 몇 번의 연산을 통해 다른 자연수 M을 만들려고 한다. 사용할 수 있는 연산이 +1, -1, *2, -10 네 가지라고 할 때 최소 몇 번의 연산을 거쳐야 하는지 알아내는 프로그램을 만드시오. 단, 연산의 중간 결과도 항상 백만 이하의 자연수여야 한다. 예를 들어 N=2, M=7인 경우, (2+1) *2 +1 = 7이므로 최소 3번의 연산이 필요한다. 접근 : bfs를 활용해 방문 체크 후 연산을 진행한다. 풀이 : from collections import deque def bfs(N, M): queue = deque() queue.append((N, 0)) check = {} while queue: item, count = queue.popleft() if check.get(it..

DFS/BFS는 정말 코테의 단골 출제 문제이다. 그래프 탐색을 마스터 해보자! 1. 그래프 탐색 DFS/BFS로 문제를 풀기 위해서는, 그래프의 기본 구조를 알아야 한다. 그래프는 노드와 간선으로 구성되어 있다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데 코딩 테스트에서는 이 두방식 모두 필요하다. 바로, 인접행렬과 인접 리스트다. 💡 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 행렬은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같이 연결된 그래프를 인접 행렬로 표현할 때 파이썬에서는 2..

문제 : 24시간 운영되는 물류센터에는 화물을 싣고 내리는 도크가 설치되어 있다. 0시부터 다음날 0시 이전까지 A도크의 사용신청을 확인해 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면, 최대 몇 대의 화물차가 이용할 수 있는지 알아내 출력하는 프로그램을 만드시오. 신청서에는 작업 시작 시간과 완료 시간이 매시 정각을 기준으로 표시되어 있고, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다. 예를 들어 앞 작업의 종료 시간이 5시면 다음 작업의 시작 시간은 5시부터 가능하다. 접근 : 종료 시간을 기준으로 정렬해서 값을 갱신한다. 풀이 : T = int(input()) for tc in range(1, T+1): N = int(input()) arr = [list(map(int, input..

문제 : 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 접근 : 가능한 많은 5를 사용해야 하는 문제다. 3과 5가 배수 관계가 아니기 때문에, 주어진 설탕의 무게를 5의 배..

문제 : N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 접근 : 간단한 정렬 문제인데, 문제를 이해하는데 조금 시간이 걸렸다. ..

문제 : 민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오. 접근 : 최대한 문제 그대로 단순무식하게 풀이하려고 했다. while문 안에서 X가 나왔을 때는 연달아 나오는 X의 개수를 세서 그 개수가 4의 배수일 때는 'AAAA'를 누적하고, 2의 배수일 때는 4로 나눈 몫 만큼 'AAAA'를 곱해서 누적한뒤에 'BB'를 누적한다. 그리고 arr을 삭제해버린다. arr이 모두 없어지거나, 4의 배수도, 2의 배수도 아닐 때는 바로 -1를 입력해 whil..

문제 : 화물이 실려 있는 N개의 컨테이너를 M대의 트럭으로 A도시에서 B도시로 운반하려고 한다. 트럭당 한 개의 컨테이너를 운반 할 수 있고, 트럭의 적재용량을 초과하는 컨테이너는 운반할 수 없다. 컨테이너마다 실린 화물의 무게와 트럭마다의 적재용량이 주어지고, A도시에서 B도시로 최대 M대의 트럭이 편도로 한번 만 운행한다고 한다. 이때 이동한 화물의 총 중량이 최대가 되도록 컨테이너를 옮겼다면, 옮겨진 화물의 전체 무게가 얼마인지 출력하는 프로그램을 만드시오. 화물을 싣지 못한 트럭이 있을 수도 있고, 남는 화물이 있을 수도 있다. 컨테이너를 한 개도 옮길 수 없는 경우 0을 출력한다. 접근 : 그리디 문제이므로, 정렬을 활용해 문제를 풀 수 있다는 접근은 쉽다. 가장 적재용량이 높은 트럭이 가장 ..

문제 : 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 ..