본문 바로가기

IT개발41

알고리즘 : 동적계획법(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.
알고리즘 : 삽입 정렬(insertion sort) 삽입 정렬(insertion sort)은? 두 번째 인덱스부터 시작함 해당 인덱스(key값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사함 key 값이 더 큰 데이터를 만날때까지 반복, 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동함 for index in range(10, 1, -1) print(index) """ 출력결과 10 9 8 7 6 5 4 3 2 """ 데이터가 4개 일 때 동작 data_list = [8, 4, 3, 5] 처음 한 번 실행하면, key값은 8, 인덱스(0) -1은 0보다 작음, 끝 : [8, 4, 3, 5] 두 번째 실행하면, key값은 4, 8보다 4가 작음 자리바꿈, 끝 : [4, 8, 3, 5] 세 번째 실행하면, key값.. 2021. 8. 23.

티스토리툴바