본문 바로가기

전체 글361

[PRGRMS]12946번: 하노이의 탑 문제: https://programmers.co.kr/learn/courses/30/lessons/12946 분할정복 문제입니다. N번째 원판을 1->3번으로 이동시키기 위해서는 아래와 같은 과정을 거칩니다. 1. 1~N-1번째까지의 원판을 1->2번으로 이동 2. N번째 원판을 1->3번으로 이동 3. 1~N-1번째까지의 원판을 2->3번으로 이동 그러면 다시 N-1번째 원판을 1->2번으로 이동시키기 위해서는 아래와 같은 과정을 거칩니다. 1. 1~N-2번째 원판을 1->3번으로 이동 2. N-1번재 원판을 1->2번으로 이동 3. 1~N-2번째 원판을 3->2번으로 이동 즉, 위 과정을 기저사례까지 반복하기 때문에 아래 두 가지 케이스를 나눠서 재귀로 풀면됩니다. 1. N번째에 할 일 2. 1~N-.. 2022. 3. 23.
[PRGRMS]43238번: 입국심사 문제: https://programmers.co.kr/learn/courses/30/lessons/43238 이분 탐색을 활용한 결정 문제입니다. 주어진 문제를 아래와 같이 바꿔봅니다. Q. 임의의 시간 X 분동안 심사관 전체는 몇 명을 입국심사 할 수 있는가? X = 28로 놓고 보면 times [7, 10] 이므로 28 / 7 = 4 28 / 10 = 2 28분동안 4 + 2 = 6명을 심사할 수 있습니다. X = 27은 27 / 7 = 3 27 / 10 = 2 27분동안 3 + 2 = 5명을 심사할 수 있습니다. 이렇게 X를 전체 범위에서 이분 탐색으로 탐색하면서 주어진 X분동안 N명이상을 심사할 수 있다면, 정답후보 X분을 더 줄여보면서 탐색을 하고 N명이상 심사할 수 없다면 X분을 늘려가면서 정.. 2022. 3. 23.
[BOJ]1719번: 택배 문제: https://www.acmicpc.net/problem/1719 다익스트라로 해결한 문제입니다. 임의의 A->B 두 순서쌍 경로 사이에 가장 먼저 방문하게 되는 노드를 구해야하는 문제입니다. 다익스트라를 사용하면 임의의 노드 A에 대해 나머지 노드에 대한 최단 경로 + 방문 정보를 저장할 수 있습니다. 그래서 N 개의 노드에 대해 N번 다익스트라를 돌린 후 1회 다익스트라 수행 때 마다 i번째 노드에서 나머지 노드를 방문할 때 최초로 방문해야 하는 노드 정보를 저장합니다. N번을 모두 돌리게 되면 2차원 배열 정답을 완성할 수 있습니다. N제한이 작으므로 log(V*Elog(V)로도 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/.. 2022. 3. 23.
[BOJ]2458번: 키 순서 문제: https://www.acmicpc.net/problem/2458 모든 학생들 간의 관계 (모든 노드간의 순서쌍)을 구하는 문제이므로 플로이드로 해결할 수 있는 문제입니다. N 제한이 작아 N^3을 돌려도 해결할 수 있다는 점을 단서로 삼을 수 있습니다. 학생들간의 키 관계를 담은 3차원 배열 int[][][] dist를 선언하였고 정보를 담아줍니다. dist[0][a][b] = 1이 의미하는 바는 a가 b보다 작은 경우입니다. dist[1][a][b] = 1이 의미하는 바는 a가 b보다 큰 경우입니다. 그래서 플로이드쌍을 전부 갱신해준 뒤 dist[0][][], dist[1][][]를 순회해서 비교 횟수가 N-1인 학생인 자신의 키 순서를 알 수 있습니다. 코드: https://github.co.. 2022. 3. 23.

티스토리툴바