나아가는중

백준 Baekjoon 16235번 나무 재테크 - JAVA 문제 풀이 구현, 시뮬레이션으로 분류된 문제이다. 문제 설명을 잘 읽고 정리하여 따라 하는것으로 풀 수 있다. 풀이에 대한 설명보다 코드의 주석을 보는것이 이해가 쉬룰 것이다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..

백준 Baekjoon 2749번 피보나치 수 3 - JAVA 문제 풀이 피보나치 수의 개념을 알고 여러 문제들을 풀어봤지만, 이번 문제처럼 큰 입력은 처음으로 주어졌다. 메모리제이션을 하고 최대한 시간초과가 나지 않게 하려 해도 불가능하여 검색을 해보니 피사노라는 피보나치의 속성이 있고, 이를 활용하여 문제를 풀 수 있었다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

백준 Baekjoon 15684번 사다리 조작 - JAVA 문제 풀이 구현 + dfs + 완전탐색 문제이다. 문제가 길고 복작해서 정말 읽기 싫은 문제였다. 최대 사다리를 3개까지 놓아 i번째 사다리가 i번으로 가게 만드는 문제이다. 사다리를 입력 받을 때 양측 통행{(x,y), (x,y+1)}이 가능하도록 놓는 것이 편하다. i번에서 i번 탐색 시 좌 우 어느 방향으로 이동해야 하는지 알 수 있으며, 이렇게 하면 검사시 두 점을 검사하는 것으로 두 가로선이 연속하거나 접하지 않게 놓을 수 있다. 사다리를 최대 3개까지 놓을 수 있어 0 ~ 3개를 놓는 경우를 dfs로 검사한다. dfs 탐색 시 이미 검사한 가로선 위치(i)를 매번 검사하지 않도록 i = h에서 검사하게 한다. x는 세로 높이가 되고 y..

백준 Baekjoon 14890번 경사로 - JAVA 문제 풀이 어떠한 알고리즘을 적용하는 것이 아니라 구현을 통해 풀어야 하는 문제이다. 입력받은 지도에서 모든 행과 열을 검사하여 경사로를 놓아 길을 지날 수 있는지 검사해야 한다. 다음 칸과의 높이 차가 1이상인 경우 경사로를 놓을 수 없다. 내리막길인 경우(현재 칸 - 다음 칸 = 1), 오르막길인 경우(다음 칸 - 현재 칸 = 1) 경사로를 놓기 위해 필요한 L개의 칸을 검사하여 경사로를 놓을 수 있는지 검사한다. 1 내리막길인 경우 다음 칸부터 다음 L개의 칸을 검사한다. 2 오르막길인 경우 현재 칸부터 이전 L개의 칸을 검사한다. 이미 경사로를 놓은 칸에 경사로를 놓을 수 없다. 소스 코드 import java.io.BufferedReader;..

백준 Baekjoon 16236번 아기 상어 - JAVA 문제 풀이 문제에 있는 조건들을 잘 정리하고 bfs를 활용하여 먹을 물고기를 찾으면 풀리는 문제이다. 문제 설명이 길고 조금 복잡하여 조심히 풀어야 한다. 자세한 풀이는 소스 코드에 주석으로 하겠습니다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws ..

[백준 Baekjoon] 1700번 멀티탭 스케줄링 - JAVA 문제 풀이 그리디 알고리즘을 활용하여 해결할 수 있는 문제였습니다. 멀티탭이 모두 사용중인 경우에 가장 마지막으로 사용되는 콘센트를 찾아 제거하는데 그리디 알고리즘이 사용됩니다. 멀티탭에 꽃혀있는 전기용품을 HashSet을 사용하여 저장하도록 하였습니다. 멀티탭에 콘센트가 전부 사용중이기 전까지(HashSet size < N) HashSet에 추가해줍니다. 멀티탭의 콘센트가 전부 사용중인 경우 남은 전기용품을 순회하여 사용중인 전기용품 중 앞으로의 순서(list)와, 사용하지 않는 전기용품(remain)을 찾습니다. 이 경우 플러그를 빼는 것이므로 answer를 1증가 시킵니다. 전부 사용중인 경우 순서에서 가장 마지막으로 사용될 전기용품을..

백준 Baekjoon 1010번 다리 놓기 - JAVA 문제 풀이 입력 받은 N과 M으로 M C(combination) N 조합을 구하는 문제이다. 여러 테스트 케이스가 존재하여 미리 30 x 30 배열에 값을 구해 저장해둔다. 조합은 앞서 구한 이전 조합을 통해 다음 조합을 구하면 시간 복잡도를 줄일 수 있는 다이나믹 프로그래밍 방식이다. nC0 = nCn = 1 nCr = n-1Cr-1 + n-1Cr 이 두가지 공식을 활용하면 쉽게 풀 수 있다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public clas..

백준 Baekjoon 14003번 가장 긴 증가하는 부분 수열 5 - JAVA 문제 풀이 가장 긴 증가하는 부분 수열 문제 중 5번째 문제이다. 1번 DP문제에서 2번 부터 이분 탐색을 적용하여 푸는 문제에서 점점 더 어려워진다. 문제 설명만 보면 이전 문제들과 차이가 없어 보이는데 부분 수열을 출력하는 것이 추가 되었다. 문제를 풀기 위해 배열 2개와 리스트 하나를 만들어 사용하였다. arr 배열 : 입력 값을 저장 idx 배열 : 각 숫자의 증가 길이 저장 list : 가장 긴 증가하는 부분 수열을 저장, 길이를 알기 위해 사용 리스트 0번째에 음의 가장 작은 값을 저장하여 비교하는데 활용한다. 현재까지 저장 된 가장 긴 증가하는 부분 수열의 마지막 값과 새로 입력 받는 값을 비교하여 새로 입력 받은..

백준 Baekjoon 6087번 레이저 통신 - JAVA 문제 풀이 두 레이저를 최소한의 거울을 사용하여 연결하는 문제이다. 최소 거리로 목적지를 구하는 다익스트라 알고리즘을 여기서는 최소한의 거울로 문제를 풀면 된다. 보통의 그래프 탐색에 방향이 추가되어 현재 방향과 다른 방향으로 갈 경우 방향을 갱신하고 1을 더해주어야 한다. map을 입력받으며 만들어둔 Node class를 사용하여 시작 레이저, 도착 레이저를 저장한다. 최초에는 모든 방향이 다 가능하므로 방향 변수는 -1로 저장한다. 동시에 추후 최소 거울의 수를 갱신할 visit배열을 무한대로 초기화한다. 우선순위 큐에서 최소 거울 Node를 꺼내 4방향 탐색하며 거울 수가 더 적은 경우 갱신하고 큐에 추가한다. 시간복잡도를 줄이기 위해 우선순..

백준 Baekjoon 2851번 슈퍼마리오 - JAVA 문제 설명 문제 설명에는 중간에 먹는 것을 중단했다는 이야기 등이 나오는데, 무시하고 10개 버섯을 계속 먹는다 생각하면 된다. 계속해서 버섯의 점수를 누적하며 100과 최소 차가 나오는 경우 점수를 갱신해주면 된다. 100에 가까운 수가 2개라면 큰 값을 선택하는건 비교 조건문에서 작거나 같은 경우로 하면 된다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedRea..