프로그래머스69 [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]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. [PRGRMS]92343번: 양과 늑대 문제: https://programmers.co.kr/learn/courses/30/lessons/92343 바킹독님 풀이를 참고하여 해결하였습니다. 풀이가 정말 자세히 나와있으니 참고하시면 좋을 것 같습니다. 비트마스킹 문제입니다. 가장 최초의 상태를 0000...000001 (0번째 노드만 방문)로 두고 현재 켜져있는 비트(사용하겠다는 의미)에서 이동가능한 다음 상태(자식 노드 존재)로 DFS를 탐색해서 2^17개의 상태를 전부 탐색해보는 방법으로 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%96%91%EA%B3%BC%20%EB%8A%91%EB%8C%80.java 2022. 3. 23. 이전 1 2 3 4 ··· 18 다음
