본문 바로가기

Problem Solving1220

[백준] 9251 LCS - Dynamic Programming / Java • 문제 링크 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net • 풀이 과정 LCS(최장 공통 부분 수열) 을 구할 두 문자열을 입력받고, 각각의 문자열의 길이 + 1 을 행과 열의 크기로 갖는 2차원 dp 배열을 생성한다. dp 배열을 모두 탐색하며 해당 좌표에 상응하는 두 문자가 같은 지 비교한다. 같다면 이전에 저장된 값(현재까지의 최장 공통 부분 수열 길이) 에 + 1 수행 후 저장하고,(dp[i - 1][j - 1] + 1) 다르다면 현재까지 저장된 최장 .. 2022. 11. 10.
[백준] 2565 전깃줄 - Dynamic Programming / Java • 문제 링크 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net • 풀이 과정 제거하여야 하는 전깃줄의 최소 개수가 아닌, 조건에 맞게 전깃줄을 최대로 설치할 수 있는 경우의 수를 구한 후 n 에서 빼는 방식으로 접근한다. A 전봇대 기준(Pair.src) 으로 정렬한다. 그런 다음 LIS (최장 증가 부분 수열) 을 구하여 정답을 출력한다. LIS 에 관한 문제는 아래에서 확인할 수 있다. [백준] 11053 가장 긴 증가하는 부분 수열 - Dynamic Programming / Java • 문제 링크 11053번:.. 2022. 11. 9.
[백준] 9461 파도반 수열 - Dynamic Programming / Java • 문제 링크 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net • 풀이 과정 문제에서 주어진 파도반 수열 p(1) ~ p(10) 의 변의 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다. 이때 n < 6 까지는 불규칙한 수열이므로 미리 값을 메모이제이션해주고, 그 이후부터는 점화식 dp[i] = dp[i -1] + dp[i - 5] 이 성립하는 규칙성을 지니고 있다. 따라서 n 의 범위가 1 2022. 11. 8.
[백준] 1904 01타일 - Dynamic Programming / Java • 문제 링크 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net • 풀이 과정 크기가 n 인 타일링의 가짓수를 구해보면, n = 1 (1) 1개 n = 2 (00), (11) 2개 n = 3 (001), (100), (111) 3개 n = 4 (0011), (1100), (1001), (0000), (1111) 5개 n = 5 (00001), (10000), (00100), (00111), (11100), (10011), (11001), (11111) 8개 위와 같이 가짓수의 증가폭이 1, 2, 3, 5, 8 로 피.. 2022. 11. 7.
[백준] 9184 신나는 함수 실행 - Dynamic Programming / Java • 문제 링크 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net • 풀이 과정 문제에 제시된 함수를 구현한 후, 메모이제이션을 할 3차원 dp 배열을 생성하며 크기는 함수의 조건상 21 로 지정한다. 미리 계산한 값을 dp 배열에 저장 및 반환하여 실행 시간을 단축시키며 각각의 테스트 케이스의 정답을 출력한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.In.. 2022. 11. 6.
[백준] 5430 AC - Data Structure / Java • 문제 링크 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net • 풀이 과정 입력받은 테스트 케이스 수 t 만큼 함수 p 와 배열의 크기 n 을 입력받고 해당 배열의 정수를 StringTokenizer 구분자를 "[]," 로 지정하여 입력받아 Deque 에 offer 한다. 함수 R 을 수행 할 시, boolean 변수 reverse 의 논리값을 변환하며, reverse = true 일 경우 덱에서 removeLast 를 통해 덱의 뒤에서부터 원소를 추출하며 그렇지 않을 경우 removeFirst 로 덱의 앞에서 부터 원소를 추출한다. 만약 추출 시 덱에 원소가 남.. 2022. 11. 5.

티스토리툴바