greedy
-
백준 1543 문서 검색Algorithm/BOJ 2020. 6. 15. 13:31
출처: www.acmicpc.net/problem/1543 분류: 그리디 접근방식 문자열 매칭 문제 입니다. 겹치지 않게 문자열을 찾으면 됩니다. 문서 길이가 2500정도 밖에 안되서 단순 매칭으로도 해결할 수 있는 문제입니다. 문제는 탐색의 시작을 반드시 0번부터 할 필요는 없다는 것이죠. 첫번째부터 탐색한거보다 그 이후부터 탐색을 시작해서 더 경우가 많아지는 반례는 찾지 못했습니다... 앞에서 탐색한 것 때문에 뒤에 문자를 더 찾지 못해 한 개를 손해 보더라도 앞에서 탐색한거랑 쌤쌤으로 개수는 똑같을 것 같은데.... 한 개이상 손해볼 수가 있는지 반례를 잘 찾지 못하겠습니다 😭 실제로도 c++ 같은 다른 분들의 풀이를 보니 그냥 첫번째부터 탐색해서 통과하셨더라구요... 채점 방식이 예전과 달라진 것..
-
백준 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부터 시작하기 때문에 해당 점에서 뒤집지 않으면 결코 같은 행렬을 만들 수 없습니다. 같다면 그냥 통과하면 되는거고 다를 경우 연산 횟수를 카운트하면서 넘어가주면 됩니다. 이때 몇 가지 경우를 더 생각해줘야 하는데 같은 행렬을 ..
-
백준 1541 잃어버린 괄호Algorithm/BOJ 2020. 6. 7. 15:18
출처: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 분류: Greedy +와 -만으로 이루어진 연산이 들어올 때 괄호를 묶어서 최소인 수를 만드는 문제입니다. + 연산부터 해주고 - 연산을 해주면 최소의 값을 구할 수 있습니다. - 로 우선 다 잘라준 다음에 각각을 다 더해주고 마지막에 빼주는 방식으로 해결했습니다. import Foundation var str = readLine()! var plusOpers = str.components(sepa..
-
1029. Two City SchedulingAlgorithm/LeetCode 2020. 6. 4. 13:17
출처: leetcode.com/problems/two-city-scheduling/ 분류: Greedy, Easy 접근방식 각 cost에는 A와 B에 보낼 수 있는 비용이 들어있습니다. 2N개의 비용이 적힌 costs에서 각각 N개씩 공평하게 A와 B에 나눌 때 최소비용을 찾는 문제입니다. costs가 [[10,20],[30,200],[400,50],[30,20]] 이렇게 주어져 있다면, A에 2개 B에 2개를 [ 10, 30, 50, 20 ]로 뽑아줄 때 가장 최소비용이 됩니다. 하지만 무작정 둘 중 최소를 찾아서 분배한다고 해서 최소비용을 보장할 수가 없습니다. costs 중에서 어떤 cost를 우선적으로 분배해줘야 할까요? 바로 둘의 차이가 큰 cost를 먼저 분배해줘야 나중에 더 작은 비용을 분배..
-
1046. Last Stone WeightAlgorithm/LeetCode 2020. 5. 31. 11:15
출처: leetcode.com/problems/last-stone-weight/ 분류: Greedy, Easy 접근방식 무게가 가장 큰 돌과 그 다음으로 큰 돌을 부시면서 1개의 돌이 남을 때까지 반복하는 문제 입니다. 두 돌의 무게가 같다면 그대로 없어지고 한쪽이 더 크다면 그 나머지가 다시 남은 돌이 됩니다. 문제는 두 돌을 골라서 부실 때마다 돌의 우선순위가 바뀐다는 점입니다. 즉, 매 스탭마다 가장 큰 돌이 바뀔 수 있다는 점이죠. 이 점을 잘 체크하면 되는 문제입니다. 해결방법 단순하게 매 스탭마다 max를 2번 뽑아서 제거해주는 방법을 사용할 수도 있겠으나, swift 기준으로 max의 시간복잡도가 O(n) 이고 max의 인덱스를 찾는데 O(n), 이를 제거하는데 O(n) 의 시간이 소요됩니다..
-
1217. Play with ChipsAlgorithm/LeetCode 2020. 5. 28. 13:40
출처: leetcode.com/problems/play-with-chips/ 분류: Greedy, Easy 접근방식 문제 자체를 이해하기가 어려웠던 문제였습니다. 간단히 요약하면, chips 에는 chip이 있는 index 가 적혀있습니다. 즉, chips = [2,2,2,3,3] 이렇게 주어져 있다면, 아래와 같은 모습으로 생각할 수 있습니다. 칩이 있는 인덱스 1 2 3 칩의 개수 0 3 2 이 칩들은 좌우로 2칸을 움직일 때는 비용이 없고 1칸을 움직일 때는 1의 비용이 듭니다. 여기서 이 칩을 한 곳으로 모으는 방법은 2가지 방법이 있습니다. 2에 있는 칩3개를 3으로 옮기는 방법 --> 비용 2 3에 있는 칩 2개를 2로 옮기는 방법 --> 비용 3 당연히 3을 2로 옮기는게 좋겠죠?? 다음으로..
-
1221. Split a String in Balanced StringsAlgorithm/LeetCode 2020. 5. 23. 21:34
출처: https://leetcode.com/problems/split-a-string-in-balanced-strings/ Split a String in Balanced Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 분류: Greedy, Easy 접근방식 "L", "R"로 이루어진 문자열에서 짝이 맞는 문자열의 개수가 얼마나 되는지 찾는 문제입니다. 저는 처음에 L 과 R 의 개수를 저장하는 변수를 만들고 카운트 해주면서 둘이 같아지면 ba..