:: ADVANCE ::

BAEKJOON ONLINE JUDGE 2531 회전 초밥 https://www.acmicpc.net/problem/2531 연속해서 먹을 수 있는 접시가 k 개 이기 때문에 회전(순환)의 경우 배열을 추가로 k개 더 선언하여 뒤에 더 입력하였다. dp로 문제를 풀었다. dp[마지막으로 먹은 초밥의 index] = index의 초밥을 마지막으로 먹었을 경우 최대로 먹은 초밥의 가짓 수 k개 안에 중복되는 초밥번호가 있을 경우 더이상 수를 세면 안되기 때문에 이를 처리해야 한다.초밥의 접시 여부를 판단하는 배열을 선언하여 i 번째 초밥을 추가하면 i - k의 초밥을 빼 준다. 또한 연속으로 초밥을 먹으면서 쿠폰 번호와 동일한 초밥을 먹을 수 있으므로 이를 판단하여야 한다.dp를 채워나갈 때 같이 계산을 하..

BAEKJOON ONLINE JUDGE 7579 앱 https://www.acmicpc.net/problem/7579 DP! 최소의 비용문제의 핵심은 입력 메모리 값을 적절히 조합하여 합이 필요한 메모리 M 이상을 만드는데, 그 중 cost가 가장 작은 값을 출력하는 것이다.단순히 완전히 탐색을 하여 메모리 조합을 찾는 경우에는 당연히 Time Limit가 발생한다.따라서 DP로 문제를 풀어야 하는데처음에는 dp[메모리] = cost(최소값) 로 생각을 하여dp의 index(memory)가 입력 기준을 처음으로 넘는 cost를 출력하려 하였으나 메모리 범위가 넓어 배열을 잡을 수 없다. ---> 반대로!!index와 값을 반대로 하여 보자dp[cost] = memory(최대값) 입력 메모리와 cost를 ..

[Binary Search] 이진 탐색 이진 탐색 Binary Search (이분 탐색이라고도 한다.) 이진 탐색은 순차 탐색과 달리 모든 경우를 다 탐색하지 않습니다.이진 탐색이란 한번 비교를 거칠 때 탐색 범위를 반으로 줄여가며 탐색을 하는 방법입니다.따라서 이진 탐색의 시간 복잡도는 O(logN)입니다. 이진 탐색의 경우 조건은 앞으로의 탐색 과정을 보면 알겠지만, 값이 정렬되어 있어야 한다는 것이다.배열에 값이 저장되어 있던, 어떤 특정한 값을 찾던지 간에 탐색해 가는 과정에서 범위를 줄이기 위해서는 정렬을 통해 더이상의 가능성이 존재하지 않는다는 보장이 되어 있어야 하기 때문이다. 이진 탐색의 탐색 과정 245791012152125 위와 같이 정렬된 배열에서 이진 탐색 알고리즘을 적용하여 데이터..