오뚝이개발자

Greedy algorithm이란? 매 의사결정마다 정해둔 조건에 따라 가장 좋아보이는 답을 선택하는 것 Greedy algorithm(탐욕알고리즘)은 어디에 쓰이나? 주로 특정 제한조건(Constraints)을 만족해야 하는 상황에서의 최적화 문제에 사용 예) machine scheduling, bin packing, minimum spanning tree(MST) MST란? Spanning tree란 그래프의 모든 노드를 포함하는 트리이다. 이 때, MST란 edge의 가중치 합의 최소인 spannig tree이다. Shortest path problem(추후 자세히 포스팅) 다익스트라 알고리즘(Single source all destination) MST(각 방법별로 추후 자세히 포스팅) Krusc..

Divide and conquer(분할정복)이란? 다음의 세 단계를 거치는 알고리즘이다. Divide : large problem을 small subproblem으로 분할 Conquer : recursive하게 각 subproblem을 푼다 Combine : subproblem의 답을 조합해 large problem의 답을 구한다. D&C 사용 예시 [8,2,6,3,9,1,7,5,4,2,8] 리스트 내에서 최솟값, 최댓값을 찾는 문제는 다음과 같이 풀 수 있다. 먼저 large set을 두 그룹으로 나누고, 나누어진 그룹에서 다시 두 그룹으로 나누고....이러한 과정을 풀기에 아주 단순한 small set이 될 때까지 반복한다. 즉, set의 원소 갯수 n이 2개 이하가 될 때까지 하는 것이다.(분할) ..

Sorting Bubble sort Selection sort Insertion sort Shell sort Quick sort Merge sort(분할->병합정렬) Heap sort 각 sorting 알고리즘의 시간복잡도는? Bubble - O(n^2) Selection - O(n^2) Insertion - O(n^2) Shell sort Quick sort worst : O(n^2) best : O(nlogn) avg : O(nlogn) Merge sort Heap sort Searching Linear search는 언제 쓰면 좋은가? item이 sorted 되어있지 않거나 unsortable할 때 Linear search의 단점? 찾는 아이템이 없거나 뒤쪽에 있는 경우 비효율적 Binary sea..

알고리즘의 효율성 측정 방법 basic operation(dominant operation)을 기준으로 하여 input size n에 따른 함수 T(n)으로 실행시간을 나타낸다.(Asymptotic algorithm analysis) Growth rate란? input size가 증가함에 따라 algorithm의 cost가 증가하는 비율 Linear Growth T(n) = n, Quadratic Growth T(n) = n^2 Big-O란? lowest upper bound

요즘 이전에 읽었던 책들이 새로운 의미로 다시 읽혀지는 거에 재미를 붙인 것 같다. 잘 이해되지 않았던 것들이나 공감하지 못했던 것들이 새롭게 읽히는 게 신기하다.(나이를 먹은 걸 수도...) 무튼, 이 책도 그렇게 읽게 되었다. 지난 번 읽었던 마지막 강의도 그렇고. 말하자면, 그냥 한 노인이 먼 바다로 나가 표류하며 자신보다 덩치가 큰 청새치를 잡기 위해 고군분투하는 내용의 연속인 책이다. 중학교 때에 읽었던 것 같은데, 그 땐 그저 단순한 내용의 반복적인 서술이 재미 없다고 느껴졌었나보다. 본래 고전이라 하면 시대에 따라 새롭게 읽히는 작품들이라 하는데 이게 그냥 개인에게도 적용되는 말인 것 같다. 주인공 산티아고를 보면서 "노인이 되어서도 더 이상 꿈이라는게 존재할까?"라는 생각을 했던 나를 반성..

그래프란? finite set of vertex(V)와 edge(E)로 이루어진 것 - graph G : (V,E) Edge(간선)란? 집합 E는 VxV의 subset이다. 일종의 relation이라 볼 수 있다. directed graph(digraph) vs. undirected graph 그래프에서 방향성이 중요한지의 여부에 따라 구분 path란? 그래프에서 node의 sequence다. 단, 각 노드를 연결하는 edge가 있어야 함 Connected graph vs. Disconnected graph connected graph : 모든 노드 사이에 path가 존재(disconnected는 그 반대) disconnected graph는 여러 개의 connected component로 구성 그래프에..

Tree란? Connected, Acyclis, Undirected graph Tree는 Graph에 포함된다. Rooted tree란? 하나의 node가 root로 지정된 tree Tree에서 depth란? root 노드로부터 해당 노드까지의 edge 수 트리의 depth : lowest leaf의 depth(이것을 트리의 height라고도 한다.) Tree에서 level이란? depth와 비슷하지만 기준이 edge가 아닌 node 아래 그림에서 B, D는 각각 레벨이 2, 3인 노드이다. Binary tree란? 모든 node가 최대 2개의 child를 갖는 트리 Binary search tree(BST)란? x라는 key value를 갖는 노드의 left subtree에는 x보다 작은 값이, rig..

Map(Dictinary)이란? value와 unique key가 mapping되는 자료구조 Ordered map vs. Unordered map ordered map : key값이 정렬된 것 - balanced tree로 구현 unordered map : key값이 정렬되지 않은 것 - hash table로 구현 Hashing이란? hash function을 통해 key value(hash key)를 table의 position으로 mapping시키는 것 Hash function을 고를 때 유의사항 계산에 드는 cost가 낮은 것(easy to compute) collision을 최소화하는 것 hash table slot에 데이터를 균등하게 분포시키는 것(evenly distributed) Hash에서..