공부공간

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 내가 진행하는 방향이 3가지라고 했을때(오른쪽, 오른쪽 아래, 아래) 이전위치에서 현재 위치로 오는 경우를따진다. 현재오른쪽 = 이전오른쪽 + 이전대각선 현재 대각선 = 이전오른쪽 + 이전대각선 +이전아래 현재 아래 = 이전 아래 + 이전 대각선 이므로 회전시에 MAP에 1이 아니라면 경우의 수를 더해준다. import java.io.BufferedReader; impor..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 현재의 값이 어떤 제곱수보다 커서 빼질 수 있다면, 그 제곱수의 값에 +1을 해주어 항상 최소를 만족한다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_17626 { public static void main(St..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 루트노드가 정해졌으므로 루트노드부터 재귀탐색을 하며 하위 노드의 개수를 저장한다. 리프 노드의 경우 1로 간주한다. 따라서, 자신과 연결된 노드들의 값 +1을 현재에 값에 저장시키며 재귀탐색을 진행한다. import java.io.BufferedReader; import java.io.InputStreamReader; import ja..

www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 수열에서 연속된 부분배열의 최댓값을 구하는 문제.. 양수면 계속더하면 최댓값이 되지만 중간에 음수가있는경우, 음수의 덧셈으로 0보다 크면 계속 더해준다. N^2 / NlogN의 풀이도 있지만, O(N)에 해결가능하다 package algorithm; import java.io.BufferedReader; import java.io.InputStreamRea..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으� www.acmicpc.net 3가지를 체크해주자. 1. 첫번째가는 길이여서 N,M까지 갈수있는 길인지? 2. 두번이상 째에 가는 길인데 N,M까지 갈수있는 경로인지 ( visit[0][y][x] 값이 양수) 3. 두번째 이상가는길인데 N,M까지 갈수 없어서 갈 필요가 없는 길인지? 3번째고려요소를 놓쳐 예전에 못풀었던 문제였다. 즉 첫번째 탐색했을때 N,M까지 못가면, 이후 탐색에서 그쪽길로 가면안된다는 체크를 해주어야한다. i..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net https://algorithmstudy-mju.tistory.com/161 BOJ - 9251 ) LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열을 구하기 위해 이전까지의 최장 공통 부분 수열을 구해 놓는다. 현재 문자가 격자상 문자와 같으면 대각선의 값 + 1을 현재 값으로, 다르다면 위 아래중 큰값으로 따라간다. import java.io.BufferedReader; import java.io.InputStreamReader; public class LCS { public..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 3X2 이차원배열과 (0번째는 최댓값계산 , 1번째는 최솟값 계산) 3X1 일차원 배열로 이전에서 올수있는 값중 최대 , 최소를 저장해놓고 다음 STEP을 진행한다. package 풀문제2; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 내려가기 { publi..