💻 Computer Science/Algorithm

이분 탐색(Binary Search)

오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘입니다. 배열 전체의 중간값을 target 값과 비교 중간값이 target 값보다 크면 왼쪽 부분만 선택 왼쪽부분의 중간값을 다시 target 과 비교 정방향으로 푸는 방법과 재귀로 푸는 방법 두 가지가 있습니다. 정방향도 어떻게 보면 개념적으로는 재귀로 푸는 방법과 같은 방법입니다. 개념 정렬된 자료를 반으로 나누어 탐색하는 방법 주의점 : 자료는 오름차순 으로 정렬된 자료여야 한다. 이진트리, 바이너리서치는 코딩 인터뷰 단골문제 퍼포먼스가 아주 좋고 구현하는 중에 dynamic programming, recursion을 볼 수 있다. 특징 linear search (순차검색) : 순서대로 찾는다. 성능평가시 비교대상으로 사용한다. ..

동적 계획법(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 흔히 말하는 DP가 바로 '동적 계획법' 한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다. 즉, 똑같은 연산을 반복하지 않도록 만들어준다. 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이라고 할 수 있다. 동적 계획법은 Optimal Substructure에서 효과를 발휘한다. Optimal Substructure : 답을 구하기 위해 이미 했던 똑같은 계산을 계속 반복하는 문제 구조 접근 방식 커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하다. 하지만 간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점이 존재한다. 모든 답을 만들어보고 그 중 최적해의 점수를 반환..