목차 문제 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까지..

11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net + 이항계수? 경우의 수를 계산할 때 사용한다. 결론부터 말하면 아래와 같이 팩토리얼로 계산할 수 있다. 팩토리얼 재귀함수로 풀어보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ne..

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/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net DFS (Depth-First Search) DFS는 깊이 우선 탐색이다. 아래 그림처럼 한 곳만 깊게~ 계속 파다가 끝이 나오면, 다른 곳으로 가서 다시 깊게~ 계속 파는 것이다. - 단순 검색은 BFS보다 느리다 - 모든 곳을 방문할 때 자주 사용된다. - 재귀함수를 사용하여 다음 탐색 노드(현재 노드와 인접하고, 방문한 적이 없는 노드)로 이동한다. BFS (Breadth-First Search)..

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);..