"탐색 (Search)" 알고리즘에 대해 알아보자. 탐색 알고리즘은 "저장된 데이터들 중 원하는 데이터를 찾는 알고리즘" 이다. 다양한 탐색 방식의 알고리즘이 존재한다. 각각의 탐색 방식과 시간복잡도 등 다양한 형태에 따라 적절한 탐색 알고리즘을 적용한다. 탐색 알고리즘 1. 선형탐색 (Linear Search) : 한쪽 끝에서 하나하나 순서대로 탐색하여 원하는 값을 찾는 알고리즘. (- 정렬되지 않은 배열도 가능) 선형 탐색은 순차 탐색 이라고도 불린다. 장점은 탐색 알고리즘의 가장 간단하고 직접적인 방법으로, 구현하기 쉽다. 그러나, 배열의 크기에 직접적인 영향을 받는다. (일반적으로 배열이 클수록 시간이 많이 든다.) * 시간복잡도 Best Case : 배열의 첫 부분(탐색하는 첫 데이터)이 key..
전체 글
[백준] 점프 점프 (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.*..
[백준] 연속합 2 (!) (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 첫번째 방법 ) DP를 1차원 배열로 2가지 구성 Left -> Right (index : 0 -> n-1) 방향으로 연속합 DP1 배열 을 구성 Right -> Left (index : n-1 -> 0) 방향으로 연속합 DP2 배열 을 구성 index : i 의 원소를 제외하는 경우의 연속합 최댓값을 갱신하며 구한다. i 번째 원소를 제외한 연속합 = DP1[i-1] + DP2[i+1] 두번째 방법 ) DP를 2차원 배열로 구성 [JAVA 코드 - 첫번째 방법] import java.io.BufferedReader; import java.io.BufferedWriter; import java...