Algorithm/Programmers93 [PRGRMS]72413번: 합승 택시 요금 문제: https://programmers.co.kr/learn/courses/30/lessons/72413 플로이드 문제입니다. 최저 택시 요금 후보로 갈 수 있는 경로는 크게 4가지입니다. 1. A를 경유해서 가는 경우: S => A => B 2. B를 경유해서 가는 경우: S => B => A 3. 각 각 택시를 타는 경우: S=> A + S => B 4. S와 A, B 사이에 임의의 경유지 i를 두는 경우(첫 번째 테스트 케이스): S => i + i => A + i => B 플로이드로 모든 경로쌍을 구한 뒤에 위 4가지 경우를 계산하여 최소값을 리턴하면 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%ED%95%A9%EC%8A%B.. 2022. 4. 12. [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. [PRGRMS]42839번: 소수 찾기 문제: https://programmers.co.kr/learn/courses/30/lessons/42839 완전 탐색문제입니다. 아래와 같은 순서로 해결하였습니다. 1. 에라토스테네스 체로 소수 미리 구해놓기 2. 2^N개만큼 만들 수 있는 숫자 전부 생성 3. 만든 숫자에 대해 순열 생성 4. 생성한 순열에 대해 소수 판별 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%86%8C%EC%88%98%20%EC%B0%BE%EA%B8%B0.java 2022. 3. 23. 이전 1 2 3 4 ··· 24 다음
