본문 바로가기

python13

DP(다이나믹 프로그래밍) Dynamic Programming - 그리디 알고리즘과 같이, 최적화 문제를 해결하는 알고리즘이다. - 문제를 부분 문제로 분할한 후 가장 작은 부분 문제부터 해를 구하여 결과를 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구하는 알고리즘이다. 다음은 피보나치 함수를 DP로 구현한 예시이다. # 기록할 배열의 크기를 먼저 정해놓는 경우 def fibo1(n): arr = [0] * (n+1) arr[1] = 1 # 최초의 부분문제의 해를 배열에 기록 for i in range(2, n+1): arr[i] = arr[i-1] + arr[i-2] # 각 부분문제의 해를 구하여 저장 return arr[n] # 배열의 크기를 미리 정하지 않고 해결하는 경우 def fibo.. 2021. 9. 7.
검색 알고리즘 주어진 자료에서 원하는 값을 찾기 위한 검색 알고리즘을 알아보자. 검색의 종류는 크게 순차 검색, 이진 검색, 해쉬가 있다. 이 번 글에서는 순차 검색과 이진 검색을 알아보자 # 1. 순차검색(sequential search) - 가장 간단하고 직관적인 검색 방법이다. - 배열이나 연결 리스트와 같이 순차 구조로 구현된 자료구조에 적합하다. - 단순하지만, 검색 대상의 수가 많을 경우엔 시간 복잡도가 급격히 증가하여 비효율적이다. - 배열 내 원소가 정렬되어 있지 않은 경우와, 정렬된 경우로 나뉜다. # 정렬되어있지 않은 경우 def search(arr, key): i = 0 n = len(arr) while i < n and arr[i] != key: i += 1 if i < n: return i el.. 2021. 8. 23.
2차원 배열 탐색 목적에 따라 여러가지 방법으로 2차원 배열을 탐색할 수 있다. # 2차원 배열 arrs = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 1. 행 & 열 우선 탐색 # 행우선 for i in range(len(arrs)): for j in range(len(arrs[0])): print(arrs[i][j], end=' ') print() # 열우선 for j in range(len(arrs[0])): for i in range(len(arrs)): print(arrs[i][j], end=' ') print() # 2. 지그재그 순회 # 지그재그 순회 for i in range(len(arrs)): for j in range(len(arrs[0])): print(arrs[i][j + (i.. 2021. 8. 22.
정렬 알고리즘 정렬을 구현하는 알고리즘은 여러가지가 있다. 이번 글에서는 그 중 3가지의 방법을 정리하고자 한다. 다음과 같은 배열이 있다고 가정하자. arr = [4, 2, 9, 3, 10, 5, 2, 7, 8, 6, 10] # 1 - Bubble sort - 리스트 내의 원소들을 하나하나 비교해가며, 큰 값을 오른쪽으로 이동시키는 방식이다. # Bubble sort for i in range(len(arr)-1, 0, -1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] print(arr) # 2 - Counting sort - 리스트의 각 원소들이 몇 번 등장하는지 count하여 정렬을 하는 방식이다. - 시간복잡도가 줄.. 2021. 8. 21.

티스토리툴바