코딩가딩가

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 탑다운(Top-Down) 방식 : 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법, 큰 문제를 해결하기 위해 작은 문제를 호출 메모이제이션(Memoization) : 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모리 결과를 그대로 가져오는 기법 보텀업(Bottom-Up) 방식 : 반복문을 이용하여 소스코드를 작성하는 방법, 작은 문제부터 차근차근 답을 도출 (탑다운 방식보다 보텀업 방식이 권장됨) ## 예시 (피보나치 수열 소스코드(재귀적)) -..

- 순차 탐색 (O(N)) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 #순차 탐색 소스코드 구현 def sequential_search(n, target, array): #각 원소를 하나씩 확인하며 for i in range(n): #현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i+1 #현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기) print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(input_data[0]) #원소의 개수 target = input_data[1] #찾고자 하는 문자열 p..

선택 정렬(Selection Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] #스와프 print(array) 삽입 정렬(Insertion Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(array)): for j in range(i, 0, -1): #인덱스 i부터 1까지 감소하며 반복하는 문..