기록방

👉 문제링크🔸 문제 분석 🔸N개의 단어가 주어진다. 단어는 알파벳으로 구성되어 있는데, 각 알파벳은 0~9 숫자로 변환할 수 있다.알파벳은 최대 10종류가 주어지고, 알파벳의 숫자는 겹치지 않아야 한다.N개의 단어를 숫자로 변환했을 때 총합의 최대값을 출력한다.🔸 문제 풀이 🔸각 알파벳이 어떤 숫자와 매칭 되어야 최대값이 되는지 찾는 문제이다.Brute Force로 전부 넣어봐도 찾을 수 있지만, 좀더 효율적으로 찾고자 각 알파벳 별 가중치를 계산한다.가중치 순서대로 9부터 0까지 부여한 후 값을 계산해 출력한다.🔸 코드 🔸import java.io.*;import java.util.Arrays;public class Main { public static void main(String[..

👉 문제링크🔸 문제 분석 🔸전형적인 최장 증가 부분 수열 (LIS) 문제이다.LIS의 DP 풀이는 O(n^2) 이고, 이분탐색 풀이는 O(nlogn)이다.여기서는 n이 1000이므로, DP 풀이를 사용했다.🔸 문제 풀이 🔸DP 배열을 만들어 사용한다.DP 배열에는 현재 인덱스를 포함해서 만들어지는 가장 긴 증가하는 부분 수열의 길이를 저장한다.배열을 순회하며, 이전 인덱스들 중 DP 배열 값의 최대값 + 1을 저장한다.dp[i] = max(dp[i], dp[j] + 1)🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;..

👉 문제링크🔸 문제 분석 🔸N개의 컴퓨터 사이 M개의 네트워크가 있다.모든 컴퓨터를 연결할 수 있는 네트워크 최소 비용을 구한다.🔸 문제 풀이 🔸전형적인 MST 문제이다. 모든 노드를 한 번씩은 연결하며 최소 비용이 되도록 하기 때문이다.여기서는 크루스칼(Kruskal) 알고리즘을 사용했다.🔸 코드 🔸import java.io.*;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { private static int[] parent; public static void main(String[] args) throws IOException { // Input Buf..

👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 1년마다 상하좌우의 바닷물 수 만큼 줄어든다.빙하가 두 덩어리 이상으로 나뉘어지는 최소 시간을 출력한다.끝까지 두 덩어리가 되지 않으면 0을 출력한다.🔸 문제 풀이 🔸빙하가 녹는건 4방탐색을 하면 되고, 덩어리 확인은 그래프 탐색과 4방 탐색을 함꼐 하면 된다.여기서는 그래프 탐색 알고리즘으로 너비 우선 탐색 (BFS) 를 사용했다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;public class Main { private static int N, M; private static int..

👉 문제링크 14499번: 주사위 굴리기첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지www.acmicpc.net🔸 문제 분석 🔸N x M 지도에서 정육면체 주사위를 굴려가며, 주사위 윗면의 숫자를 출력한다.주사위가 이동했을 때 다음과 같은 숫자 변화가 있다.이동한 지도의 칸의 숫자가 0이면, 맞닿아 있는 주사위 아랫면의 숫자가 지도로 복사된다.이동한 지도의 칸의 숫자가 0이 아니면, 지도의 숫자가 주사위 아랫면으로 복사된다.🔸 문제 풀이 🔸주사위의 회전에 따른 숫자 이동을 구현한다.지도상의 ..