파이썬75 Python 자료구조&알고리즘 - 순차 탐색, 이진 탐색 1. 순차 탐색(Sequential Search) 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 1. 이진 탐색(Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방 1-1. 이진 탐색과 순차 탐색의 비교 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 divide : 문제를 하나 또는 둘 이상으로 나눔 conquer : 나눠진 문제가 충분히 작고 해결이 가능하면 해결하고, 그렇지 않으면 다시 나눔 이진 탐색 divide : 리스트를 두 개의 서브 리스트로 나눔 conquer : 검색할 숫자 > 증가값 : 뒷 부분의 서브 리스트에서 검색힐 숫자를 찾음 검색할 .. 2023. 2. 22. Python 자료구조&알고리즘 - 분할 정복 1. 분할 정복(Division Conquer) 문제를 나눌 수 없을 떄까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 하향식 접근방법으로 상위의 해당을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식(재귀함구로 구현) 문제를 잘게 쪼갤때 부분 문제는 서로 중복되지 않음 Memorization 기법을 사용하지 않음 2. 대표적인 분할 정복 알고리즘 : 퀵 정렬(quick sort 정렬 알고리즘의 꽃(고급 알고리즘) 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽, 오른쪽은 재귀용법으로 사용해 다시 동일 함수로 호출하여 위 작업을 반복함 2-1. 퀵 정렬 알고리즘 구현 리스트 개수가 1개면 해당 리스트를 리턴 리.. 2023. 2. 22. Python 자료구조&알고리즘 - 동적 계획법, 백준 11726번 1. 동적 계획법(Dynamic Programming) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분의 값을 활용해서 보다 큰 크기의 부분 문제를 해결함 상향식 접근법(최하위 해답을 구한 후 해당 결과를 이용해서 상위 문제를 풀어가는 방식) 프로그램 실행 시 이전의 계산한 값을 저장하여 다시 계산하지 않도록 전체 실행 속도를 빠르게 하는 기술(메모이제이션 : Memoization)을 사용 문제를 잘게 쪼갤 때, 부분 문제는 중복되기 때문에 재활용 2. 동적 계획법 알고리즘 피보나치 수열 n을 입력받아서 아래와 같이 계산 피보나치 수열 함수흫 '피보나치' fibonacci(0) : 0 fibonacci(1) : 1 fibonacci(2) : 1 fibonacci(3) : 2 fibonacci(4).. 2023. 2. 21. Python 자료구조 & 알고리즘 - 재귀호출 1. 재귀호출(recusive call) 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘, 고급 정렬 알고히즘 작성시 자주 사용됨 1-1. 재귀 호출 분석 2! = 1 * 2 3! = 1 * 2 * 3 4! = 1 * 2 * 3 * 4 = 3! * 4 1-2. 규칙 n! = n * (n-1)! 함수로 만들어 보자 함수(n)은 n=1 함수(n)은 n>1 이면 return n*함수(n-1) 1-3. 검증 2! 함수(2)이면 2>1 이므로 2 * 함수(1) 함수(1)은 1이므로 return 2 * 1, 답은 2 3! 함수(3)이면 3>1 이므로 3 * 함수(2) 함수(2)는 위 계산에 의해 2! 이므로 return 2*1 = 2 3 * 함수(2) = 3 * 2 = 3 * 2 * 1, 답은 6 4! 함수.. 2023. 2. 21. 이전 1 ··· 4 5 6 7 8 9 10 ··· 19 다음
