반응형 SMALL 문제풀이21 [백준] 11726번: 2xn 타일링 (Java/자바) 문제https://www.acmicpc.net/problem/11726 문제풀이전형적인 DP 문제이다. 이 문제는 처음에 봤을 때 완전 탐색으로 풀어야하나? 이렇게 고민되기도 하지만, 그렇게 된다면 구현 자체도 복잡할뿐만 아니라 2의 N승까지의 복잡도를 갖기 때문에 시간내에 풀 수 없게된다. 천천히 생각해보면 N = 1, N = 2, N = 3, ... 일때의 상황을 그려보고 점화식으로 풀이가 가능한 형식임을 눈치채야한다. 점화식은 dp[N] = dp[N-1] + dp [N-2] 이다.dp[1] = 1 // N == 1 일 때 가능한 조합은 1가지 뿐이다.dp[2] = 2 // N == 2 일 때 가능한 조합은 2가지 이다. (2x1 을 2개 쌓거나, 1x2를 2개 쌓거나)dp[3] = 3 // N ==.. 2024. 7. 28. ⭐ [백준] 11053번: 가장 긴 증가하는 부분 수열 (Java/자바) 문제https://www.acmicpc.net/problem/11053 문제풀이가장 베이직한 DP 문제라고 할 수 있다. 일반적으로 DP는 이전 값을 `기억` 하는데 초점을 맞추면 된다.memoization alogorithm 이라고 할 수 있는데 위 문제가 가장 기초가 되는 문제이다. 예제를 기준으로 설명하자면 아래와 같다. 1. N의 크기를 갖는 dp 배열을 생성한다.2. dp는 0~N 까지의 index의 수열들이 갖는 최대 부분 수열을 저장할 용도이다.3. dp는 초기에는 값을 업데이트 하지 않았기 때문에 자기 자신만을 수열로 갖는 상태이므로 1로 초기화 시켜준다.4. [ 10, 20, 10, 30, 20, 50 ] 수열의 0 index에서 부터 N번째 index까지 순차적으로 탐색한다.5. 탐.. 2024. 7. 24. [백준] 9663 N-Queen (Java/자바) 문제https://www.acmicpc.net/problem/9663 문제풀이처음에는 map을 2차원 배열로 잡고 무지성으로 Brute Force 방법으로 풀었으나 당연하게도 시간초가 났다.이 문제를 푸는 방법에 대해서는 다른 블로그를 참고하여 풀었는데 그 방법을 보아하니 아래와 같은 로직으로 풀게 되어있었다. (사전지식)Queen 은 상/하/좌/우/대각선으로 마음대로 움직일 수 있다. 따라서 Queen의 상, 하, 좌, 우 (= 다른 말로 Queen이 놓여진 행/열)의 index와 같은 Queen은 무조건 공격 받는다. 그렇기 때문에 map의 크기를 2차원 배열로 사용하지 않고 1차원 배열로 해놓고 map의 index를 열로, map 안의 원소의 값를 행으로 생각하고 문제를 푼다. 1. Queen을 .. 2024. 7. 23. [백준] 2580 스도쿠 (Java/자바) 문제https://www.acmicpc.net/problem/2580 문제풀이백트래킹 문제로 아래와 같은 흐름을 따른다. 1. 현재 위치에서 가능한 번호를 넣은 채 다음으로 넘어간다.2. 순서대로 map 전체를 탐방하며 가능한 번호로 계속 넘어간다.3. 만약, 중간에 가능한 번호가 없는 구역이 나타나면 이전으로 넘어가서 가능한 번호를 다시 탐색한다.4. 1~3번을 반복하며 map의 끝까지 갔을 경우 종료한다. 소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static int[][] map = new int[9][9]; .. 2024. 7. 23. [BOJ_3190_JAVA] 뱀 문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 'Dummy'라는 도스 게임이 있다. 이 게임에는 뱀이 나와서 기어 다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어 다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.. 2022. 2. 5. [BOJ_1717_JAVA] 집합의 표현 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 .. 2022. 1. 15. 이전 1 2 3 4 다음 반응형 SMALL
