나아가는중

백준 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..

백준 Baekjoon 5972번 택배 배송 - JAVA 문제 풀이 다익스트라 알고리즘 문제이다. 1번 헛간에서 N번 헛간까지 가는 최소한의 소들을 만나며 지나가는 비용을 찾아 출력하면 된다. 여러 방법으로 다익스트라를 구현할 수 있는데 연결리스트 배열과 우선순위 큐를 사용하여 풀었다. 헛간간에 무방향이기 때문에 양방향으로 헛간의 정보를 입력 받는다. 모든 방법을 탐색하는 것이 아닌 우선순위 큐를 사용하여 시간 복잡도를 줄였다. 시작점인 1번 헛간 이외의 헛간은 최대길이로 초기화 하고 이를 비교하며 최소 비용을 갱신하는 방법을 사용하였다. 현재 비용과 새로운 비용을 비교하여 해당 헛간으로 가는 비용이 더 적은 경우에만 큐에 추가하는 방식이다. boolean배열을 만들어 이미 방문한 헛간은 다시 방문하지 않..

백준 Baekjoon 10157번 자리배정 - JAVA 문제 풀이 대기 순서가 K인 관객에게 배정될 좌석 번호(x,y)를 찾는 문제이다. 문제 설명에서 주어졌듯이 배열을 달팽이 모형으로 순회하며 K번째가 될때 위치를 출력해주면 된다. 배열을 달팽이 모형으로 순회할줄만 알면 어렵지 않은 문제이다. 초기 위치를 x = R - 1, y = 0으로 방향은 위, 오른쪽, 아래, 왼쪽 순으로 초기화 하였다. while문에서 k번째가 될때까지 횟수 cnt를 증가 시키며 k가 될때에 종료된다. 다음으로 배정될 좌석을 찾고 지도 밖으로 벗어나거나 이미 배정된 자리인 경우 방향을 돌려 배정하도록 하였다. - 처음 한바퀴를 돌 때에는 0보다 작거나 R, C보다 크면 지도 밖을 벗어난다. - 그다음 바퀴부터는 이미 배정된 좌..

백준 Baekjoon 1389번 케빈 베이컨의 6단계 법칙 - JAVA 문제 설명 문제 설명이 길고 복잡한데 플로이드 와샬 알고리즘을 적용하면 쉬게 풀리는 문제입니다. 2차원 배열 distance를 만들어 자기 자신이외는 전부 INF(무한대)로 초기화 합니다. 다음 입력받는 연결에 대하여 양방향으로 A-B, B-A를 1로 저장 합니다. 아래의 3차원 for문을 사용하여 각각의 단계로 가는 최소값을 갱신합니다. 마지막으로 그중 가장 작은 합이 정답이 됩니다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util..