본문 바로가기

전체 글

 (152)
Lesson 14. Binary search algorithm - MinMaxDivision 1. 문제You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty bl..
이진 탐색 (Binary Search Algorithm) 검색 범위를 줄여나가면서, 원하는 데이터를 찾는 전체 탐색 알고리즘이다.시간복잡도는 \( log{2}^{N} \) 으로 매우 빠르다.단점으로는 이미 정렬된 자료에 대해서만 사용할 수 있다. 예시) 16을 찾아보자. 1단계left index: 0right index: 14mid index: (0 + 14) / 2 = 7A[mid] 값이 찾고자 하는 값(17)보다 큰 지 작은지 확인한다. · · · · · · · · · · ①① 결과에 따라 검색 범위를 조정한다.만약 A[mid] 값이 찾고자 하는 값 보다 크다면,  찾고자 하는 값이 mid 보다 왼쪽에 있으므로,right 값을 수정한다. (right = mid - 1)만약 A[mid] 값이 찾고자 하는 값 보다 작다면, 찾고자 하는 값이 mid 보다 오른쪽..
Lesson 13. Fibonacci numbers - Ladder 1. 문제You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:  - with your first step you can stand on rung 1 or 2,  - if you are on rung K, you can move to rungs K + 1 or K + 2,  - finally you have to stand on rung N.Your task is to count the number of different ways of climbing to the top of the lad..
Lesson 13. Fibonacci numbers - FibFrog #7 (속도 개선) 1. 속도 개선 아이디어여전히 bad_alloc이 해결되지 않았다.결국 q.push 횟수를 줄여야 한다. 현재 q.push는 start_leaf 와 next_leaf에서 발생한다.결국 내가 점프할 leaf가 있냐 없느냐가 q.push 발생 여부를 결정한다. 그럼 어떻게 하면 q.push를 줄일 수 있을까? 다음과 같은 경우를 생각해보자. 파란색과 빨간색은 어느 한 지점에서 만나는데, 파란색은 2번의 점프로, 빨간색은 1번의 점프로 도착했다.우리는 피보나치라는 정해진 크기로만 점프할 수 있기 때문에, 이 후 점프(녹색)는 같을 수 밖에 없다. 따라서 우리에게는 점프 관리가 필요하다.만약 파란색이 A지점에 도착했을 때, 이미 빨간색이 1번의 점프로 도착한 사실을 알 수 있다면, 파란색은 더이상 진행할 필요가..
Lesson 13. Fibonacci numbers - FibFrog #6 (속도 개선) 1. 속도 개선 아이디어leaves를 역방향으로 탐색하는 건 어떨까? 시작 점프(starting point)를 최대한 큰 피보나치 수로 시작하면,도착지에 더 적은 점프로 도착할 확률 높지 않을까?  최소 점프를 일찍 구하게 되면, 점프 예외처리(cur_jump + 1 >= min_jump)를 통해, 처리 속도를 높일 수 있다.최소 점프가 아니더라도, 낮은 수의 점프를 일찍 구하게 되면, 속도 개선에 도움이 된다. 2. 코드 (C++)#include int solution(vector &A) { int destination = A.size() + 1; //generate fibonacci numbers vector fib = {}; fib.emplace_back(0); fib.e..
Lesson 13. Fibonacci numbers - FibFrog #5 (속도 개선) 1. 속도 개선 아이디어이전 코드에 추가할 수 있는 예외처리를 생각해보자. next_leaf가 destination을 넘어간다면, 더이상 진행할 필요가 없다(break)피보나치 수에 destination이 있다면, 단 1번의 점프로 끝낼 수 있다현재 점프 횟수가 최소 점프 횟수인지 비교(cur_jump >= min_jump)하지 말고,현재 점프에서 한번만 더 점프하면 최소 점프인지 확인(cur_jump + 1 >= min_jump)하는 형태로 수정하면q.push를 주일 수 있다현재 위치가 도착지(cur_pos == destination)인지 비교하지 말고,현재 위치에서 도착지로 점프할 수 있는지 확인하도록 수정하면q.push를 줄일 수 있다Fib를 이용한 탐색을, Fib[2]부터 시작하면 좀 더 최적화 ..
Lesson 13. Fibonacci numbers - FibFrog #4 (속도 개선) 1. 속도 개선 아이디어이전까지 점프 가능한 잎들만 따로 모아뒀었다. (leave)leave는 특정 케이스에서는 탐색 횟수가 줄어든다는 장점을 가지지만, 극단적인 경우에서는 단점으로 작용한다.예를들어 테스트 케이스가 다음과 같다면? {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}leave만드는 것이 의미 없어진다. leave를 만들지 않고, vector A를 그대로 사용한다면 탐색에 대해서도 다시 생각해 볼 수 있다. 현재 탐색IF leave[i] \( - \) leave[cur_pos] \( = \) fibonacci number THEN    jumpEND IF 수정 탐색next_leaf = i + Fib[K]IF A[next_leaf] = 1 THEN    jump..
Lesson 13. Fibonacci numbers - FibFrog #3 (속도 개선) 1. 속도 개선 아이디어아무래도 재귀함수로는 한계가 있어보인다.너비 우선 탐색(BFS, Breadth First Search)을 이용해서 전체 탐색하도록 수정해 보자. 2. 코드 (C++)BFS로 전체 탐색 구현#include int solution(vector &A) { int destination = A.size() + 1; //generate fibonacci numbers vector fib = {}; fib.emplace_back(0); fib.emplace_back(1); int M = 2; int n = fib[1] + fib[0]; while(n leaves = {}; leaves.emplace_back(0); for(size_t i ..

티스토리툴바