이진 탐색(Binary Search)
배열이 정렬되어 있을 때, 가운데 값과 비교하여 찾고자하는 값이 더 크면 오른쪽을 작다면 왼쪽을 탐색하는 방식 예시 [2, 5, 7, 9, 14, 19, 20, 24]가 있을 때 만약 2를 찾고 싶다면 가운데 값인 14와 비교를 하면 더 작기 때문에 다시 왼쪽 부분인 [2, 5, 7, 9]에서 같은 방식으로 반복한다. 최종적으로 2를 찾아 인덱스를 리턴하게 된다. 장점 시간복잡도가 log n으로 상당히 빠르다. 완전 탐색을 수행했을 때 시간 초과가 나는 여러 문제에서 활용될 수 있다. 구현 재귀로 구현 int recursive_binarySearch(vector arr, int start, int end, int target){ if(start > end) return -1; int mid = (star..
2022. 3. 3.
프로그래머스 - N으로 표현 / C++
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 풀이 N으로 표현할 수 있는 경우는 N 한 가지이다. 이를 DP[0]이라고 하면 DP[0] = { N }이다. N 2개로 표현할 수 있는 경우는 NN, (N+N, N-N, N*N, N/N) 이며 이를 DP[1]이라 하면 DP[1] = { NN, N+N, N-N, N*N, N/N } 이다. N 3개로 표현할 수 있는 경우는 NNN, (NN+N, NN-N, NN*N, NN/N), {(N+N)+N), (N+N)-N, (N+N)*N, (N+N)/N}, ... 이다. 이를 DP[2]라 하면 DP[2]는 DP[1]와 DP[0]의 사..
2022. 3. 2.