본문 바로가기

IT개발/알고리즘, 우리 친해지자!26

알고리즘 : 퀵 정렬(Quick sort) 퀵 정렬(quick sort)은? 정렬 알고리즘 pivot(피봇(기준점))을 정해서 기준점보다 작은 데이터는 left(왼쪽), 기준점보다 큰 데이터는 right(오른쪽)으로 모으는 함수를 작성함 각 left(왼쪽), right(오른쪽)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 작업을 반복함 함수는 left(왼쪽) + pivot(기준점) + right(오른쪽)을 리턴함 알고리즘 구현하기 quicksort 함수 만들기 리스트 갯수가 한 개이면 해당 리스트 리턴, 아니라면 리스트 맨 앞의 데이터를 pivot(기준점)으로 놓기 left, right리스트 변수를 만들고 맨 앞의 데이터를 뺀 나머지 데이터를 pivot과 비교 기준점보다 작으면 left.append(해당 데이터) 기준점보다 크면 right.a.. 2021. 8. 30.
알고리즘 : 동적계획법(Dynamic Programming)과 분할정복(Divide and Conquer) 정의 동적계획법 (DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법, 가장 최하위 해답을 구한 후 저장하고 해당 결과값을 이용해서 상위·문제를 풀어가는 방식 Memoization 기법 사용 (프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술) 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용됨 (피보나치 수열) 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식 (일반적으로 재귀함수).. 2021. 8. 28.
알고리즘 : 재귀 용법(recursive call) 재귀 용법 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘 작성시 사용됨 스택의 전형적인 예(함수는 내부적으로 스택처럼 관리됨) 재귀 용법의 이해 - 팩토리얼을 구하는 알고리즘을 Recursive Call을 활용해서 작성해보자 - 생각해보기 2! = 1 X 2 3! = 1 X 2 X 3 4! = 1 X 2 X 3 X 4 =>규칙 : n! = n X (n-1)! 1. 함수 만들기 2. 함수(n)은 n > 1 이면 return n X 함수(n - 1) 3. 함수(n)은 n = 1이면 return n =>검증(코드로 구현전에 간단한 경우부터 먼저 검증한다) 1. 2! 경우 함수(2)이면, 2 > 1 성립함으로 2 X 함수(1) 함수(1)은 1 이므로 return 2 X 1 = 2 맞음 2. 3! 경우 .. 2021. 8. 26.
알고리즘 : 선택정렬(selection sort) 선택 정렬(selection sort)은? 1. 주어진 데이터 중, 최소값을 찾음 2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 코드로 만들려면? 1. 데이터 두 개의 경우 data_list = [8, 2] data_list[0] > data_list[1] 이므로 data_list[0]값과 data_list[1] 값을 교환 2. 데이터 세 개의 경우 data_list = [8, 2, 6] 처음 한 번 실행하면 2, 8, 6이 됨 두 번째 실행하면 2, 6, 8이 됨 3. 데이터 네 개의 경우 data_list = [8, 4, 3, 2] 처음 한 번 실행하면 2, 4, 3, 8이 됨 두 번째 실행하면 2, 3, 4, 8 됨 세 번째 .. 2021. 8. 24.

티스토리툴바