목차 문제 https://www.acmicpc.net/problem/1932 풀이 일단 각 행에서 최대값을 선택해서 풀면 정답이 나오는지 확인해보자 7 -> 8 -> 1 -> 7 -> 5 = 28 정답인 30보다 작다. 이렇게 풀면 틀리게된다. DP문제는 점화식을 세워서 풀어야하는 경우가 많다. 또한 이렇게 모든 경우의 수를 파악해서 "최소값", "최대값"을 찾게되면 값을 누적하여 처리해야한다. 아래 사진처럼 일단 경우의 수를 파악하고, 점화식을 이끌어낸다. 주황색 부분은 2가지 값을 가질 수 있는데, 비교하여 최대값을 저장한다. 점화식 (x, y) A. [x][y] = [x-1][y-1] + [x][y] B. [x][y] = [x-1][y] + [x][y] 1. x-1 < 0 인 경우는 연산이 불가하다..

목차 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제풀이 시간제한이 1초이므로 일반적인 for문은 사용할 수 없다. DP로 풀어보겠다. 정수 n은 양수이며 11보다 작다. 1, 2, 3의 합으로 나타내야한다. [0]~[10]인 배열을 생성했다고하자. [0]은 사용하지 않는다. 잘 살펴보면 [2]는 [1]에 +1을 더한값과 자기자신인 2를 가지고 있고 [3]은 [2]에 +1을 더한값과 자기자신인 3을 가지고 있다. [4]는 [3]+1, [2]+2, [1]+3을 더한값을 가지고있지만 자기자신인 "4"는 표현할 수 없기 때문에 제외되었다. [..

목차 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제풀이 시간초과 보드를 반복적으로 4등분하여 Z 모양으로 읽어야한다. 분할정복을 생각해서 풀었지만.. 시간초과가 발생한다. 탐색 범위 좁히기 문제를 다시 살펴보자 61을 찾으려면 굳이 모든 부분을 탐색해야할까? 아니다. 4등분한 우측하단으로 범위를 좁히고 다시 우측하단으로 범위를 좁혀서 Z 탐색하면된다. 그럼 61(6, 7)이 우측하단에 위치하는 것을 어떻게 찾아내면될까? N이 8..

목차 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제풀이 분할정복은 재귀함수를 사용하여 문제를 해결할 수 있을 때까지 하위문제로 나누어 문제를 해결하고, 결과를 다시 전체에 합치는 방법이다. 1번째는 모든 좌표를 대상으로 2중 for문을 돌려 색을 판단한다. => 모두 같다면 색깔에 맞게 저장 => 하나라도 다른 색깔이 있다면 4분할 좌측상단 : x는 0~4까지, y는 0~4까지 탐색 좌측하단 : x는 0~4까지..

목차 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 인접한 좌표가 연결되어 있는지 체크하는 문제이다. 인접하다해서 bfs, dfs가 떠올랐고, 상하좌우로 이동할 수 있다해서 dx, dy에 대한 내용이 떠올랐다 일반적인 bfs, dfs는 아래 사진처럼 1번에서 시작하면 연결된 9번까지 도착할 수 있었다. 문제에 bfs, dfs를 그대로 적용하면 어떻게될까? (0,0)에서 시작한다 했을 때 (1,1)까지만 연결되어있기때문에 나머지는 탐색하지 못하고 ..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 1차원 BFS이다. 2차원 BFS의 check 변수를 node로 사용한다. 제출코드 package baekjoon; import java.io.IOException; import java.util.*; public class Main1697 { static int length = 100000; static int[] node = new int[length+1];..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제풀이 //중요도에 해당하는 문서를 지우기 전까지는 루프돌기 이부분을 처음엔 importmant++로 두었을 때 테스트케이스가 잘 동작되어서 제출했는데 런타임 에러 (ArrayIndexOutOfBounds) 가 발생했다 디버그해보니 9까지인 중요도가 10, 11 로 올라가고있었다 count++로 고치니 잘 돌아간다! package baekjoon; import java.io.BufferedReade..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { /* * (와 )개수가 같으면 : YES : stack..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제풀이 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.StringTokenizer; interface Stack{ void push(int n);..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 import java.util.*; import java.io.FileInputStream; class Solution { public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int widthMax = 1000; int heightMax = 255; int test_count = 10; for(int test_case = 1; test_case