백준

[백준] 1746번 - 듣보잡 (JAVA) [ 접근 과정 ] HashMap을 활용하여 해결하였다. 듣도 못한 사람이름을 key 로 하고, value는 1로 한다. 해시에 해당 key가 존재하는지를 판단하는 containsKey 함수를 활용하여 듣도 못한 사람과 보도 못한 사람에 동시에 선정된 사람을 찾아낸다. [ JAVA 코드 ] // 1764번 - 듣보잡 // 해시로 해결해보기 import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { // 0. 입출력 선언 / 초기화 BufferedReader br = new BufferedReader(new InputStream..

1. 배열을 이용한 방법 배열 + 이진탐색 (상위 탐색, 하위 탐색) 사용 1. 배열을 정렬 2. 정렬된 배열의 상위 부터 탐색 하여 나온 인덱스 와 하위 부터 탐색하여 나온 인덱스를 이용하여 숫자의 개수 도출 import java.util.*; import java.io.*; class Main { static int N, M; public static int lowerBound(ArrayList array, int target){ int lo = 0, hi = array.size(), mid; while (lo < hi) { mid = (lo + hi) / 2; if (target

[백준] 점프 점프 (11060번 JAVA) / DP [접근 방법] arr 배열로 Ai 배열을 입력 받는다. DP 배열은 현재 위치 까지 이동하는데 소요된 "최소 점프 수" 이다. 현재 위치인 2에서 점프 가능한 칸 수가 3인 경우, 3, 4, 5으로 이동가능 하다. 따라서, DP[3], DP[4], DP[5] 값은 "DP[2] + 1" 으로 갱신 된다. arr[3] = 2 이므로, 4, 5로 이동 가능하다. 이때, 기존 DP[4] 와 DP[5]에 값이 존재하므로, 기존 DP[4] = 2의 경우 (1 -> 2 -> 4) 와 (1 -> 2 -> 3 -> 4)의 경우 중 점프 횟수가 더 작은 값으로 갱신 한다. 완성된 DP는 다음과 같다. [JAVA 코드] // 11060 - 점프 점프 import java..

[백준] BOJ 거리 (12026번 JAVA) / DP [접근 방법] 스타트는 항상 B 이다. B - > O - > J 순으로 이동하여야 한다. DP 배열의 의미는 해당 위치 까지 "이동하는데 든 에너지의 최솟값" 이다, 현재 위치의 문자가 B 라면, 다음 이동 가능한 문자인 O에 대하여, 현재 위치의 문자가 O 라면, 다음 이동 가능한 문자인 J에 대하여, 현재 위치의 문자가 J 라면, 다음 이동 가능한 문자인 B에 대하여, 탐색하여 가장 적은 에너지를 소모하는 것을 DP에 저장한다. 1

[백준] 점프 (!) (1890번 JAVA) / DP [ 접근 방법 ] 게임 판에 적혀있는 '이동 가능 거리' 를 arr 2차원 배열에 저장 해당 좌표까지 도착 할 수 있는 방법 수 를 DP 2차원 배열에 저장 좌표 (1, 1) 부터 (N, N) 까지 DP 시작 한다. 예제로 설명한다면, [입력값] [DP 출력] DP의 (1,1)을 초기값으로 1로 설정한다. (1, 1)에서 '이동 가능 거리'는 ' 2 ' 이다. (1, 1) -> (3, 1) (1, 1) -> (1, 3) 으로 이동 가능하다. 이와 같은 방법으로 한다면, 위와 같은 DP 출력 값이 나오게 된다. [ JAVA 코드 ] // 1890번 점프 import java.util.*; import java.io.*; class Main { publi..

[백준] 퇴사 (!) (14501번 JAVA) / DP [접근 방법] * 물리적으로 불가능한 것 (퇴사 후엔 상담이 불가능) 을 제외한다. (N = 7인 경우, 7일차에 2일이 걸리는 상담을 할 수 없다.) 역방향으로 DP를 도출한다. N -> 1 순으로, for (i = N -> 1 까지 i--){ // 물리적으로 불가능한 것 제외 if ( 현재 일자(i) + 상담에 드는 기간(T[i]) > N + 1 ){ DP[i] = DP[i+1]; } else { i 날짜의 일을 하는 경우 => DP[i + T[i]] + P[i] i 날짜의 일을 하지 않는 경우 => DP[i+1] 중 최댓값 구하기 } } [JAVA 코드] // 14501 - 퇴사 import java.util.*; import java.io.*..