그리디
-
백준 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..
-
백준 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 =..
-
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가지고 최대를 찾아..
-
BOJ1080 행렬Algorithm/BOJ 2020. 6. 11. 17:31
출처: www.acmicpc.net/problem/1080 분류: Greedy 접근방식 두 형렬에서 한 행렬을 한번에 3x3 만큼씩 뒤집는 연산을 통해 같은 행렬을 만들 수 있는 최소 연산횟수를 구하는 문제입니다. 처음엔 dfs로 무식하게 모든 경우를 다 해봤는데 이럴 경우 엄청난 연산 횟수로 역시 시간초과가 납니다. 그리디 문제인 만큼 그리디하게 풀면 생각보다 쉽게 해결할 수 있습니다. 0,0 부터 시작해서 n-3까지 가면서 해당 지점이 타겟 행렬과 다르다면 뒤집어줍니다. 0,0부터 시작하기 때문에 해당 점에서 뒤집지 않으면 결코 같은 행렬을 만들 수 없습니다. 같다면 그냥 통과하면 되는거고 다를 경우 연산 횟수를 카운트하면서 넘어가주면 됩니다. 이때 몇 가지 경우를 더 생각해줘야 하는데 같은 행렬을 ..