david의 CS Blog

1. 계산 로봇 https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 각 칸에 있는 로봇이 입력값, 저장값, 출력값을 가지므로 이해를 위해 입력값, 저장값, 출력값을 저장하는 2차원 배열 3개를 만들어보자. 각 로봇들의 입력값은 로봇의 위치(x, y)를 기준으로 왼쪽에 있고, |i-a|≤j-b를 만족하는 (a, b)에 있는 로봇들의 출력값이다. 로봇의 저장값은 입력값들의 최댓값이고, 저장값에 자신들의 가중치를 더한 값이 출력값이다. 이제 배열들..

Binary Search 데이터를 효율적으로 탐색하기 위해서는 탐색 공간이 효율적으로 구성되었는지와, 탐색 알고리즘이 잘 설계되어 있는지를 고려해야 한다. 탐색 알고리즘이 잘 설계되었다는 것은 해가 될 가능성이 높은 데이터를 위주로 탐색한다는 것으로, 해를 찾기 위한 연산 횟수의 상한(upper bound)이 작을수록 좋다. 이분탐색은 그러한 탐색 횟수의 상한을 $logN">logN$으로 보장하는 탐색 알고리즘이다. Binary Search라는 이름에 걸맞게, 매 시행마다 탐색 구간을 절반씩 줄여나가면서 탐색을 진행하는 알고리즘이다. 일반적인 탐색 방법과 비교하기 위해 다음과 같은 문제를 해결해보자.   [1,N]">$[1, N]$ 수열에서 정수 $K$는 어느 인덱스 값을 가지는가?( $KK&#x2208..