나아가는중

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

백준 Baekjoon 11479번 통나무 건너뛰기 - JAVA 문제 풀이 가장 난이도가 낮은 배열로 만드는 방법이 무엇인지 찾아야 한다. 첫번째 통나무와 마지막 통나무도 연결된 것으로 단순히 정렬하는 것으로는 답을 구할 수가 없다. 문제에서 주어진 {2, 4, 5, 7, 9}의 답은 [2, 5, 9, 7, 4]이다. 예시를 보면 가장 작은 값들을 양 끝에 두고 가운데로 갈 수록 갚이 커진다는 것을 보고 문제 풀이를 유추할 수 있다. 주어진 입력 배열을 정렬시킨다. 정렬된 배열의 숫자를 새로운 배열 양끝에 번갈아 가며 넣는다. 배열에서 최대 난이도를 찾아 출력한다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io..

백준 Baekjoon 5212번 지구 온난화 - JAVA 문제 설명 입력받은 지도의 땅 주변의 바다의 수를 확인하여 3면이 바다인 경우 바다로 변경하고, 출력할 범위를 찾아 출력하면 되는 문제이다. 입력받은 지도에서 땅을 바다로 변경하는 경우 다른 땅의 주변 바다가 늘어나 별도의 배열을 만들어 사용해야 한다. 땅의 경우 주변 바다의 수를 검사 변경해야 하는 경우 변경 50년 후에도 땅인 경우 출력범위를 갱신 출력범위의 지도를 출력 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { pu..

백준 Baekjoon 3077번 임진왜란 - JAVA 문제 풀이 올바른 순서가 주어졌을 때, 작성한 답안을 2개씩 비교하여 순서가 올바르면 1점씩 증가한다. N이 5일 때 {0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} {3, 4} 이렇게 두개씩 짝을 지어 올바른 순서의 순서와 같은지 비교하면 된다. 해전을 HashMap을 사용하여 문자열의 순서를 저장하여 쉽게 찾을 수 있도록 하면 된다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import ja..