거누의 개발노트

DP DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 피보나치 수열로 예를 들어 본다면, def fibo(n): if n in [1, 2]: return 1 return fibo(n-1) + fibo(n-2) assert fibo(10) == 55 assert fibo(100) == 354224848179261915075 # 안끝난다. 이런식으로 재귀 함수로 푼다면 100번째 값을 찾을 때는 fibo(1)번째, fibo(2)번째를 찾았던 n번째수를 계속해서 찾아나갈 것이다. 그렇지만 찾아 나간 결과를 저장..

플로이드 워셜(Floyd-Warshall) 알고리즘이란? 모든 최단 경로를 구하는 알고리즘 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다. 파이썬 코드 INF = int(1e9) def floyd_warshall(graph): N = len(graph) dist = [[INF] * (N + 1) for _ in range(N + 1)] for idx in range(1, N + 1): dist[idx][idx] = 0 for..

다익스트라 알고리즘 다익스트라(dijkstra) 알고리즘은 그래프에서 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 예를들어 아래와 같은 경로의 그래프가 있다고 하자. 위 그림은 아래 처럼 표현 할 수 있다. 그래프를 보면서 이해하면 더 쉽다. 6 11

이번주도 마찬가지로 시간이 너무 빠르다. ( 매번 시간이 빨라서 이 말 밖에 안나온다...ㅎ ) 어느정도 적응이 된건지 아니면 쉬운 문제를 푸는건지 몰라도 조금씩 늘어가고 있는건 보인다. ( 그래도 다행이다. 사실 첫주차 불안했다. ) 이번주차부터 TIL을 꼬박꼬박 써서 수월하게 적을 수 있을 것 같다. 1일차 1일차는 트리와 이진트리에 대해서 배웠다. https://geonoo.tistory.com/106 자료구조/알고리즘 - 이진트리(1) 트리란? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 큐(Queue)와 스택(Stack)은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 geonoo.tistory.com 2일차 이진 탐색 트리의 검색,..

이진탐색? 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법 1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다. import math math.log2(100000000) # 26.575424759098897 파이썬 while로 이진탐색 구현 def binary_search(arr, target, start, end): while start target: end = mid-1 else: start = mid+1 print(binary_search([1,2,3,4,5,6,7,8,9],8,0,8)) # 7 파이썬 이진탐색 내장 함수 bisect import bisect arr1 = [i for i in range(1,100,2)] # [1..

Quicksort 분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘입니다. 배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눕니다(Divide). 그리고 그 사이에 기준을 위치시킵니다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있습니다. def quicksort(lst, start, end): def partition(part, ps, pe): pivot = part[pe] i = ps - 1 for j in range(ps, pe): if part[j]

정렬? 엑셀이나 문서작성 프로그램을 사용한 사람이라면 데이터를 오름차순 혹은 내림차순으로 정렬 해본적이 있을 것이다. 정렬이란 데이터의 집합을 어떠한 기준(핵심항목, key)으로 기준의 최소값이면 최대값까지 최대값이면 최소값까지 일정한 순서로 줄지어 세우는 것이다. [4, 6, 2, 9, 1] # 정렬되지 않은 배열 [1, 2, 4, 6, 9] # 오름차순으로 정렬된 배열! [9, 6, 4, 2, 1] # 내림차순으로 정렬된 배열! 버블정렬? 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 소스코드 def bubble(lst): for i in range(l..

이진 탐색 트리란? 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다. 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가진다. 평균적으로 탐색의 시간복잡도는 O(logN), 치우친(skewed) 경우 O(n) 따라서 균형이 중요하다. 아래 그림에서 균형잡힌 경우와 치우친 경우를 확인할 수 있다. 이진 트리의 검색, 삽입, 삭제 검색 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 ..