[백준/BOJ] 1149 RGB거리 - JAVA - 실버1문제https://www.acmicpc.net/problem/1149문제 분석조건N개의 집이 일렬로 있다.각 집은 빨강, 초록, 파랑 중 하나로 칠해야 한다.서로 인접한 두 집은 같은 색으로 칠할 수 없다.모든 집을 칠하는 비용이 주어질 때, 전체 최소 비용을 구하는 문제이다.풀이방법i번째 집을 칠할 때는, 바로 앞 집과 같은 색을 사용할 수 없다는 제약이 존재한다.따라서 i번째 집을 빨강으로 칠한다면, i-1번째 집은 초록이나 파랑으로 칠해야 한다.이 원리를 바탕으로, 현재 집을 어떤 색으로 칠할지를 결정할 때는 이전 집에서 가능한 두 가지 색 중 더 적은 비용을 선택하여 누적해나가는 방식으로 최소 비용을 구할 수 있다.점화식에 따라 각 집을 어..

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)최장 증가 부분 수열은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘이다.예를 들어 주어진 수열이 위와 같을 때 만들어 질 수 있는 증가하는 부분 수열은 위와 같이 같은 색으로 묶인 {2, 4}, {1, 2, 3}, {1, 5, 6} 등 여러가지가 있을 수 있지만위 그림과 같이 원소 5개로 이루어진 {1, 2, 3, 5, 6}이 수열 A에서 가장 긴 증가하는 부분 수열이다. 이렇게 최장 증가 부분수열을 구하는 알고리즘에 대해 알아보자.풀이방법LIS 길이 구하기 - DP: O(n^2)LIS 길이 구하기 - 이분탐색: O(n log n)DP를 이용하여 구할 경우 구현이 간단하지만 시간복잡도가 O(n^..

[백준/BOJ] 1520 내리막 길 - JAVA - 골드3문제https://www.acmicpc.net/problem/1520문제 분석조건왼쪽 위에서 시작하여 오른쪽 아래로 이동하는 것이 목표현재 숫자보다 작은 인접한 숫자로만 이동할 수 있음가능한 경로의 수를 출력풀이방법DFS를 이용하여 경로를 탐색하며 DP를 이용하여 방문했던 점엔 다시 방문하지 않는 방법을 이용했습니다.DP 테이블을 -1로 초기화 한 뒤 출발지점부터 탐색을 시작현재 좌표에 이미 방문을 했으면 현재 좌표의 DP값을 반환하고, 첫 방문(-1)일 시 0으로 DP값을 업데이트DFS 탐색을 시계방향으로 했을 때 아래와 같은 상황이 된다.방법을 반복하여 목표 지점에 도달하였을 경우 1를 반환하고 이를 이전 좌표 DP값에 업데이트 한다.DP값을 ..

백준 BOJ 1014 컨닝 - JAVA - 플래4문제https://www.acmicpc.net/problem/1014문제 분석조건N행, M열로 배치된 좌석에서 컨닝을 못하도록 배치할 수 있는 최대 학생 수 구하기앞줄의 대각선, 좌우에 학생이 있을 경우 컨닝을 할 수 있음부서진 자리에는 앉을 수 없다.풀이방법불 끄기 문제와 비슷하게 접근하였다.(앞 행이 결정되면 뒷 행이 영향을 받음)앞행이 결정되더라도 뒷줄이 여러가지 경우의 수가 나올 수 있다는 점이 다름[백준/BOJ] 14939 불 끄기 - JAVA [백준/BOJ] 14939 불 끄기 - JAVA백준 BOJ 14939 불 끄기 - JAVA문제https://www.acmicpc.net/problem/14939문제 분석조건방의 크기는 10X10으로 일정하다..