문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가..
전체 글
문제 설명 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다. x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요. 제한사항 1 ≤ x ≤ y ≤ 1,000,000 1 ≤ n < y 입출력 예시 x y n result 10 40 50 2 10 40 30 1 2 5 4 -1 나의 풀이 from collections import deque def solution(x, y, n): # BFS를 통해 타겟 숫자 추적 q = deque() q.append(x) ch..
https://www.acmicpc.net/problem/16639 문제 접근 파일합치기 문제와 비슷한 방식으로 DP를 통해 해결하려고 시도했다. 내가 생각해내지 못했던 것은 연산자에 대한 인덱스 처리와 연산자에 따라 최솟값을 이용해서 최댓값을 만들 수 있는 경우가 있다는 것을 놓치고 있었고 검색을 통하여 힌트를 얻어 문제를 해결했다. 풀이 과정 문제를 푸는 핵심 개념은 Bottom-Up 방식으로 수식을 작은 범위부터 큰 범위로 확장해나가면서 계산하면 된다. 각 구간별 최댓값을 DP 배열에 저장하면서 구간을 확장하면 결국 DP[n][n]에 우리가 구하고자 하는 값이 저장될 것이다. 위의 그림을 코드로 표현하면 아래와 같을 것이다. n은 전체 수식에서 피연산자 갯수를 구한 것이고 (수식의 길이 + 1) /..
https://www.acmicpc.net/problem/17182 문제 접근 이 문제는 플로이드 워셜 + 순열로 해결해야 하는 문제이다. 출발하는 행성에서 모든 행성을 탐사하는데 걸리는 시간을 구해야 하므로, 최단경로를 구할 때 출발 행성에서 다른 행성까지의 최단경로를 구하는 다익스트라나 밸만포드보다는 모든 행성 간 최단경로를 구할 수 있는 플로이드 워셜 알고리즘을 이용해야 한다. 모든 행성 간 최단경로를 구했으면 방문하는 순서를 결정해야 한다. permutations 함수를 통해 출발 행성을 제외한 나머지 행성들의 순열을 구하고 거리의 합이 가장 작은 경우를 구해주면 된다. 풀이 과정 1. 플로이드 워셜을 통한 모든 정점 간 최단경로 계산 for k in range(N): for i in range(..
https://www.acmicpc.net/problem/2573 문제 접근 오랜만에 정답을 안보고 푼 문제이다. BFS를 이용한 구현문제였다. BFS를 통해 4방향에 인접한 빙산을 탐색하여 빙산의 그룹이 분리되었는지 확인하고 iceberg에 저장된 빙산들을 4방향에 인접한 물의 갯수만큼 빙산의 높이를 빼주면 된다. 풀이 과정 1. 빙산이 분리되었는지 확인 빙산의 위치에서 BFS를 통해 방문한 위치의 갯수와 미리 iceberg 배열에 저장해두었던 빙산의 위치의 갯수가 같으면 분리되지 않은 것이고 다르면 분리된 것이다. 하나의 빙산의 위치에서 BFS를 통해 탐색하면 모든 빙산을 방문할 것이기 때문에 위치의 갯수가 다르면 분리된 것으로 판단한다. def bfs(x, y): visited = [[False] ..
https://www.acmicpc.net/problem/11657 문제 접근 시작 노드에서 각 노드별로 최단경로를 구하는 문제이다. 최단경로를 구하는 알고리즘은 다익스트라와 벨만포드가 있다. 이 문제는 Edge의 음수 가중치가 존재하므로 다익스트라를 이용해서 최단경로를 구하면 제대로된 거리를 구할 수 없다. 따라서 음수 가중치가 있어도 최적해를 찾을 수 있는 벨만포드 알고리즘을 이용해서 문제를 해결해야 한다. 풀이 과정 벨만포드 알고리즘 순서 출발 노드 설정 dist 배열 초기화 모든 간선에 대해 각 간선을 거쳐 다른 노드로 가는 최단 거리 갱신 -> (정점의 갯수 - 1)번 수행 3번이 끝난 후에도 최단 거리가 갱신된다면 음수 사이클이 존재하는 것이다. 이 과정을 코드로 구현해보자. def bellm..
https://www.acmicpc.net/problem/1717 문제 접근 분리집합 문제이다. 분리집합문제는 Union-Find를 이용하여 해결할 수 있다. 이 문제는 문제 입력에 따라 Union연산을 하거나 같은 집합인지 확인하면 되는 문제였다. 주의할 점은 find 함수 작성할 때 최적화를 하지 않으면 시간 초과가 발생할 수 있다. 풀이 과정 1. 합집합 연산 def union(u, v): u = find(u) v = find(v) if u < v: parent[v] = u else: parent[u] = v 2. 최상위 부모 검색 최상위 부모를 검색할 때 루트가 제대로 저장되지 않은 경우는 검색하면서 다시 저장해주어야 시간 초과를 해결할 수 있다. 그냥 재귀를 호출하여 최상위 부모를 검색하면 시간..
https://www.acmicpc.net/problem/13913 문제 접근 BFS를 이용하여 목적지에 도달할 때까지 계속해서 탐색하는 방식으로 문제를 접근했다. 무조건 current - 1, current + 1, current * 2에 해당하는 좌표와 지금까지의 경로를 같이 큐에 삽입하도록 했는데 메모리 초과가 발생했다. 이미 방문한 위치를 또 방문할 뿐더러 중복되는 모든 경로까지 큐에 삽입하게 되기 때문이다. 따라서 dist배열을 통해 이미 방문한 위치를 체크하면서 해당 위치까지 도달하는데 걸리는 시간을 같이 저장했다. 또 경로를 트래킹하기 위해서 foot_print배열에 해당 위치에 이전 위치를 저장하도록 문제를 해결했다. 틀린 코드 ... def bfs(): q = deque() q.appen..
https://www.acmicpc.net/problem/11779 문제 접근 다익스트라를 이용한 최단경로를 찾는 문제이다. 풀이 과정 다익스트라 알고리즘을 통해 start와 end 사이의 최단경로를 구하도록 한다. 경로도 같이 저장해야 하므로 dist배열을 갱신할 때 부모 노드를 parent배열에 저장하도록 한다. 정답 코드 """ 백준 11779번 최소비용 구하기2 """ import sys import heapq def dijkstra(): dist[start] = 0 queue = [] heapq.heappush(queue, [dist[start], start]) while queue: cost, node = heapq.heappop(queue) if dist[node] < cost: contin..
https://www.acmicpc.net/problem/2252 문제 접근 위상 정렬(Topological Sorting)을 이용하는 문제이다. 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행할 때 사용할 수 있는 알고리즘이다. 위상 정렬에 대한 자세한 설명은 풀이 과정을 통해 다루도록 한다. 풀이 과정 1. 위상 정렬이란? -> 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 위상 정렬은 다음의 조건을 만족해야 적용될 수 있다. 그래프는 방향성을 가진 그래프여야 한다. 그래프에 Cycle이 없어야 한다. 위 두 조건을 한 문장으로 표현하면 위상 정렬은 DAG(Directed Acyclic Graph)인 경우에만 적용이 가능하다는 것이다. 2. ..