본문 바로가기

Algorithm221

[백준] 9252: LCS 2 - JAVA https://www.acmicpc.net/problem/9252 풀이LCS(최장 공통 부분 수열)문제. 두 수열이 주어졌을 때 공통된 부분 수열 중 가장 긴 것을 찾는다. 점화식은 다음과 같다. dp[i][0], dp[0][j]는 0으로 채워진 상태로 시작한다.if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1;} else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}수열A와 수열B를 한 글자씩 비교한다. 두 문자가 다르다면 dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 하고, 같다면 dp[i-1][j-1] + 1 으로 한다. 이렇게 하면 최장 공통 부분 수열의 길이를 구할 수 있다.. 2024. 5. 12.
[백준] 10942: 팰린드롬? - JAVA https://www.acmicpc.net/problem/10942 풀이수열이 주어지고 수열의 S번째 수부터 E번째 까지 팰린드롬을 이루는지 확인하는 문제. 수열의 1번부터 N번까지의 팰린드롬 여부를 담는 dp배열을 만든다. S, E를 입력받으면서 dp배열에 결과를 저장하면서 판별한다. 팰린드롬 판별은 재귀를 통해 구현했다. S와 E가 같으면 한 자리수이므로 true이고, 아닌 경우 다시 재귀를 통해 S+1과 E-1의 팰린드롬 여부를 판별하도록 했다.  메모리: 219448KB시간: 832ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[] arr; static boolean[][] dp; pub.. 2024. 5. 12.
[백준] 2251: 물통 - JAVA https://www.acmicpc.net/problem/2251 풀이물통 세 개의 부피가 정해져 있고 초기에는 C물통만 가득 차 있다. A물통이 비어있을 때마다 C물통의 양을 체크하여 저장하면 되는 문제이다. A, B, C물통의 양을 방문처리하기 위해 boolean[][][] 배열을 이용했고, C물통의 양을 오름차순으로 저장하기 위해 TreeSet을 이용했다. dfs탐색을 통해 진행하며 물통의 양을 체크했고, A물통에 물이 있다면 "A물통의 양 + B물통의양"과 "B물통의 용량"을 비교하여 A물통에서 B물통으로 옮기는 경우를 처리했다.  메모리: 23284KB시간: 140ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12.
[백준] 7682: 틱택토 - JAVA https://www.acmicpc.net/problem/7682 풀이구현 문제였다. 틱택토 게임의 게임판을 보고 이 상태로 종료될 수 있는지 보는 문제. 여러 경우를 처리해야 하는 문제였다. 1. 이차원 배열에 입력받으면서 X와 O의 개수를 세줬다. O가 X보다 많으면 invalid. 2. X의 개수 - O의 개수가 1이나 0이면 3칸을 잇는데 성공한 개수를 센다. 3. 판이 꽉 차있는 경우 O가 이긴다면 invalid. X가 마지막에 놓기 때문이다. 4. 꽉 차있지 않다면 3칸을 잇는데 성공한 개수가 1보다 많으면 invalid. 5. O가 마지막에 놨는데 O가 이기면, X가 마지막에 놨는데 X가 이기면 invalid. 6. 이외의 경우 valid.  메모리: 15048KB시간: 144ms언어: Ja.. 2024. 5. 12.
[백준] 17836: 공주님을 구해라! - JAVA https://www.acmicpc.net/problem/17836 풀이그래프 탐색 문제. (1, 1)에서 (N, M)까지 최단 시간으로 가야 한다. T라는 제한 시간이 있고, 벽은 지나갈 수 없으며, 무기를 찾으면 벽도 통과할 수 있다. 즉, 무기가 있고 없고 두 경우를 방문 처리를 따로 해야 하는 문제이다. class를 만들어 좌표와 시간, 무기가 있는지 정보를 담았다. bfs 탐색을 통해 (0, 0)부터 진행했다. 시간이 T 초 이상이면 진행을 멈췄고, 그전에 목적지에 도착했으면 출력 후 멈췄다. 사방 탐색 후 다음 칸으로 넘어갈 때 무기가 있는지 없는지에 따라 다르게 처리했다.  메모리: 16148KB시간: 176ms언어: Java 11import java.io.*;import java.util... 2024. 5. 12.
[백준] 2143: 두 배열의 합 - JAVA https://www.acmicpc.net/problem/2143 풀이배열 2개가 주어지고 배열들의 부 배열들을 합하여 T를 만들는 경우의 수를 찾는 문제이다. 두 가지 방법으로 풀 수 있는 문제였다. 첫 번째로 생각한 방법은 Map을 사용해 containsKey를 이용하는 방법이었다. 배열 A의 부 배열들의 합을 map에 저장해 놓는다. 배열 B의 부 배열의 합을 구하면서 T에서 뺀 값이 A의 map에 있다면 map의 value 만큼 카운트하여 더해준다. 이 방법으로 제출하고 다른 풀이들을 보니 이분 탐색으로 푸는 방법도 있었다. List에 부 배열들을 저장하고 이분 탐색을 위해 정렬한다. ListA에서 값을 꺼내면서 T - 꺼낸 값을 찾을 값으로 하여 ListB에서 이분탐색을 통해 찾는다. 개수가 여.. 2024. 5. 12.
[백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다.  메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12.
[백준] 23083: 꿀벌 승연이 - JAVA https://www.acmicpc.net/problem/23083 풀이경로의 개수를 세야 하는 DP문제. 벌집 구조이다. 아래쪽, 오른쪽 위, 오른쪽 아래 3가지 방향으로 이동할 수 있다. bottom-up으로 진행을 하면 오른쪽 위로 이동할 때 처리가 곤란할 것 같아서 top-down방식을 채택했다. dp배열의 초기값을 -1로 설정하고 -1이 아닌 경우에는 dp배열의 값이 설정되었다는 것이므로 dp배열의 값을 반환했다. 구멍뚫린 칸은 0으로, (1, 1)은 1로 설정했다. 현재 칸을 (r, c)라고 할때 c가 2의 배수인 경우와 아닌 경우 탐색 해야 하는 배열이 달랐다.if(c % 2 == 0) { return dp[r][c] = (doDp(r + 1, c - 1) + doDp(r, c - 1).. 2024. 5. 12.
[백준] 12850: 본대 산책2 - JAVA https://www.acmicpc.net/problem/12850 풀이결론부터 말하면 분할정복을 통해 행렬의 거듭제곱을 하는 문제였다. 각각의 포인트에서 연결된 길을 이차원배열에 저장했다. 초기 배열을 V1이라고 하면 V1[a][b]는 a에서 b로 1분만에 갈 수 있는 경로의 수를 의미한다. V1을 제곱한 것을 V2라고 하면 V2[a][b]는 a에서 b로 2분만에 갈 수 있는 경우의 수이다. 즉, Vx[a][b]는 a에서 b로 x분만에 갈 수 있는 경우의 수를 의미한다. 따라서 주어진 D만큼 V행렬을 제곱하여 V[0][0]을 구하면 D분만에 0에서 0으로 갈 수 있는 경우의 수이다. 분할정복은 doPow함수로 구현했고, 행렬의 곱셈은 multiply함수로 구현했다.  메모리: 14256KB시간: 124.. 2024. 5. 12.
[백준] 1717: 집합의 표현 - JAVA https://www.acmicpc.net/problem/1717 풀이자료구조, 서로소집합 문제. 집합들이 있고, 합집합연산과 서로 같은 집합인지 확인하는 연산이 있다. 배열을 집합의 개수만큼 만들고 자신의 번호로 초기화 한다. 자신의 그룹을 찾는 함수, 그룹을 합치는 함수, 같은 그룹인지 확인하는 함수 3가지를 구현해야 한다. 자신의 그룹을 찾는 findGroup 함수에서는 배열의 값을 findGroup의 결과값으로 갱신하면서 어떤 그룹에 속해있는지 찾는다. 그룹을 합치는 grouping 함수에서는 findGroup을 한 결과들을 이용해 두 집합을 하나의 그룹으로 묶어준다. 같은 그룹인지 확인하는 check 함수에서는 마찬가지로 findGroup을 한 결과가 서로 같은지 여부를 판단한다.  메모리: 5.. 2024. 5. 12.

티스토리툴바