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.. Algorithm/Programmers 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-.. Algorithm/Programmers 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분을 늘려가면서 정.. Algorithm/Programmers 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 Algorithm/Programmers 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 Algorithm/Programmers 2022. 3. 23.

• 

  [PRGRMS]92341번: 주차 요금 계산 문제: https://programmers.co.kr/learn/courses/30/lessons/92341 시뮬레이션 문제입니다. 주어진 정보를 입력받아 아래와 같이 처리를 하면 됩니다. 1. 시간을 분으로 환산하고 2. 해당 시간에 맞는 주차요금을 계산 저는 차량 번호가 작은 자동차부터 결과를 주기 위해 최종 연산결과는 treeMap에 담았습니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%A3%BC%EC%B0%A8%20%EC%9A%94%EA%B8%88%20%EA%B3%84%EC%82%B0.java Algorithm/Programmers 2022. 3. 17.