Algorithm/Baekjoon117 1082. 방 번호 (Python) 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 풀이 일단 가장 큰 숫자를 만들기 위해서는 최대한 숫자를 많이 사서 숫자의 길이를 가장 크게 해야한다. 이를 위해 가장 싼 가격을 가진 숫자를 찾아서 M원으로 총 몇 개의 숫자를 살 수 있는지를 체크한다. 이때, 숫자 0은 0 하나일 때를 제외하고 맨 앞에 오지 못하므로 1~N-1 까지의 숫자중 가장 싼 가격의 숫자를 하나 선택하여 제일 앞에 두고 다시 0~N-1 까지의 숫자 중 가장 싼 가격의 숫자를 찾아서 나머지 자리를 채운다. 이렇게 숫자를 만들고나면 M원에서 .. 2022. 6. 2. 11779. 최소비용 구하기 2 (Python) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 출발지가 주어졌고 비용에 음수가 없으므로 다익스트라를 이용하여 출발지에서 도착지까지의 최단 거리를 구할 수 있다. 다익스트라는 링크를 참고하자. 문제에서는 단순히 최단 거리뿐만 아니라 경로까지 요구하고 있다. 이를 위해 prev라는 리스트를 추가하였다. prev[x]는 출발지에서 x까지 최단 거리로 이동할 때 x 지점에 도착하기 이전에 방문했던 지점에 대한 정보를 담고 있다. 예를 들어 start -> a -> b -> x와 .. 2022. 5. 30. 14938. 서강그라운드 (Python) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 최단거리를 활용하는 문제인데 시작점이 주어지지 않는다. 그렇기 때문에 모든 지점에서 다른 지점까지의 최단 거리를 구하는 플로이드 워셜 알고리즘을 사용하자. 플로이드 워셜 알고리즘은 링크를 참고하자. 플로이드 워셜을 사용하여 모든 지점에서 다른 지점까지의 최단 거리를 구한 후 for문을 통해서 1번부터 N번까지를 시작지점으로하여 수색범위내에 도착 가능한 지점의 아이템 개수를 카운트한다. 이중 가장 큰 값을 찾으면 된다. 코드 import sys input = sys.. 2022. 5. 30. 12851. 숨바꼭질 2 (Python) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 bfs를 사용하여 답을 구할 수 있다. 현재 위치에서 +1, -1, *2를 해준 위치를 우선순위 큐에 넣고 시간이 빠른 것부터 큐에서 꺼내어 위의 과정을 반복한다. 방문 체크는 X위치에 도착한 시간을 사용한다. 만약 이전에 X 위치에 가장 빠른 시간 5초가 걸려 도착했는데 현재 다시 X에 도착한 시간이 6초라면 큐에 넣어주지 않는다. 하지만 4초에 도착했다면 가장 빠른 시간을 갱신하고 큐에 넣어 이동을 반복한다. 한 가지.. 2022. 5. 29. 2263. 트리의 순회 (Python) https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 입력으로 주어진 인오더와 포스트오더를 사용하여 재귀를 통해 프리오더를 구할 수 있다. 포스트오더는 리스트의 마지막에 있는 숫자가 현재 트리의 부모 노드에 해당한다. 이를 통해서 현재 트리의 부모 노드 숫자를 알 수 있다. 이제 이 숫자를 인오더 리스트의 어느 위치에 있는지를 찾는다. 인오더의 위치를 기준으로 왼쪽에 있는 숫자 리스트가 현재 트리의 왼쪽 서브 트리에 해당하고, 오른쪽에 있는 숫자 리스트가 현재 트리의 오.. 2022. 5. 27. 5639. 이진 검색 트리 (Python) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 트리 클래스를 사용하여 실제로 트리를 구성하여 출력하는 방법과 입력으로 주어진 전위 순회 결과에서 재귀를 사용하여 후위 순회 결과를 얻는 방법으로 문제를 해결할 수 있다. 전자는 Tree 클래스를 만들고 루트 노드의 값으로 트리 객체를 하나 생성한다. 그 후 Tree 클래스의 insert 메서드를 사용하여 트리에 값을 넣어준다. insert 메서드는 부모 노드의 값과 새로 삽입되는 값을 비교하여 작을 경우 왼쪽 트리에 값을 삽입하고 클 경우 오.. 2022. 5. 26. 이전 1 ··· 3 4 5 6 7 8 9 ··· 20 다음
