DP

    [java] 백준 9251 (LCS) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9251 (LCS) Gold 5

    Problem : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Approach LCS(Longest Common Subsequence) 문제로 DP로 풀이가 가능한 문제이다. 배열은 DP[s1.length + 1][s2.length + 1] 으로 선언하여 두 문자열을 각각 한 문자씩 비교해 나간다. DP[i][j] 는 s1.charAt(i)와 s2.charAt(j)를 비교한 후, 그 때까지의 LC..

    [java] 백준 2156 (포도주 시식) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2156 (포도주 시식) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net Approach DP로 풀 수 있는 문제이다. ​ 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. ​ 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. ​ 3. 최대로 많이 마시게끔 포도주를 마셔야 한다. 놓여있는 마지막 잔을 마실 경우, ​ 1. ~ X O O 로 마시는 경우가 있다...

    [java] 백준 10844 (쉬운 계단 수) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 10844 (쉬운 계단 수) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach DP로 풀 수 있는 문제이다. 문제 풀이에 앞서, 밑의 조건을 알고 가면 편하다. ​ 1. 0으로 시작하는 N자리 수는 없다. ​ 2. 1자리 수는 모두 계단수이다. ​ 3. DP에 저장할 때에 1,000,000,000으로 나눈 나머지를 저장해야 한다. N자리 수를 봤을 때, 10의 자리 수가 0이면 1의 자리 수가 1이어야 한다. 10의 자리 수가 1~8이면 1의 자리 수는 10의 자리 수의 +1한 수 이거나 -1한 수 여야만 한다. 10의 자리수가 9이면 1의 자리 수는 ..

    [java] 백준 1932 (정수 삼각형) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1932 (정수 삼각형) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net Approach DP 문제이다. 문제에서는 이등변 삼각형처럼 보이지만, 실제로는 정사각형 배열의 반만 쓰면 된다. 크기가 N인 정수 삼각형이고, i는 위에서부터 층의 높이, j는 삼각형의 열일 때, ​ DP[i][j] = DP[i - 1][0] (j == 0) ​ DP[i][j] = DP[i - 1][j - 1] (j == N) ​ DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] (j == 1...N-1) 위의 식을 도출..

    [java] 백준 2580 (스도쿠) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 2580 (스도쿠) Gold 4

    문제 원문 링크 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Approach 이 문제 또한 대표적인 BruteForce, Backtracking 문제이다. N-Queens 문제와 접근법은 동일하다. 놓을 수 있는지 없는지 검사 후, 다음 단계로 넘어가며, 놓을 수 없다면 다시 뒤로 돌아가 똑같이 다음 수를 검사하는 것이다. 나는 1차원 배열을 사용하였으며, 배열에서 i번째 요소는 N x N 행렬에서 (i / N)행 (i % N)열이다. ..

    [java] 백준 9663 (N-Queen) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9663 (N-Queen) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/9663 Approach 대표적인 BruteForce, Backtracking 알고리즘 문제이다. 첫번째 열부터 숫자를 하나씩 놓으면서 그 다음 열에 놓을 수 없는지를 검사하여 놓을 수 있는 총 개수를 구하는 문제다. 퀸을 놓으려면 가로, 세로, 대각선에 퀸을 놓아서는 안된다. arr[] 배열은 몇 번째 열, 몇번째 행에 퀸을 놓은지를 기록한 것이다. 예를 들어, arr[i] = j 라 할 때, i번째 열에 j번째 행에 퀸이 놓아져 있다는 뜻이다. for(int i = 0; i < n; i++){ arr[lv] = i; if (isPossible(lv)){ backtracking(lv + 1); } } 루프를 이렇게 처리함으로써..

    [java] 백준 11660 (구간 합 구하기 5) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 11660 (구간 합 구하기 5) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net Approach DP를 활용하여 풀 수 있는 문제이다. DP[i][j] = (0, 0)부터 (i, j) 까지의 직사각형을 이루는 요소들의 합이다. 이 때, (0, 0)과 (i, j)는 직사각형의 좌상, 우하의 꼭짓점이다. 위의 DP배열을 이용하여, 좌상 꼭짓점이 (x1, y1)이고, 우하 꼭짓점이 (x2, y2)일 때, 구간 합은 다음..

    [java] 백준 14002 (가장 긴 증가하는 부분 수열 4) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 14002 (가장 긴 증가하는 부분 수열 4) Gold 4

    문제 원문 링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach 이 문제는 백준 11053번 가장 긴 증가하는 수열 의 문제에서 가장 긴 부분 수열을 추가로 출력하는 문제이다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20,..

    [java] 백준 11053 (가장 긴 증가하는 부분 수열) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 11053 (가장 긴 증가하는 부분 수열) Silver 2

    문제 원문 링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력이 1000보다 작으므로 N..

    [java] 백준 14226 (이모티콘) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 14226 (이모티콘) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net Approach DFS 를 이용한 DP문제이다. 문제의 조건 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 이 문제를 풀려면 이모티콘의 길이가 X일 때, 현재 클립보드에 저장된 이모티콘의 길이가 몇인지를 저장해 놓아야 한다. 그래야 X보다 큰 길이Y의 이모티콘을 만들 때..

티스토리툴바