Algorithm/BOJ
-
백준 1041 주사위Algorithm/BOJ 2020. 6. 30. 15:37
출처: www.acmicpc.net/problem/1041 분류: Greedy 접근방식 주사위를 쌓아서 정육면체를 만들 때 각 주사위에서 서로 마주보는 면이 동시에 보일 수는 없습니다. 따라서 마주보는 면이 안 나오게 잘 계산해서 최소값을 구해줘야 합니다. 주어진 도면에서 각 주사위의 마주보는 면은 (0, 5), (1, 4), (2, 3) 입니다. (주사위 1개인 경우 제외) 만들어진 정육면체에서 각 주사위는 3가지 케이스 밖에 생기지 않고 각 케이스의 개수는 아래와 같습니다. 세 면이 보이는 경우 4개 ( 각 모서리 위쪽 ) 두 면이 보이는 경우 4(N-1) + 4(N-2) (옆면 모서리 + 위쪽 모서리) 한 면이 보이는 경우 4N(N-2) + (N-2)(N-2) (테두리를 제외한 옆면 + 테두리를 제..
-
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 =..
-
백준 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 /..