🧑💻/Algorithm
-
알고리즘) 백준 7562번 나이트의 이동 Swift🧑💻/Algorithm 2021. 5. 11. 19:07
www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 예제 입력 출력 3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1 5 28 0 문제 접근 예제를 살펴봅시다. 길이가 8이고 (0, 0)에서 (7, 0)으로 가는 방법은 이렇습니다. 하지만 다르게 가는 방법도 물론 존재합니다. (0, 0) -> (2, 1) -> (4, 2) -> (6, 1) -> (8, 2) -> (7, 0) 다시 문제로 돌아와서, 나이트가 이동할 수 있는 지점은 기준점으로부터 1..
-
알고리즘) 백준 13305번 주유소 Swift🧑💻/Algorithm 2021. 5. 10. 19:28
www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 예제 입력 출력 4 2 3 1 5 2 4 1 18 4 3 3 4 1 1 1 1 10 5 3 2 1 4 5 8 9 4 1 46 문제 접근 문제의 포인트는 가장 저렴한 주유소에서 충전하여 최대한 많은 거리를 가는 것입니다. 문제 속 예제를 로직화 해보았습니다. 0번째 : 최소 비용이 5원이므로 5원 * 2km 를 가야 합니다. 1번째 : 최소 비용이 5원에서 2원으로 변경됩니다. 2원 * 3km 를 ..
-
Swift 코딩테스트 - 탐욕(Greedy) 알고리즘🧑💻/Algorithm 2021. 2. 17. 15:58
Greedy Algorithm 최적 해에 가까운 값을 구할 때 사용합니다. 매 순간마다 최적의 방법을 선택하여 값을 구하지만 결과적으로 최적 해라는 보장은 없습니다. 다음 그림을 탐욕 알고리즘으로 풀면 다음과 같이 13 + 11 = 24라는 값이 도출됩니다. 하지만 실제로는 7 + 100 = 107이 나올 수 있는 최대 값입니다. 이렇게 탐욕 알고리즘은 최적 해라는 보장이 없습니다. 최적 해를 구하는 동적 계획법을 사용하면 되지만 속도가 월등히 빠르다는 장점이 있습니다. 대표적으로 최소 동전 개수로 돈을 거슬러 주는 예가 있습니다. 거스름돈 : 1200원 동전 종류 : 500원, 400원, 100원 탐욕 알고리즘에 의하면 500원 2개, 100원 2개로 총 4개가 나옵니다. 하지만 실제로 최적의 개수는 ..