알고리즘 (60) 썸네일형 리스트형 백준(BOJ) 21608 : 상어 초등학교 https://www.acmicpc.net/problem/21608 문제 자체는 어렵지 않은데 까다로운 설정들이 들어가있어서 다시 해볼때도 주의하면서 해보는게 좋다. 🚀풀이 사방탐색, HashMap, 구현력 앉을 좌석을 찾는 방법을 구현할 때 NxN 배열을 순차 탐색하며 주어진 조건 3가지를 고려하여 자리를 선택하여 차례대로 학생들을 배치하였다. 3가지 조건을 고려하기 용이하도록 Seat 클래스를 만든 뒤, Comparable 인터 페이스를 상속하여 비교하였다. 비교하기 용이하기 위해 Seat클래스에는 x y 좌표, 주변 좋아하는 학생 수, 주변 빈칸 수를 필드로 가지도록 하였다. Seat 클래스안에 정보들을 한 번에 가지고 있지 않았더라면 중첩 if 문들로 비교를 해야 해서 가독성이 많이 떨어질 것이므.. 백준(BOJ) 15486 퇴사2 퇴사1 문제와의 차이점 동영상보고 기록해 놓기: https://www.acmicpc.net/problem/15486 어떻게 현실적으로 이 문제를 보고 어떻게 "이문제는 DP로 풀어야 한다"라고 떠올릴 수 있는 것인가? 우선은 해본다. 아래 그림과 같이 그려보는것이다. 1,2,3일째는 모두 그 이득이 0이다. 그런데 1일차에 있는 일을 하게 되면 그 이득으로 4일 차에 10을 얻게 된다. 마찬가지로 2일차의 일을 하게 되면 그 이득으로 7일차에 20의 이득을 얻게 된다. 이렇게 차근차근 표시해 나가는 것이다 우선은. 마찬가지로 3일차에 해당하는 일을 하게 되면 4일 차에 10의 이득을 얻게 된다. 그런데 이미 4일차에는 1일차에 해당하는 일을 했을때 얻을 수 있는 이득이 있다. 그러므로 1일차에 일을 하여.. 백준(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) 9655번 돌게임 https://www.acmicpc.net/problem/9655 DP쓸필요 없이 그냥 단순히 규칙만 찾으면 끝나는 문제다. " n = 1 : 돌이 1개가 있으면 상근이가 1개를 가져가면 끝나므로 상근이가 이긴다. n = 2 : 처음에 상근이가 1개를 가져가고 창영이가 남은 1개를 가져가면 되므로 창영이가 이긴다. n = 3 : 상근이가 처음에 돌 3개를 가져가면 끝나므로 상근이가 이긴다. n = 4 : 상근이가 돌 1개를 가져가든, 3개를 가져가든 돌이 1개나 3개가 남으므로 창영이가 이긴다. n = 5 : 상근이가 처음에 돌 1개를 가져갈 수 도 있고 3개를 가져갈 수도 있다. → 1개를 가져갔을 경우 : 4개가 남고 창영이가 1개를 가져가든 3개를 가져가든 1개나 3개가 남으므로 상근이가 이긴다. .. S-algo10 동적프로그래밍(1) cansum 보호되어 있는 글입니다. 백준(BOJ) 1010번 다리놓기 https://www.acmicpc.net/problem/1010 조합을 사용하여 정말 간단히 풀리는 문제다. 내가 조합을 공부할 때는 이보다 훨씬 복잡했다. 조합을 재귀트리로 구현할때 어떻게 구현하는지와 아래와 같이 dp를 써서 구현할 때 어떻게 저런 수식이 나오는지 그리고 시중의 다른 풀이법에 대하여 공부하자. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static int solution(int r, int n){ int[][]dp=new int[n+1][r+1]; for(.. 백준(BOJ) 27112 시간외 근무 멈춰!!! https://www.acmicpc.net/problem/27112 문제의 특성! -"주말에는 정규근무를 할수 없다." 이러한 조악한 조건들이 들어가면 문제가 지저분해 진다. 다만, 단순히 지저분해 진다고 해서 그 지저분한 것을 어떻게 구현하나로 방향을 잡지 말고 그 조악한 것을 문제에서 주워진 조건을 변형하고 어떻게 상쇄시켜버릴지, 없애버릴지 생각해 내는 것은 참 훌륭한 것같다. 실제 예를들면 아래와 같다. 해결코드를 보면 주워진 deadline을 새롭게 갱신해 준다(renewedDeadline). 이렇게 주워진 마감일을 앞당김으로써 주중에도 정규근무(regularWork)가 가능하게 해준것이다. 즉, 주말에는 regularWork가 불가능하다는 조악한 상황설정을 문제에서 주워진 값에 변형을 가해줌으로.. 백준(BOJ) 13164번 행복 유치원 문제를 읽고 "어떻게 이 문제를 탐욕적 알고리즘과 연관시켜 멋지게 해결할 수 있을까?"라고 생각했다. 도저히 염두가 나지 않아 바로 답을 보았다. 해결의 키는 주워진 수의 조로 분할 한다는 것이고 이는 각각의 원생들 사이 중에서 어느곳에다 분별의 막대기를 둘지 선택하는 문제임을 인지하는데 있다. 어디다 막대기를 두어야 하는가? 원생들은 서로 인접해야 한다고 했으므로(이게 정말 중요함) 원생들의 키차이가 가장 많은 곳에 막대기를 두어 다른조로 구분해 내면 된다. 그렇게 되면 그 큰 키차이가 없어진다. 즉, 원생들의 키의 차이를 모두 구한 자료구조 리스트를 구하고 그 리스트를 오름차순 정렬한다.그 후 height.length-(groups-1)를 구한후 그보다 1더 작은 위치까지 모두 더해 주면 된다(아래코.. 이전 1 2 3 4 5 6 7 8 다음