1. 순차 탐색(Sequential Search) 이란? 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 연습 - 임의 리스트가 다음과 같이 rand_data_list로 있을 때, 원하는 데이터 위치를 리턴하는 순차탐색 알고리즘 작성 def sequential(data, search): for index in range(len(data)): if data[index] == search: return index return -1 from random import * rand_data_list = list() for num in range(10): rand_data_list.append(randint(1, 100)..

1. 이진 탐색(Binary Search)란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 이차 탐색의 이해(순차 탐색과 비교하며 이해하기) 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘(Divide and Conquer) Divide : 문제를 하나 또는 둘 이상으로 나눔 Conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결, 아니면 다시 나눔 이진 탐색 Divide : 리스트를 두 개의 서브 리스트로 나눔 Conquer 검색할 숫자(search) > 중간값이면, 뒷 부분의 서브 리스트에서 검색 검색할 숫자(search) < 중간값이면, 앞 부분의 서브 리스트에서 검색 이진 탐색을 분할 정복 알고리즘을 사용해서 쓴다면 재귀용법을 사용해서 구현 가능 3...

1. 병합 정렬(merge sort) 재귀용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 크게 Split, Merge 두 단계가 있음 2. 알고리즘 이해 데이터가 네 개일 때 ex : data_list = [1, 9, 3, 2] 먼저 [1, 9][3, 2]로 나눔 다시 앞 부분을 [1], [9]로 나누고 다시 [1, 9]로 정렬해서 합침 뒤도 [3], [2]로 나누고 [2, 3]으로 정렬 이제 [1, 9]와 [2, 3]을 합친다 1 3 이므로 [1, 2, 3] 9만 남아서 [1, 2, 3..

1. 퀵 정렬(quick sort) 이란? 정렬 알고리즘의 꽃 기준점(pivot 이라고 부름)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 작성 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업 반복 함수는 왼쪽 + 기준점 + 오른쪽을 합쳐서 리턴함 대표적인 분할 정복 알고리즘 2. 어떻게 코드로 만들까? 연습 - 리스트를 리스트 슬라이싱(예 [:2])를 이용해서 세 개로 짤라 각 리스트 변수에 넣고 출력해보기 1. 피봇 선택 (보통 맨 앞에 있는 데이터 선택) 2. 분류 => 작은 데이터, pivot, 큰 데이터 3. pivot 선택, 분류하기 (데이터 수가 1개가 될 때까지) 4. 합치기 (return ...) def qsort(list):#p..

1. 정의 동적 계획법(DP라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 답을(해를) 활용해 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해 상위 문제를 풀어가는 방식 => 큰 문제를 작은 문제로 나누었을 때 작은 문제를 1번만 풀어서 저장(메모이제이션)해두고 상위 문제에 활용하기 위해 사용(계산 최소화) Memoization 기법을 사용 Memoization(메모이제이션)이란 : 프로그램 실행시 이전 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용 됨. ex) 피보나..

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 검증 (코드로 검증 X, 직접 간단한 경우부터 대입해서 검증) 먼저 2! 부터 함수(2) 이면, 2 > 1이므로 2 X 함수(1) 함수(1) ..

알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있다 시간 복잡도 : 얼마나 빠르게 실행되는가 공간 복잡도 : 얼마나 많은 저장 공간이 필요한가 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 통상 둘 다 만족시키기가 어렵다 시간과 공간은 반비례적 경향이 있음 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 그래서 알고리즘은 시간 복잡도가 중심 공간 복잡도 대략적인 계산은 필요함 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야 할 때 만들어진 경우가 많음 그래서 기존 알고리즘 문제에 시간 복잡도뿐 아니라, 공간 복잡도 제약 사향이 있는 경우가 있음 또한, 기존 알고리즘 문제에 영향을 받아서 면접시에 공간 복잡도를 묻는 경우도 있음 Complexit..

1. 삽입 정렬(insertion sort)란? 삽입 정렬을 두 번째 인덱스부터 시작 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동 2. 삽입정렬 코드 연습 데이터가 두 개일 때 data_list = [9, 4] if data_list[1] < data_list[0]: data_list[0], data_list[1] = data_list[1], data_list[0] 데이터가 세 개 이상일 때 data_list = [7, 9, 8, 3] for index in range(len(data_list)-1): for index2 in r..