DP

    [java] 프로그래머스 (보행자 천국) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (보행자 천국) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1832 Approach 2017 카카오코드 예선 문제이다. DP를 이용하되, 두개의 DP를 유지하여야 하는 문제이다. 어느 한 지점 (x, y)에 대하여 그 점에 세로방향 길로 도착했는지, 가로방향 길로 도착했는지, 두개의 DP배열을 유지해야한다. 왜냐하면, 현재 위치 (x, y)에 회전금지 표지판이 있으면, 직진으로만 다음 위치로 갈 수 있기 때문이다. 따라서, 일반적으로 DP를 수행하되, 세로방향 길인지, 가로방향 길인지에 따라 다르게 처리를 해준 후, 목적지 (ex, ey) 를 세로방향 길로 도착할 수 있는 경우의 수와 가로방향 길로 도착할 수 있는 경우의 수를 더한다음 문제에서 요구한것처..

    [java] 프로그래머스 (순위) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (순위) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr Approach 플로이드-와샬 알고리즘을 활용하여 풀 수 있는 의외의 문제이다. 기본적인 메커니즘은 이렇다. result에 {1, 2}, {2, 3}이 있다면, (1, 3)도 결정된다. 경기결과에 없더라도 1과 3사이에 순위를 매길 수 있다. 그런 후, (i, j)와 (j, i)가 모두 갱신이 안되었다면, i 는 순위가 확정되지 않았다고 취급할 수 있다. 먼저 DP배열을 생성한 후, 초기화를 진행한다. (경기결과를 DP배열에 반영) 플로이드-와샬 알고..

    [java] 프로그래머스 (등굣길) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (등굣길) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr Approach 간단한 DP문제이다. 주의할 점은 문제에서 주어진 예시그림과 주어진 데이터가 불일치한다는 점을 알고 가야한다. 문제의 그림에서는 m = 4, n = 3이지만, 3 x 4 지도가 나와있어 n이 행의 개수, m이 열의 개수라고 생각할 수 있겠지만, 그렇게 푼다면 런타임에러가 계속 뜰 것이다. m을 행의 개수, n을 열의 ..

    [java] 프로그래머스 (정수 삼각형) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (정수 삼각형) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr Approach 대표적인 DP 문제이다. 문제에서 보이기는 정삼각형이지만, 배열로 구현하게 되면 왼쪽 하단이 직각을 이루는 직각삼각형이 된다. 따라서 점화식도 간단하게 유추가 가능하다. 점화식은 DP[i][j] = max(DP[i - 1][j - 1], DP[i - 1][j]) + triangle[i][j] 이다. 주의할 점은 삼각형의 변에 해당하는 경우에는 오는 경로가 하나 뿐이므로 예외적으로 처리해 주어야한다. 삼각..

    [java] 프로그래머스 (피보나치 수) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (피보나치 수) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr Approach 간단히 DP를 이용하여 n번째 피보나치 수 % 1234567를 구하는 문제이다. Code public class Fibonacci { public static void main(String[] args) { int n = 5; Fibonacci f = new Fibonacci(); System.out.pri..

    [java] 백준 1915 (가장 큰 정사각형) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1915 (가장 큰 정사각형) Gold 5

    Problem : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net Approach DP로 풀 수 있는 문제로, DP[i][j] 는 (i, j) 위치에서 좌상으로 진행했을 때 만들수 있는 가장 큰 정사각형의 한 변의 길이이다. 따라서 주어진 board[i][j] 가 1이라면 일단 최소 1x1 정사각형을 만들 수 있으므로 dp[i][j] = 1을 저장한다. 그리고 board[i][j - 1], board[i - 1][j], board[i - 1][j - 1]이 모두 1이라면 DP[i][j]에 min(DP[i][j - ..

    [java] 프로그래머스 (가장 큰 정사각형 찾기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (가장 큰 정사각형 찾기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr Approach 이 문제는 백준 1915번 가장 큰 정사각형 문제와 유사하다. 아래는 내 풀이에 대한 포스팅이다. 2021/01/13 - [Algorithm/Baekjoon Online Judge] - [java] 백준 1915 (가장 큰 정사각형) Gold 5 [java] 백준 1915 (가장 큰 정사각형) Gold 5 Problem : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 ..

    [java] 백준 9019 (DSLR) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9019 (DSLR) Gold 5

    Problem : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net Approach BFS + DP + Tracing 을 사용하여 풀이한 문제이다. 필자는 위의 과정보다 숫자를 만드는 작업이 더 어려웠다.(어렵다기보다 생각할 조건들이 많아서 귀찮았다.) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S ..

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

    [java] 백준 9252 (LCS 2) Gold 5

    Problem : https://www.acmicpc.net/problem/9252 9252번: LCS 2 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)를 비교한 후, 그 때까지의 ..

    [java] 백준 2629 (양팔저울) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 2629 (양팔저울) Gold 2

    Problem : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net Approach 주어진 추들의 무게로 구슬의 무게를 확인할 수 있는지를 판단하는 문제였다. 구슬을 목적지라고 가정한다면, 목적지를 갈 수 있는지를 판단하는 문제다. 따라서 필자는 깊이우선탐색을 이용하여 풀이를 하였다. 일단, 탐색 진행 방법에는 3가지 방법이 있다. 무게를 확인할 구슬은 항상 저울의 왼쪽에 놓는다고 가정하였을 때, 다음 구슬을 저울의 오른쪽에 올리는 경우(w + w..

티스토리툴바