greedy
-
백준 1202 보석 도둑Algorithm/BOJ 2021. 4. 7. 13:56
출처: www.acmicpc.net/problem/1202 분류: 우선순위 큐, 그리디 접근방식 진짜 어마무시하게 틀렸던 문제입니다... 보석과 가방을 모두 오름차순으로 정렬해두고 가방에 담을 수 있는 보석들을 우선순위 큐에 담아서 가장 비싼 보석을 넣어주면 되는 문제였습니다. 핵심이 되는 코드 부분만 보시면 이해하실 수 있을거에요 :) var jamIdx = 0 for back in backs { while jamIdx Bool) { // 최대 힙인지 최소 힙인지 기준을 잡는다. self.orderCriteria = sort } public init(array: [T], so..
-
백준 13904 과제Algorithm/BOJ 2021. 1. 27. 13:56
출처: https://www.acmicpc.net/problem/13904 분류: 그리디 접근방식 그리디하게 점수가 높은 과제부터 배정해주는 방식으로 해결했습니다. 점수가 높은 과제를 마감일에 처리해주되 해당 날이 이미 배정되어 있다면 비어 있는 날을 찾아 그 전날에 배정해주는 방식으로 해결했습니다. 만약 1 30 2 40 2 50 주어졌다면, 점수가 가장 높은 2 50을 먼저 배정해주고 그 다음 높은 2 40을 배정해주려 하는데, 2일차는 이미 차서 그 전날인 1일차에 배정해주는 방식입니다. 이미 점수가 높은 순서대로 배정시키기 때문에 다 차있어서 배정할 수 없다면 그게 최선일거라고 판단했습니다. 해결방법 protocol Readable { func readSingleValue() -> String f..
-
백준 1339 단어 수학Algorithm/BOJ 2021. 1. 22. 14:43
출처: https://www.acmicpc.net/problem/1339 분류: 그리디 접근방식 기본적으로 글자를 체크하고 수를 만드는 방식은 글자를 키로하고 글자의 자리 수 배열(해당 문제에서 최대 8자리)을 만들어서 이 글자가 해당 자리수에 몇 번이 사용되었는지 체크했습니다. 그리고 이걸 가지고 수를 만드는 방식으로 접근했습니다. 이제 문제는 어떤 글자에 어떤 숫자를 할당할지 결정해야 합니다. 아마도 가장 일반적인 생각이자 실수하기 딱 좋은 가정은 가장 큰 자리 수의 숫자가 많은 글자에 가장 큰 수를 매칭시키는 것으로 생각할 수 있습니다. 아래 예를 생각해볼까요? AA BC " 가장 큰 자리에 A 와 B가 1개씩 있어서 동률이고, 그 다음에 A가 한 번 더 있으니 A에 가장 큰 수인 9를 할당하면 되..
-
백준 8980 택배Algorithm/BOJ 2020. 7. 20. 16:10
출처: www.acmicpc.net/problem/8980 분류: 그리디 접근방식 출발 도시와 도착 도시, 용량이 적혀있는 택배 목록이 주어질 때 배달할 수 있는 최대 용량을 구하는 문제입니다. 단, 한번 지나온 마을은 다시 돌아갈 수 없습니다. 핵심 포인트는 다음 2가지 입니다. 문제의 핵심은 도착 도시를 기준으로 정렬 각 도시에서 적재 가능한 용량 체크 특히 도착 도시를 기준으로 정렬하는 것이 핵심인데요, 도착 도시를 기준으로 정렬했기 때문에 가장 먼저 내릴 수 있는 택배를 우선적으로 배달할 수 있습니다. 예를 들어, 3 60 3 1 3 50 1 2 30 2 3 60 이렇게 주어질 때 도착 기준으로 정렬합니다. 1 2 30 1 3 50 2 3 60 가장 먼저 도착하는 2번 마을에 배달해야 할 양 30..
-
백준 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 { // 비교대..
-
백준 1507 궁금한 민호Algorithm/BOJ 2020. 6. 18. 13:33
출처: www.acmicpc.net/problem/1507 분류: Greedy, Floyd Wharshall 접근방식 플로이드 와샬 알고리즘을 사용했습니다. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최소 비용을 구하는 알고리즘입니다. 이 문제는 그 결과가 주어진 경우라고 할 수 있는데요, 주어진 간선 중에서 가중치가 가장 작은 것부터 연결해가면서 플로이드 와샬로 다시 가중치 그래프를 완성시켜 나갑니다. 연결하려고 하는 간선의 가중치가 만들고 있는 가중치 그래프와 같다면 이미 다른 경로를 통해 연결이 되어 있으므로 연결하지 않습니다. 작은 경우에만 새로 연결합니다. 불가능한 경우에는 -1을 출력하라고 했으니, 복귀를 다 마친 다음에 원본과 다르다면 -1을 출력해줍니다. 해결방법 let n =..