Swift
-
백준 1507 궁금한 민호Algorithm/BOJ 2020. 6. 18. 13:33
출처: www.acmicpc.net/problem/1507 분류: Greedy, Floyd Wharshall 접근방식 플로이드 와샬 알고리즘을 사용했습니다. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최소 비용을 구하는 알고리즘입니다. 이 문제는 그 결과가 주어진 경우라고 할 수 있는데요, 주어진 간선 중에서 가중치가 가장 작은 것부터 연결해가면서 플로이드 와샬로 다시 가중치 그래프를 완성시켜 나갑니다. 연결하려고 하는 간선의 가중치가 만들고 있는 가중치 그래프와 같다면 이미 다른 경로를 통해 연결이 되어 있으므로 연결하지 않습니다. 작은 경우에만 새로 연결합니다. 불가능한 경우에는 -1을 출력하라고 했으니, 복귀를 다 마친 다음에 원본과 다르다면 -1을 출력해줍니다. 해결방법 let n =..
-
Floyd Wharshall 플로이드 와샬Algorithm/Theory 2020. 6. 18. 13:24
목표 - 하나의 정점에서가 아닌 모든 정점에서 모든 정점으로 가는 최단 경로를 구하고 싶을 때 사용한다. - 거쳐가는 정점을 기준으로 알고리즘을 수행한다. - 삼중 for문을 사용해 구현하므로 O(n^3)의 시간 복잡도를 갖는다. 플로이드 와샬 알고리즘 ? 플로이드 와샬 알고리즘은 한 정점에서 시작해 모든 정점을 탐색하는 최단 방법을 다룬 다익스트라나 다른 그래프 탐색 알고리즘과 달리 모든 정점에서 모든 정점의 최단 경로를 구하고 싶을 때 사용합니다. 핵심 아이디어는 A -> B 노드로 갈 때, A -> B 로 바로 가는 경우 와 A -> K -> B 로 어떤 노드 k를 거쳐가는 방법 을 비교해서 최소값을 구하자는 것입니다. 구현은 가중치 테이블을 이용합니다. 아직 연결이 되지 않은 노드는 ∞으로 두고 ..
-
백준 1700 멀티탭 스케줄링Algorithm/BOJ 2020. 6. 17. 14:32
출처: www.acmicpc.net/problem/1700 분류: 그리디 접근방식 플러그의 개수와 사용해야 할 기기들의 순서가 주어질 때 플러그를 최소한으로 뽑을 수 있는 횟수를 찾는 문제입니다. 저는 처음에 단순히 앞으로 사용될 횟수가 가장 적은 플러그를 빼면 되지 않을까 생각했지만, 그렇게 하면 다음과 같은 경우에 최적의 경우가 되지 못합니다. 2 1 3 1 3 1 3 2222.... 이런 경우라면 2 1 3 중에서 사용 횟수는 1과 3이 가장 적지만 2는 나중에 나오기 때문에 당장 2를 뽑아서 사용해야 합니다. 뽑혀있는 플러그 중에서 가장 나중에 사용될 아이를 찾아야 합니다. 플러그를 뽑아야 할 상황이 오면 현재 꽂아야 할 기기 다음부터 확인해서 가장 나중에 사용될 플러그의 인덱스를 찾습니다. 가장..
-
백준 1065 한수Algorithm/BOJ 2020. 6. 15. 14:56
출처: www.acmicpc.net/problem/1065 분류: 완전 탐색 접근방식 주어진 N보다 작은 수 중에서 각 자리수가 등차수열을 이루는 수를 찾는 문제입니다. 등차 = 1의자리 수 - 10의자리수 와 같이 구할 수 있겠죠? 1의 자리 수 = n%10 10의 자리 수 = (n%100)/10 저는 이런 식으로 구했습니다. 해결방법 func isHansu(_ number: Int) -> Bool { if number 0 { if d != n - num%10{ return false } n = num%10 num /..
-
백준 1543 문서 검색Algorithm/BOJ 2020. 6. 15. 13:31
출처: www.acmicpc.net/problem/1543 분류: 그리디 접근방식 문자열 매칭 문제 입니다. 겹치지 않게 문자열을 찾으면 됩니다. 문서 길이가 2500정도 밖에 안되서 단순 매칭으로도 해결할 수 있는 문제입니다. 문제는 탐색의 시작을 반드시 0번부터 할 필요는 없다는 것이죠. 첫번째부터 탐색한거보다 그 이후부터 탐색을 시작해서 더 경우가 많아지는 반례는 찾지 못했습니다... 앞에서 탐색한 것 때문에 뒤에 문자를 더 찾지 못해 한 개를 손해 보더라도 앞에서 탐색한거랑 쌤쌤으로 개수는 똑같을 것 같은데.... 한 개이상 손해볼 수가 있는지 반례를 잘 찾지 못하겠습니다 😭 실제로도 c++ 같은 다른 분들의 풀이를 보니 그냥 첫번째부터 탐색해서 통과하셨더라구요... 채점 방식이 예전과 달라진 것..
-
BOJ 백준 1449 수리공 항승Algorithm/BOJ 2020. 6. 13. 12:00
출처: www.acmicpc.net/problem/1449 분류: 그리디 접근방식 테이프의 좌 우로 0.5를 남겨둬야 한다고 했으니 테이프 길이 - 1 만큼의 구멍은 한 번에 막을 수 있습니다. 구멍을 막을 때마다 테이프의 길이는 줄어들겠죠. 테이프의 길이보다 구멍까지의 간격이 더 크다면 테이프를 새로 끊어야 합니다. 현재 남은 테이프로 남은 구멍을 메꿀 수 있는지 확인하고 아니면 테이프를 새로 끊어줍니다. 다른 분의 접근법을 보고 알았는데요. 더 쉽게 생각하면 현재 구멍의 위치 + 테이프길이-1 만큼까지 커버가 가능하다는 말이 됩니다. 테이프를 새로 끊을 때 현위치 + 테이프길이-1 까지를 커버 가능한 범위라고 생각하면, 다음 위치가 커버 가능한 범위를 벗어나면 테이프를 새로 끊어주면 됩니다. 해결방법..
-
백준 2437 저울Algorithm/BOJ 2020. 6. 13. 01:53
출처: www.acmicpc.net/problem/2437 분류: 그리디 접근방식 쉬워보였으나, 실제로도 방법만 알면 쉬우나, 쉽지 않았던 문제입니다 😭 추들이 주어질 때 측정할 수 없는 최소값을 구하는 문제입니다. 어떤 경우가 되면 더 이상 무게를 구할 수 없다고 판단할 수 있을까요? 추를 오름차순으로 정렬했을 때, 처음 추의 무게가 2라면, 절대 1은 만들 수가 없습니다. 1, 2 다음에 900이 나온다면? 최대로 3까지 만들 수가 있습니다. 1, 2, 3 다음에 900이 나온다면? 최대로 6까지 만들 수가 있습니다. 그렇다면 이제 다시 생각해볼까요? 저희는 직관적으로 알고 있습니다. 1, 2, 3 다음에 900이 나오면, 이미 900은 너무 큰 숫자니 제치고 그 전의 1, 2, 3가지고 최대를 찾아..