알고리즘 문제 풀이/백준

[백준 11049] 행렬 곱셈 순서

DP를 활용하는 문제이다. DP 문제인건 보자 마자 알겠는데 어떻게 식을 세워야 할지 몰라서 찾아보다가 아래 유튜브 영상을 보고 이해를 했다. https://youtu.be/prx1psByp7U Bottom Up 방식으로 작은 부분먼저 계산해두고 최종 결과를 계산 해 나간다. 예를 들어 A,B,C 세개의 행렬의 곱셈 연산수를 구하기 위해서는 (AB)C, A(BC) 의 연산 결과를 비교해야 한다. 이 때 괄호 안의 값인 AB, BC를 먼저 계산해서 dp배열에 저장 해 두고 최종 결과를 계산할 때 해당 값을 사용한다. 위 영상의 예제는 행렬 네개를 사용하여 설명하므로 A,B,C,D 네개의 행렬을 곱하는 예시를 들어보면 다음과 같다. 가장 처음엔 인접한 두개의 행렬들의 곱셈 연산 횟수를 계산한다. 문제에서 주..

[백준 20040/] 사이클게임 java

문제 Union-find 를 활용하는 기본적인문제이다. 선택한 두 점의 번호를 한 집합으로 합쳐가는데, 이 때 두 번호가 모두 이미 선택된(집합에 이미 속한)번호들이라면 사이클이 생긴다. 사이클이 발생하면 이후의 입력값들은 더이상 볼 필요 없이 바로 종료하면 된다. Java 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N,M; static int[] parent; public static void main(String[] args) throws Exception { BufferedReader br = new Buf..

[백준 2467] 용액 java

문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 정수를 2개 선택하는데, 그 정수 2개의 절댓값이 0에 가장 가까운 수가 되도록 선택한다. 같은 절댓값을 만드는 숫자 쌍이 여러개일 경우 아무거나 출력. 입력 첫째 줄에 전체 용액의 수 N ( N은 2이상 10만 이하) 둘쨋줄에는 각 용액의 특성 값이 공백으로 분리되어 주어짐. (각 용액은 -1,0000,0000,000 이상 1,000,000,000 이하) 용액은 오름차순으로 정렬되어 ..

[SWEA 1949] 등산로 조정

문제 가장 높은 곳에서 시작해서 현재 위치 이하인 높이로만 길을 탐색 할 수 있을 때, 최대로 갈 수 있는 길의 길이를 찾는다. 단 1번 높이를 깎을 수 있다. 이 때 깎은 후의 높이가 1보다 작아도 상관 없다. 풀이 방법 가장 높은곳에서만 시작 할 수 있으므로 map의 가장 높은 곳들을 찾아서 dfs를 시작 한다. dfs로 상하좌우 탐색하면서 현재 위치 보다 낮은 곳으로 이동한다. 높이를 깎는 것은 1회만 가능 하기 때문에 ,이 경로로 도달하는 동안 길을 깎았는지를 체크할 boolean 변수 하나를 설정해 주었다. 높이는 최대 K까지 깎을 수 있으므로 0~K 만큼 깎아본 경우를 모두 따져본다. 코드 import java.io.BufferedReader; import java.io.IOException;..

[백준 14502] 연구소 java

https://www.acmicpc.net/problem/14502 문제 안전 영역이 최대가 되도록 벽 3개를 세웠을 때의 안전 영역 크기 구하기. 0: 빈칸 1: 벽 2: 바이러스 바이러스는 상하좌우 인접한 빈칸으로 퍼져 나갈 수 있으며 벽을 만나면 멈춘다. 문제 예제 2번의 경우 빨간색 위치에 벽을 세우고 나면 바이러스가 초록색 칸들로 퍼진다. 이후 남은 0의 개수는 9개가 된다. 풀이 방법 벽 3개를 세우는 모든 경우에서 안전 영역의 크기를 계산해서 최대 안전 영역의 크기를 계산한다. 벽 3개를 세운다. 바이러스가를 전파 시킨다. 빈칸(안전영역)의 크기를 센다. 코드 처음엔 안전 영역이 여러개 나오면 그 중 가장 큰 안전 영역의 값이 답인줄 알았는데 그런게 아니고 그냥 지도 전체에서 0의 개수만을 ..

[백준 17069] 파이프 옮기기2 java

문제 파이프를 연결해서 (N-1,N-1)칸 까지 갈 수 있는 경우의 수를 세는 문제. 파이프는 세로, 가로,대각선으로만 둘 수 있다. 세로 파이프는 세로, 대각선으로만 이을 수 있다. 가로 파이프는 가로, 대각선으로만 이을 수 있다. 대각선은 가로,세로,대각선 모두 가능하다. 풀이 방법 i,j 좌표로 올 수 있는 방법을 저장하는 3차원 dp배열을 만들어서 저장 한다. 파이프 모양에 따라서 방법의 수가 달라지기 때문에 3차원으로 만들어서 가로,세로,대각선일 경우를 각각 따져야 한다. (i,j)에 두는 파이프 모양에 따라 경우의 수를 구한다. 가로로 둘 경우 - 왼쪽 칸에 가로로 둔 경우, 대각선으로 둔 경우만 가능 : (i,j-1)의 가로 방법 수 + (i,j-1)의 대각선 방법의 수 세로로 둘 경우 - ..