본문 바로가기

프로그래밍67

8. 알고리즘 이진탐색(Binary Search)과 순차탐색 1. 이진탐색(Binary Search)란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법 문제 : 1-30번째 병뚜껑에 각각 1~100 사이의 번호가 표시되어 있다. 이중에 70이 있을지 없을지 확인하는 방법은? 조건 1) 가장 적게 병을 따야 한다. 2) 각 병뚜껑에 쓰여진 번호는 낮은 번호 순으로 기입되어 있다. 방법 : 가운데 있는 병뚜껑을 순차적으로 따서 범위를 좁힌다. 이것이 이진탐색방법이다. 순차탐색 : index 0 부터 하나씩 찾기 때문에 훨씬 느리다. 2. 분할정복알고리즘과 이진탐색 분할정복 알고리즘 Divide : 문제를 하나 또는 둘 이상으로 나눈다. Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진.. 2023. 1. 26.
7. 알고리즘 정렬 병합정렬(merge sort) 1. 병합정렬 (merge sort) 분할정복 알고리즘을 사용한다. 재귀용법을 활용한 정렬 알고리즘이다 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 2. 알고리즘 이해 알고리즘 내부에서는 먼저 모두 데이터길이가1일 때 까지 나눈 후, 비교 및 병합을 반복한다. 데이터가 네개일 때 예 : data_list=[1,9,3,2] 먼저 [1,9],[3,2]로 나눈다 다시 앞부분을 [1],[9]로 나눈다 다시 정렬해서 합친다 [1,9] 다음 [3,2]은 [3],[2]로 나눈다 다시 정렬해서 합친다 [2,3] 이제[1,9],[3,2]를 합친다. 12이니[1,2]다 9>3이니[1,2,3.. 2023. 1. 26.
6. 알고리즘 퀵 정렬 (quick sort) 1. 퀵 정렬 (quick sort) 정렬 알고리즘의 꽃 파이썬과 만나면 매력이 넘친다 기준점(pivot이라고 부른다)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다. 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일함수를 호출하여 위 작업을 반복한다. 함수는 왼쪽 + 기준점 + 오른쪽을 return한다 1. 0(pivot)을 기준으로 데이터를 모은다 5 3 2 0(pivot) 1 4 6 32 48 44 56 70 67 87 2. 다시 pivot을 기준으로 왼쪽 오른쪽을 나눈다. (기존pivot 왼쪽) 5 2(pivot) 3 0 32 44 48 56 (기존pivot 오른쪽) 0 4 1(pivot) 6 56 67 70 87 3. 합친다. 5 3 2 0 1 4 6 .. 2023. 1. 25.
5. 알고리즘 동적계획법(dynamic programming)과 분할정복 동적계획법(Dynamic Programming)과 분할정복(Divide and Conquer) 1. 정의 동적계획법(DP라고 많이 부른다.) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결하고, 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다. Memoization 기법을 사용한다 Memoization이란? 프로그램 실행 시 이전에 계산한 값을 저장하며, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술이다 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용 된다 예 : 피보나치 수열 분할정복 문제를 나눌 수 없을 .. 2023. 1. 25.
4. 알고리즘 재귀 용법(재귀 호출) 재귀 용법(recursive call, 재귀 호출) 고급 정렬 알고리즘에서 재귀 용법을 사용한다. 1. 재귀용법 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘 작성시 사용되므로, 익숙해져야 한다 2. 이해 def factorial(n) : if n >1 : return n*factorial(n-1) else : return 1 factorial(5) 스택 처럼 작동 된다 n=1 factorial(1)=1 n=2 2*factorial(1) n=3 3*factorial(2) n=4 4*factorial(3) n=5 5*factorial(4) factorial(1)=1 2*factorial(1)=2*1 = factorial(2) 3*factorial(2)=3*2 = factorial(3) 4*fact.. 2023. 1. 25.
3. 알고리즘 참고 공간복잡도 공간복잡도 알고리즘 계산 복잡도는 다음 두가지 척도로 표현될 수 있다. 시간 복잡도 : 얼마나 빠르게 실행되는지에 대한 척도 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지에 대한 척도 좋은 알고리즘은 실행시간도 짧고, 저장공간도 적게 쓰는 알고리즘이다 통상 둘다 만족시키기는 어렵다 시간과 공간은 반비례적인 경향이 있다. '최근 대용량 시스템이 보편화 되면서, 공간복잡도 보다는 시간 복잡도를 우선적으로 고려한다 그래서, 알고리즘은 시간복잡도가 중심이다 그럼에도 공간 복잡도 대략적인 계산은 필요하다. 이유는 다음과 같다. 기존 알고리즘문제는 예전에 공갑복잡도도 고려되어야할 때 만들어진 경우가 많다. 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간복잡도 제약 사항이 있는 경우가 있다. 또한 기존.. 2023. 1. 25.

티스토리툴바