(알고리즘) 이진 탐색 1. 이진 탐색 (Binary Search) 이란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 데이터가 정렬이 되어 있다는 전제 하에 사용 가능 다음 문제를 먼저 생각해보자 이진 탐색의 이해 (순차 탐색과 비교하며 이해하기) 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를 두 개의 서브 리스트로 나눈다. Comquer 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다. 검색할 숫자 (search) < .. (알고리즘) 재귀용법 1. 재귀 용법 (recursive call, 재귀 호출) 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘 작성시 사용되므로, 익숙해져야 함 2. 재귀 용법 이해 예제를 풀어보며, 재귀 용법을 이해해보기 예제 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기 예제 - 분석하기 간단한 경우부터 생각해보기 2! = 1 X 2 3! = 1 X 2 X 3 4! = 1 X 2 X 3 X 4 = 4 X 3! 규칙이 보임: n! = n X (n - 1)! 함수를 하나 만든다. 함수(n) 은 n > 1 이면 return n X 함수(n - 1) 함수(n) 은 n = 1 이면 return n 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함) 먼저 2! .. (알고리즘) 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total.. (알고리즘) 알고리즘 복잡도 표현 기법 알고리즘 복잡도 표현 방법¶ 1. 알고리즘 복잡도 계산이 필요한 이유¶하나의 문제를 푸는 알고리즘은 다양할 수 있음¶ 정수의 절대값 구하기 1, -1 ->> 1 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 2. 알고리즘 복잡도 계산 항목¶ 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 알고리즘 시간 복잡도의 주요 요소¶반복문이 지배합니다. 생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미.. 이전 1 다음
