알고리즘

Dynamic Programming 동적 프로그래밍

Dynamic Programming (동적 계획법) 이란? 큰 문제를 작은 문제로 나누어 푸는 문제 같은 문제라면 한 번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘 기법 ✔ 다이나믹 프로그래밍 사용 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다 📌 메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다 같은 정보를 다시 호출하면 메모했던 결과를 그대로 가져옵니다 값을 기억해둔다..

[이것이 코딩 테스트다 with Python] 부품 찾기 : 이진 탐색

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 7 이진 탐색 실전문제 7-2 부품 찾기 197p 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품..

[이것이 코딩 테스트다 with Python] 이진탐색

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 7 이진 탐색 실전문제 7-1 이진 탐색 189 문제 주어진 입력값에 대해서 이진탐색 진행해 인덱스를 출력하자 입력 조건 숫자의 갯수와 찾아야 할 숫자를 입력받고 다음줄에서 숫자 배열을 입력받는다 출력 조건 찾은 곳은 인덱스를 출력하고 없다면 원소가 존재하지 않는다는 문구를 출력한다 입력 예시 1 10 7 1 3 5 7 9 11 13 15 17 19 출력 예시 1 4 입력 예시 2 10 7 1 3 5 6 9 11 13 15 17 19 출력 예시 2 원소가 존재하지 않습니다. ✔ Solution - 재귀함수 def binary_search(array, target, start, end): if start > end: return None # 중간..

이진 탐색 알고리즘

이진 탐색(Binary Search) 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 시간 복잡도는 $O(logn)$을 가진다. ✔ 이진 탐색 과정 1. 데이터 집합(배열)의 중앙 요소를 선택합니다. 중간값 : 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 여기서 target = 9 로 한다. 2. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다. 중앙값의 7과 비교하여 9가 더 크기 때문에 왼쪽을 지우고 오른쪽에서 중앙값을 구한다. 다시 구한 중앙값은 10이다. 3. 위의 2번을..