📕그래프는 뭘까? 알고리즘에서의 그래프는 '간선들로 연결된 정점들의 집합'이라고 얘기할 수 있다. 그럼 정점은 뭐고 간선은 뭐냐? 정점(vertex)은 흔히 노드(node)라고 알려져 있는 점이다. 그리고 이 점과 점을 연결한 선이 바로 간선(edge)이다. 그리고 이 간선은 방향이 있을 수도 있고, 없을 수도 있다. 방향이 있는 그래프를 directed graph(방향 그래프)라고 하고 방향이 없는 그래프를 undirected graph(무방향 그래프)라고 한다. 그래프에는 '사이클'이라는 개념이 있다. 말 그대로 사이클, 즉 자기 자신으로 돌아오는 길이 있는 것을 사이클이라고 한다. 하지만 트리는 이 '사이클'이 존재하지 않는다. 정확히는 사이클이 존재하지 않는 그래프를 트리라고 한다. 📕그래프를 나..

📕Facts(한 것) 알고리즘 복습 및 포스팅 학교 시험(알고리즘) 📕Findings(배운 것) 오늘 하루 학교 알고리즘 시험에 모든 걸 쏟아부었다. 다행히도 시험은 그럭저럭 잘 본 것 같다. 마지막 문제가 DP문제가 나왔는데, 텍스트 에디터 밖에 사용하지 못하고, 문제가 코드를 짜는 것이 아니라, 설명을 하는 것이었기 때문에 그럭저럭 잘 푼것 같다. 📕Feeling(느낀 점) 알고리즘 시험 공부에 시간을 제일 많이 들여서 그런지 이제 시험 한개쳤는데, 벌써 시험 다 친 기분이다. 📕Affirmation(자기 선언) 日日新又日新 순간에 최선을 📕여담

📕기수정렬은 어떤 정렬인가아마 card-sorting machine에 대해서 아는 사람은 드물 것이다. 오래전 IBM에서 만든 컴퓨터는 펀치 카드를 사용해서 결과값을 출력했는데,이 카드를 정렬하는 기계가 바로 card-sortin machine이다. 그리고 이 기계에서 Radix sort를 사용했다! 📕LSD radix sort & MSD radix sortLSD radix sort를 알려면, 먼저 LSD가 무엇인지 알아야한다. LSD는 Least Significant Digit의 이니셜이다.LSD radix sort는 가장 아래자리의 문자 혹은 숫자부터 정렬하는 정렬 알고리즘이다.반대로 앞에서 부터 정렬하는 MSD도 있다. (MSD의 M은 Most) 그렇다면 어떻게 정렬할까? 혹시 기수정렬의 다..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 자료구조, 알고리즘 포스팅(DP, radixsort, graph, MST) 📕Findings(배운 것) 기수정렬에서 LSD 정렬의 시간복잡도는 O(dN)이고 MSD 정렬의 경우 최선은 O(2N), 최악은 O(2dN)이다. 다익스트라는 그리디 알고리즘의 일종이지만 bellman-ford는 모든 경로를 탐색하는 알고리즘이다. 당연히 bellman-ford 알고리즘이 시간이 평균적으로 더 소요되고, 다익스트라의 시간복잡도는 이진 힙 구조로 구현하는 경우O(E * logV), 배열로 구현하는 경우 V^2이며 bellman-ford의 경우 시간복잡도는 O(E*V)이다. 크루스칼 알고리즘의 시간복잡도는 O(E logE)이고 프림 알고리즘의 시간복잡..

📕Backtracking이란? 영어 사전에서 backtrack이란 단어를 검색하면 나오는 결과이다. '(방금 왔던 길을) 되짚어 가다' 미로찾기를 한다고 생각해보자, 두갈래 갈림길이 나왔을때 왼쪽으로 가다가 막히면 어떻게 하는가? 다시 갈림길이 있는 곳으로 돌아와서 오른쪽으로 가지 않겠는가? 이것이 바로 백트래킹의 핵심이다. 길이 막혔을 경우 다시 돌아가는 것을 원하는 결과가 나올때까지 반복하는 것이 바로 백트래킹이다. 간간단한 예제를 살펴보자. S = {W1 = 5, W2 = 6, W3 = 10, W4 = 11, W5 = 16} and W = 21 S에 있는 수를 뽑아 W를 만드려고 한다. 이때 생기는 조합은 여러가지가 있다. {W1, W2, W3} , {W1, W5}, {W3, W4} = 21 이러한..

📕Huffman code 란?압축은 자료의 크기를 줄이기 위해서 사용된다. 그리고 이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데, 그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 알고리즘이다. Huffman code도 그리디 알고리즘의 일종이다. 허프만코드는 데이터를 매우 효율적으로 압축하는데, 20~90%의 용량을 아낄 수 있다. 허프만 코드는 prefix-free* codes로 표현된다. prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장한다. (*prefix codes가 표준 표기이긴 하지만, prefix-free codes가 좀 더 맞는 이름이기 때문에 여기에서는 prefix-free codes로 표기하겠다) ..