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

[백준/BOJ] 12946 하노이의 탑 - JAVA - Lv2문제https://school.programmers.co.kr/learn/courses/30/lessons/12946 문제 분석조건한 번에 한 개의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 올라갈 수 없다.세 개의 기둥을 이용해 모든 원판을 시작 기둥에서 목표 기둥으로 옮겨야 한다.풀이방법원판이 1개일 경우, 시작 기둥에서 목표 기둥으로 바로 옮긴다.원판이 N개일 경우, 가장 큰 N번 원판을 목표 기둥으로 옮기기 위해 다음을 반복한다.N-1개의 원판을 보조 기둥으로 옮긴다.N번 원판을 목표 기둥으로 옮긴다.보조 기둥에 있던 N-1개의 원판을 목표 기둥으로 옮긴다.이 과정을 재귀적으로 반복하여 모든 원판을 이동시킨다.코드import ja..

[프로그래머스] 43162 네트워크 - JAVA - Lv3문제https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분석조건배열로 연결관계가 포함된 컴퓨터가 있다.컴퓨터끼리 직접, 혹은 간접적으로 연결되어 있으면 같은 네트워크라 하는데 전체 네트워크의 수를 구하는 문제풀이방법0번 컴퓨터부터 n-1번 컴퓨터까지 반복문을 돌면서 방문하지 않은 컴퓨터에서 BFS를 돌린다.코드import java.util.*;class Solution { public int solution(int n, int[]..

최장 증가 부분 수열(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 11053 가장 긴 증가하는 부분 수열 - JAVA - 실버2문제https://www.acmicpc.net/problem/11053문제 분석조건첫째 줄에 수열의 크기, 둘째 줄에 수열이 주어짐가장 긴 증가하는 부분 수열의 길이 출력풀이방법LIS 알고리즘을 활용하여 풀이코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Bu..

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