algorithm
-
BOJ 1439 뒤집기Algorithm/BOJ 2020. 6. 22. 15:42
출처: www.acmicpc.net/problem/status/1439/74/1 분류: Greedy 접근방식 0이 연속되는 구간, 1이 연속되는 구간을 계산해서 더 작은 구간을 다 뒤집으면 되니까 더 적은 구간을 출력해주면 되는 문제입니다. 해결방법 let str = readLine()! var zeroSection = 0 var oneSection = 0 var current: Character? for char in str { guard let curr = current else { current = char continue } if char != curr { if char == "0" { zeroSection += 1 } else { oneSection += 1 } current = char } }..
-
백준 2812 크게 만들기Algorithm/BOJ 2020. 6. 22. 15:27
출처: www.acmicpc.net/problem/2812 분류: Greedy 접근방식 주어진 수에서 k개를 지워서 가장 큰 수를 만들어야 하는 문제입니다. 앞에서부터 스택에 담는데, 스택의 뒤에서부터 해당 수보다 작은 수는 다 지워내고 추가합니다. 저희는 k개를 지워야 하므로 지울 때마다 k의 개수를 줄여나갑니다. k가 0이 되었다면 더이상 지울만큼 지웠으므로 그냥 스택에 담아줍니다. 정리해보면 주어진 문자열에서 현재 확인할 숫자 n을 가지고 스택을 뒤에서부터 확인하면서 크거나 같을 때까지 반복합니다. // 현재 대상이 되는 수 n // stack의 뒤에서부터 확인하는 인덱스 i while i >= 0 { if n = 0 { if cuttedNumber[idx] >= originChar { // 비교대..
-
백준 3019 빵집Algorithm/BOJ 2020. 6. 18. 15:35
출처: www.acmicpc.net/problem/3109 분류: 그리디, DFS 접근방식 첫번째 열부터 차례대로 연결할 수 있는지 탐색하면 되는 문제입니다. 처음에 그냥 풀었다가 시간초과가 나고.. dfs를 사용해서 풀었는데, 주의할 건, 다음으로 연결할 수 있는 경우는 오른쪽, 오른쪽 위, 오른쪽 아래 3가지라서 다음 경우까지 모두 해봐야 하기 때문에 dfs에서 결과를 그냥 리턴하면 안되고 true일 경우에만 리턴해야 합니다. 해결방법 let n = readLine()!.split(separator: " ").map{Int($0)!} var map = [[Bool]]() for _ in 0.. Bool { return r >= 0 && c >= 0 && r < n[0] && c < n[1] } var..
-
백준 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 /..