거누의 개발노트

다익스트라 알고리즘 다익스트라(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..

파이만 알고리즘 1. 문제를 적는다. 2. 골똘히 생각한다. 3. 답을 적는다. 이 세상의 어떠한 어려운 문제도 해결할 수 있게 해 주는 우주 최강의 무적 알고리즘이라고 설명하고 있다. 일단 보면 너무 황당하다. 대부분의 사람들이 파인만같은 천재들만 사용할 수 있는 방법이라고 생각한다. 그런데, 사실 이 말은 같은 물리학자인 머리겔만? 이 말한 것으로 알려져있다. 결론부터 말하면 머리겔만이라는 사람이 파인만한태 열등감을 가지고 있어서 비꼬는식의 농담같은 거였다고 한다. 사실 이 이야기를 겔만이 했다는 뒷배경만 제외하고 나면 너무나 당연한 말이다. 모든 문제는 문제로서 인식하고, 깊이 생각하는 과정을 거쳐야 해결할 수 있다는 말이기 때문이다. 본론으로 들어가면 소프트웨어 소프트웨어를 설명할 때는 음식을 만..

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..

힙? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다. 그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가기때문에 최대의 값들을 빠르게 구할 수 있다. 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다! 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이 4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다! 8 Level 0 6..

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