본문 바로가기

알고리즘/Greedy Algorithm

 (9)
백준(BOJ) 1912: 연속합 https://www.acmicpc.net/problem/1912 점화식등 다해놓고 안타깝게도 아래 max변수의 초기값을 생각없이 -1로 무턱대고 잡았다가 오답이 떳다. 초기화을 함부로 주지 말자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Testing3{ public static void solution(int n, int[]arr){ int[]dp=new int[n]; dp[0]=arr[0]; for(int i=1;i
(풀어야함), 기말 문제 중복 문자 제거하기 B. 중복 문자 제거하기 - 탐욕적 알고리즘으로 해결하는 문제 * 전수조사하기에는 경우의 수가 너무 많음 def solve(S, included, i, freq, done, ret): if i == len(S): ret.append(''.join(S[i] for i in range(len(S)) if included[i])) return included[i] = False if S[i] in done: solve(S, included, i+1, freq, done, ret) else: if freq[S[i]] > 1: freq[S[i]] -= 1 solve(S, included, i+1, freq, done, ret) freq[S[i]] += 1 included[i] = True done.add(S[i]..
백준(BOJ) 1092: 배 https://www.acmicpc.net/problem/1092 문제가 깔끔하지 않을수 있다. 여기서 깔끔하지 않다는 것은 어떠한 명확한 알고리즘을 묻는것도 아니고, 그 알고리즘을 감추어 놓은 것도 아니고, 알고리즘과 관련된 어떠한 참신한 생각을 떠올려야 풀리는 문제도 아닌 문제를 말한다. 하지만 이런 더러운 문제도 가치가 있다. 왜? 이러이러한 문제가 내가 알고있는 어떠한 해결법으로는 깔끔하게 풀리지 않는다는 것을 알려준다는 점에서 그러하다. 나는 이문제가 "최소 회의실 개수" 문제와 같이 우선순위 큐를 이용하여 풀릴줄 알았다. 그래서 그렇게 접근해 보았지만 예제 테스트를 모두 통과했지만 결국 오답이 나왔다. 코드는 상당히 지저분했다. 즉, 최소 회의실 문제는 PriorityQueue에 넣는 것도 회..
백준(BOJ) 2839번 설탕배달 https://www.acmicpc.net/problem/2839 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /* DP단원에 속해있지만 문제를 보고나서 가장 먼저 떠오른건 탐욕적 알고리즘이었다. 이후 DP로 풀려했지만 시중에도 그렇고 깔끔한 풀이가 존재하지 않았다... */ public class Main{ public static int solution(int n){ int a; if(n==0) return 0; if(n=5) { a = solution(n - 5); if(a>=0) return a+1; } if(n>=3){ a=solution(n-3); if(a>=0) retur..
백준(BOJ) 27112 시간외 근무 멈춰!!! https://www.acmicpc.net/problem/27112 문제의 특성! -"주말에는 정규근무를 할수 없다." 이러한 조악한 조건들이 들어가면 문제가 지저분해 진다. 다만, 단순히 지저분해 진다고 해서 그 지저분한 것을 어떻게 구현하나로 방향을 잡지 말고 그 조악한 것을 문제에서 주워진 조건을 변형하고 어떻게 상쇄시켜버릴지, 없애버릴지 생각해 내는 것은 참 훌륭한 것같다. 실제 예를들면 아래와 같다. 해결코드를 보면 주워진 deadline을 새롭게 갱신해 준다(renewedDeadline). 이렇게 주워진 마감일을 앞당김으로써 주중에도 정규근무(regularWork)가 가능하게 해준것이다. 즉, 주말에는 regularWork가 불가능하다는 조악한 상황설정을 문제에서 주워진 값에 변형을 가해줌으로..
백준(BOJ) 13164번 행복 유치원 문제를 읽고 "어떻게 이 문제를 탐욕적 알고리즘과 연관시켜 멋지게 해결할 수 있을까?"라고 생각했다. 도저히 염두가 나지 않아 바로 답을 보았다. 해결의 키는 주워진 수의 조로 분할 한다는 것이고 이는 각각의 원생들 사이 중에서 어느곳에다 분별의 막대기를 둘지 선택하는 문제임을 인지하는데 있다. 어디다 막대기를 두어야 하는가? 원생들은 서로 인접해야 한다고 했으므로(이게 정말 중요함) 원생들의 키차이가 가장 많은 곳에 막대기를 두어 다른조로 구분해 내면 된다. 그렇게 되면 그 큰 키차이가 없어진다. 즉, 원생들의 키의 차이를 모두 구한 자료구조 리스트를 구하고 그 리스트를 오름차순 정렬한다.그 후 height.length-(groups-1)를 구한후 그보다 1더 작은 위치까지 모두 더해 주면 된다(아래코..
백준(BOJ) 11000: 강의실 배정 문제를 다시 풀때마다 새로운 회의를 이미 강의실을 차지하고 있는 모든 회의들의 마감시간과 비교해야하는 것 아니냐는 게으른 사고에 빠지곤 한다!!! 아래는 이에 대한 답이다! 모든 것과 비교해야 하는 경우 이러한 번거로움을 없애줄 수 있는 것이 우선순위 큐이다. 왜 그런가? 사실은 모든 것과 비교할 필요가 없고 그 중 가장 크거나 혹은 가장 작은 것과의 비교만 이루어 지면 되기때문이다. 배열에 시작시간이 가장 이른 순서로 배열을 정렬하고 그 배열의 첫번째 인자의 마감시간을 우선순위 큐에 넣는다. 그리고 두번째인자부터 그 시작시간을 우선순위큐의 인자와 비교만 하면 되는 것이다. 만약 우선순위 큐의 값이 더 작다면 pop하고 2번째 회의의 마감시간을 큐에 넣으면 되고 만약 우선순위 큐의 값이 더 크다면 pop..
백준(BOJ) 14916: 거스름돈 https://www.acmicpc.net/problem/14916 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Testing2{ public static int solution(int value, int answer){ if(value

티스토리툴바