Algorithm
[백준] 1114 통나무 자르기 - C++
[백준] 1114 통나무 자르기 - C++
2023.04.14시간 제한은 2초인데, 입력받는 L의 제한이 10억 까지이다. O(L) 시간복잡도로는 해결할 수 없다. 여기서 이분 탐색에 대한 단서를 얻고, 결정 문제로 바꿔서 풀이해야겠다는 전략을 세웠다. 구해야 하는 건 조건을 만족할 때의 가장 긴 조각의 길이와 처음 자르게 되는 위치이다. "가장 긴 조각의 길이" 를 검증 대상으로 설정하고 가장 긴 조각의 길이가 mid일 때 조건을 만족시킬 수 있나? 로 생각하자. 이분 탐색을 위해 입력받는 위치를 우선 정렬해 줘야 한다. (위치가 중복되서 나올 수 있어 중복을 제거하는 것도 괜찮을 것 같다) 현재 자를 수 있는 위치와 다음 자를 수 있는 위치의 차이를 통해 현재 위치와 다음 위치의 길이를 구할 수 있고, 배열에 값을 저장해 검증에서 사용하자. 처음 자르게 되는 ..
[백준] 9486 이름 남기기 - C++
[백준] 9486 이름 남기기 - C++
2023.01.03N이 적당히 작으니 비트필드를 사용할 수 있다. dp[status][cur] = 현재 입력을 완료한 상태는 status이고 지금은 cur번째 문자를 입력하고 있을 때의 최소 클릭 횟수 위와 같이 dp 배열을 정의하자. 재귀함수는 두 가지 케이스로 나뉜다. 1. 아무것도 입력하지 않은 경우 2. 뭔가 입력된 상태 아무것도 입력하지 않은 경우 문자는 A부터 시작하고, 어떤 문자부터 입력해야 최소 횟수를 반환하는지 알 수 없으니 모든 경우를 살펴봐야 한다. 뭔가 입력된 상태에서는 왼쪽 혹은 오른쪽으로 이동하는 경우도 추가로 생각해 줘야 하고, 이전에 입력한 문자부터 시작되는 부분을 고려해야 한다. 최소 횟수를 구하는 문제이니 INF를 적당히 설정해 주자. #include #include #include #in..
[백준] 23743 방탈출 - Java
[백준] 23743 방탈출 - Java
2022.11.02각각의 방이 노드, 워프가 간선을 의미함은 쉽게 이해할 수 있다. 문제는 비상 탈출구를 어떻게 처리하는가인데.. 두 가지 방법이 있다. 1. 브루트포스 방식으로 비상 탈출구를 설치할 수 있는 모든 경우의 수를 살펴본다. 즉, 방의 개수가 3이면 1 / 2 / 3 / 1 2 / 1 3 / 2 3 / 1 2 3 이렇게 뽑을 수 있는 모든 수를 뽑고, 뽑힌 수에 비상 탈출구를 설치한 후 최소 스패닝 트리를 돌린다. 크루스칼 알고리즘을 사용하는데, 만들어진 MST가 항상 모든 노드를 순회한다는 보장이 없다. 따라서 만들어진 MST에 대해 bfs를 수행해 모든 노드를 순회할 수 있는지 따로 확인하는 작업이 필요하다. 구현도 굉장히 힘든데.. 이렇게 풀면 시간 초과가 발생한다. 더보기 import java.io.*..
[백준] 14950 정복자 - Java
[백준] 14950 정복자 - Java
2022.11.01최소 스패닝 트리를 사용하는 문제임을 알아챘으면 풀이하기 쉬워진다. 어떤 순서로 정복하든, 비용의 증가는 막을 수 없기에 주어진 그래프에서 MST를 구해주고 증가하는 정도를 따로 계산해주면 된다. import java.io.*; import java.util.*; public class Main { static int INF = 987654321; static int N, M; static int K; static ArrayList list = new ArrayList(); static int[] parent; static int[] cost; static int min = INF; public static void main(String[] args) throws IOException{ BufferedR..
[백준] 1194 달이 차오른다, 가자 - Java
[백준] 1194 달이 차오른다, 가자 - Java
2022.10.27외판원 순회 문제를 푼 적이 있다면 쉽게 풀 수 있는 문제이다. 주의할 점은 다음과 같다. 1. 열쇠를 먹은 후에는 돌아올 수 있어야 한다. visit배열을 3차원으로 설정하자. 2. 열쇠는 비트마스킹으로 처리해준다. 3. 최단 거리를 구해야 하니 bfs를 사용해 순회하자. 비트마스킹과 visit배열을 3차원으로 설정하는 부분만 주의하면 다른 bfs 최단거리 문제와 같다. import java.io.*; import java.util.*; public class Main { static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; public static void main(String[] args) throws IOException { BufferedRe..
[백준] 1939 중량제한 - Java
[백준] 1939 중량제한 - Java
2022.10.26그래프 탐색 알고리즘과 이분 탐색 알고리즘을 함께 사용하는 문제이다. 공장을 두 개 입력받으니, 시작 공장과 도착 공장이 정해진다. 시작 공장에서 도착 공장까지 가려면 중간에 다리를 많이 건너야 한다. 다리가 버틸 수 있는 최대 무게가 이분 탐색에서의 Right 부분이 되고, Left부분은 0으로 설정된다. 이제 문제를 바꿔서 생각해보자. 시작 공장에서 중량이 x인 물품을 옮길 때 도착 공장까지 옮길 수 있는가? 옮길 수 있으면 답을 갱신하고, 옮길 수 없으면 Right 부분을 갱신한다. import java.io.*; import java.util.*; public class Main { static int INF = 987654321; static int N, M; static ArrayList[] ..
[백준] 3109 빵집 - Java
[백준] 3109 빵집 - Java
2022.10.25파이프를 가장 많이 연결하기 위해서는.. 1. 첫 번째 행 부터 탐색한다. 2. 다음 열을 탐색 할 때는 ↗ → ↘ 순서로 탐색해야 한다. (그리디) 3. 파이프를 겹쳐서 설치하면 안되니, 방문 처리를 확실하게 해 주자. 탐색 순서가 정해져 있기 때문에, 탐색 시 bfs를 사용하면 안 된다. import java.io.*; import java.util.*; public class Main { static int R, C; static char[][] map; static boolean[][] visit; static int[] dr = {-1,0,1}; static int[] dc = {1,1,1}; static int ans = 0; static boolean flag = false; public s..
[백준] 14590 KUBC League (Small) - C++
[백준] 14590 KUBC League (Small) - C++
2022.10.06외판원 순회에서 한 단계 더 발전된 문제이다. dfs를 돌면서 dp 배열을 채운 뒤, 값들을 역추적해서 방문한 순서도 구해줘야 한다. dp[curNode][curState] : 현재 curNode를 탐색하고 있고, curState를 방문한 상태일 때 최대 길이 풀이의 편의를 위해 zero base index로 접근하고, 구해야 하는 선수가 1번이라고 했으니 0번으로 설정하고 dfs를 돌리자. #include #include using namespace std; int N; int arr[22][22]; int dp[21][1
[백준] 13156 Selling CPUs - Java
[백준] 13156 Selling CPUs - Java
2022.09.14입력을 먼저 해석하자. 5 3 1 4 10 1 1 1 1 8 1 1 1 1 9 1 1 5개의 CPU를 받았고 3명의 상인이 있다. 1번 상인) CPU를 한 개 팔 때는 1원을 준다 / 두 개 팔 때는 4원을 준다 / 세 개 팔때는 10원을 준다 ... 2번 상인) CPU를 한 개 팔 때는 1원을 준다 / 두 개 팔 때는 1원을 준다 / 세 개 팔 때는 8원을 준다 .. 3번 상인도 위와 마찬가지이다. 상인은 1번부터 순서대로 만나야 하고, 거래도 한 번만 할 수 있다. dp[i][j] = i번 상인을 만나고 있고, j개의 CPU를 팔았을 때 얻는 이익의 최댓값 import java.io.*; import java.util.*; public class Main { public static void main..
[백준] 1823 수확 - Java
[백준] 1823 수확 - Java
2022.09.13https://www.acmicpc.net/problem/13002 13002번: Happy Cow 천나라에 살고있는 민호는 애지중지하는 소 한마리가 있다. 소의 행복은 곧 민호의 행복이기 때문에 가지고 있는 전재산을 털어 최고로 맛있는 여물 N개를 구매 했다. 민호는 여물을 관리하기 www.acmicpc.net 위의 문제와 동일한 문제이다. 항상 그렇듯 dp배열부터 정의해보자. dp[i][j] = i ~ j 구간에서 수확했을 때 얻을 수 있는 최대 이익 이제 재귀를 사용한 top-down으로 풀지, 반복문을 사용한 bottom-up 방식으로 풀지 생각해야 한다. 여기서 판단의 기준이 되는 건 dp배열의 형태인데.. 지금은 재귀를 사용하는 편이 더 쉬워 보인다. import java.io.*; impor..
[백준] 18427 함께 블록 쌓기 - Java
[백준] 18427 함께 블록 쌓기 - Java
2022.09.04다이나믹 프로그래밍 유형 문제는 dp 배열 디자인과 점화식 설정이 90%, 나머지 10%는 구현이다. 키보드를 치는 시간보다 종이에 배열 디자인, 점화식 구하는 시간이 훨씬 더 길다.. dp[i][j] : 1 ~ i 번 까지 학생이 높이가 j인 탑을 만드는 경우의 수 학생이 블럭을 사용하지 않는경우도 있으니 점화식은 이 부분을 고려해서 작성해야 한다. dp[i][j] = dp[i-1][j] (i 번째 학생이 블럭을 사용하지 않음) + dp[i][j - list[i].get(k)] (i번째 학생이 어떤 블럭을 사용함) import java.io.*; import java.util.*; public class Main { static int INF = 987654321; public static void m..
[백준] 2228 구간 나누기 - Java
[백준] 2228 구간 나누기 - Java
2022.09.03이런 문제를 처음 봤을 때 어떻게 접근해야 할까? 먼저 종이에 예제 입력을 그려보고 어떻게 풀 지 생각한다. 일단 다이나믹 프로그래밍을 사용해야 할 것 같으니, dp 배열을 어떻게 디자인 할 지 생각한다. ( ex. dp[i][j] = i번째 수 까지 사용하고, 구간 j개를 사용했을 때의 최대 구간합 / 초기값 설정 / 탑다운 or 바텀업 ) 문제 상황에 맞춰서 dp배열을 디자인한다. 1차원으로 부족할 것 같으면 차원을 하나 더 늘려서 생각해본다. 종이에 dp배열을 그려놓고 어떤 방식으로 채워갈지 고민한다. 이전에 푼 문제에서 얻은 아이디어를 적용할 수 있는지 고민하면서, 점화식을 어떻게 세울 지 생각한다. import java.io.*; import java.util.*; public class Mai..