DP

    [Java] 백준 16639 (괄호 추가하기 3) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16639 (괄호 추가하기 3) Gold 1

    Problem : https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net Approach 괄호 추가하기 2와 같은 BruteForce 문제가 아닌 DP 문제로, 아예 다른 유형의 문제였다. 중첩된 괄호가 있을 수도 있고, 괄호 안에 여러 연산자가 존재할 수도 있기에, 연산자들의 우선순위는 고려할 사항이 아니다. 따라서 수식의 i ~ j까지의 결과는 i ~ k의 결과 + k ~ j의 결과 임을 이용하면 된다. 주의할 점은 (음수) * (..

    [Java] 백준 17069 (파이프 옮기기 2) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17069 (파이프 옮기기 2) Gold 5

    Problem : https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net Approach DP 로 문제를 풀이했다. 백준 17070 (파이프 옮기기 1)와 똑같은 문제지만, 문제의 입력 부분에 차이가 있다. [java] 백준 17070 (파이프 옮기기 1) Gold 5 문제 원문 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 ..

    [Java] 백준 21774 (가희와 로그 파일) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21774 (가희와 로그 파일) Gold 3

    Problem : https://www.acmicpc.net/problem/21774 21774번: 가희와 로그 파일 2000년부터 2020년까지 연도 중에, 윤년인 것은 2000, 2004, 2008, 2012, 2016, 2020년 입니다. www.acmicpc.net Approach 문자열을 파싱하여 DP를 구성하고, 이분 탐색의 lowerbound, upperbound를 활용해야 하는 문제이다. 문제 풀이의 로직은 다음과 같다. 먼저 문자열을 파싱한다. 주어진 시각 문자열이 YYYY-MM-DD hh:mm:ss 형식이고 순서대로 주어지므로, -:와 공백문자를 없애면 자연스럽게 정렬이 된 상태가 된다. (본인은 Long 타입으로 형변환을 하였지만, String 타입이어도 자연스럽게 사전순으로 정렬 상..

    [Java] 백준 6087 (레이저 통신) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 6087 (레이저 통신) Gold 4

    Problem : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net Approach BFS + DP 문제라고 볼 수 있다. 특정 위치 (x, y)를 방문하는 방법은 여러 방법이 있는데, 그 중 방향 전환을 최소로 하는 방문을 찾는 문제이다. 문제에서 거울이라는 개념이 나오는데, 쉽게 말하여 방향이 변하는 곳엔 거울을 놓을 수 밖에 없다. 따라서, 목표 위치 (x, y)를 방문하는 방법 중, 방향 전환이 최소인 방문을 찾으면 된다. cha..

    [Java] 백준 2096 (내려가기) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2096 (내려가기) Gold 4

    Problem : https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net Approach 간단한 DP 문제로 생각하고 풀었다. DP의 점화식은 문제에서 알려주고 있기 때문에 따로 언급은 하지 않겠다. 최솟값 배열과 최댓값 배열을 따로 두어, 한 번 순회하며 두 값을 각각 갱신하였다. 마지막 줄을 검사하여 최종최댓값과 최종최솟값을 구하면 된다. Code import java.io.*; import java.util.StringTokenizer; /** * No.209..

    [Java] 백준 1937 (욕심쟁이 판다) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1937 (욕심쟁이 판다) Gold 3

    Problem : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net Approach 어느 한 지점으로부터 시작하여 최대 몇개의 지점을 방문할 수 있는지를 판단하는 DFS문제이다. DFS는 인접행렬의 경우 O(n^2)의 시간복잡도를 가지고 있어, n의 크기가 크다면 모든 지점을 시작지점으로 하여 DFS하기에는 시간초과가 뜰 것이다. (O(n^2 * n^2)) 따라서 위와 같이 시간초과를 피하기 위하여, 모든 점을 시작지점으로 DFS를 수행..

    [Java] 백준 2098 (외판원 순회) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2098 (외판원 순회) Gold 1

    Problem : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net Approach 대표적인 외판원 문제 (TSP: Traveling Salesman Problem) 이다. 어떤 지점 A에서 모든 지점을 돌아 다시 A로 오는 최소 비용 경로를 찾으면 된다. (완전탐색) 시작 지점은 아무 곳에서 시작해도 된다. 어디서 시작하든 최소 비용 사이클은 동일하기 때문이다. 코드의 주석처럼 도시가 4개일 때, 1001이..

    [Java] 백준 1562 (계단 수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1562 (계단 수) Gold 1

    Problem : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach Bitmasking을 이용한 DP문제였다. 그냥 계단수를 구하는 문제를 풀어본 기억이 있어 일단 DP를 떠올렸다. 그리고 보통 사용한 숫자를 체크할 때에는 Bitmasking을 사용했기에 이 문제도 그렇게 접근해 보았다. i자리 계단수를 구하는 방법은 i-1자리 계단수의 끝자리에 +1 한 숫자와 -1 한 숫자를 붙인 계단수의 합이다. 하지만 끝자리가 0과 9인 경우에는 각각 +1한 숫자, -1한 숫자만 고려해야한다. 34가 계단수임을 알고 있으면 343도(-1한 숫자를 붙인 것) 계단수..

    [java] 프로그래머스 (멀리 뛰기) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (멀리 뛰기) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr Approach 매우 간단한 DP 문제이다. DP[i] 를 i 칸에 도달할 수 있는 방법의 수라고 하였을 때, i 칸에 도달할 수 있는 방법은 (i - 2 칸에서 2칸으로 움직였을 경우) + (i - 1 칸에서 1칸으로 움직였을 경우)이다. 위의 문자대로 DP[i] = DP[i - 2] ..

    [java] 프로그래머스 (거스름돈) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (거스름돈) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr Approach 백준 온라인 저지에서도 DP 카테고리의 문제를 풀어봤다면, 비슷한 문제를 보았을 것이다. 꽤나 유명한 DP문제이고, 아마 나는 KnapSack 문제로 풀었던 것 같다. 하지만 여기서는 KnapSack처럼 2차원배열을 가지고 풀면 효율성테스트에서 시간초과가 발생하므로, 1차원배열로 풀이하여야 한다. DP[i] 를 i ..

티스토리툴바