코딩관계론

아이디어 도출 방법 주어진 문제는 search배열(n)에서 특정 숫자(m)를 찾는 문제였다. 하지만 배열의 길이가 크고, 찾고자 하는 특정 숫자가 많아지면 이중반복문으로는 해결하기 어렵다. 따라서 이중 반복문을 제거하고, 주어진 배열에서 더 빠르게 탐색할 수 있는 알고리즘이 필요한데 이것이 이분 탐색이다. 이분 탐색은 기존의 O(n)의 시간 복잡도를 O(logn)으로 줄여준다. 이런 방법을 사용한다면 기존의 O(n*n)의 시간 복잡도에서 O(nlogn) + O(mlogn)으로 개선할 수 있다. 또한 이분 탐색을 하기 전 필수적으로 수행되어야 할 것은 '특정 배열'(주어진 숫자를 찾고자 하는 배열)이 정렬되어 있어야 한다. 최종 결과 n = int(input()) search = list(map(int, ..

변수 설명 N[] = 모래의 초기 상태 a, b deg = a이상 b이하 deg만큼 모래를 채워라(빼라) 풀이 a~b까지 deg를 누적해서 더해주고 b + 1에서 deg를 소멸시켜주자 누적해서 더해주는 것은 각 인덱스에 무엇을 얼만큼 더해야 하는지 알려주기 때문에 누적하는 것이 굉장히 중요하다. 여기서 문제점은 a ~ b까지 deg를 누적해서 더했다면 n[b + 1] = [b] + b[n + 1]이 된다. n[b + 1]에서는 deg값을 인덱스마다 누적 할 필요가 없는데 어떻게 하면 소멸할 수 있을까를 고민하면 된다. b[n + 1]에 -deg 값을 넣음으로써 해당하는 누적 값을 없앨 수 있다. 풀이 def make_psum(arr): psum = [] psum.append(arr[0]) for i in..