알고리즘의 시간과 공간을 측정할 때는 시간복잡도와 공간 복잡도라는 말을 많이 쓴다. 그런데 시간 복잡도는 무엇이며, 공간 복잡도는 무엇일까? 시간 복잡도는 '어떤 일을 수행할 때, 그 일이 완료되기까지 걸리는 시간이 얼마나 복잡한가' 라고 생각하면 편하다. 공간 복잡도는 '어떤 일을 수행할 때, 그 일이 완료되기까지 필요한 공간(메모리)가 얼마다 되는가' 라고 생각하면 된다. 복잡도의 개념에 대해 알았으면, 이를 표기할 방법이 필요하다. 얼마나 복잡한지를 어떻게 표현할 것인가? (하늘만큼 땅만큼 복잡해요) 이때 Big-O의 개념이 등장한다. 🧐Big-O만 있는게 아니다? 많은 사람들이 시간 복잡도라고 하면 Big-O를 떠올릴 것이다. 하지만 시간복잡도와 공간복잡도를 나타내는 방법에서는 Big-O만 존재하..
📕 정렬 알고리즘 알고리즘 문제를 조금이라도 풀어봤다면, 정렬에 관한 문제가 많이 나오는 것을 알 수 있다. 정확히, 정렬을 활용해서 해결해야 하는 문제가 많이 출제된다.(기본 중의 기본) 데이터를 정렬하는 것은 효율적인 알고리즘에서의 중요한 단계로, 문제 해결을 효율적으로 할 수 있도록 도와준다. 우리는 정렬 알고리즘을 통해서 실수, 문자열, 파일 등을 손쉽게 정렬할 수 있게 된다. 이 문서에서는 정렬의 기본이라고 할 수 있는 선택 정렬과, 삽입 정렬을 다룰 예정이다. 📕 선택 정렬 선택 정렬은 가장 기본적인 알고리즘 중의 하나로, 사람이(보편적으로) 데이터를 보고 정렬하는 과정과 동일하다고 생각하면 편하다. 정렬 순서는 왼쪽에서 오른쪽으로 흘러가며, 최소값을 통해서 데이터의 대소 관계를 비교하고 교체..
📕다익스트라 알고리즘 다익스트라 알고리즘은 가장 빠른 길을 찾을 때 주로 사용하는 알고리즘이다. 빠른 길을 찾을때 사용한다고? 그럼 BFS쓰면 되는거 아닌가? 라고 생각할 수 있다. 맞다 BFS를 사용하면 되지만 BFS를 사용하지 못하는 경우가 존재하는데 바로 비용이 존재할때이다. BFS의 경우 모든 간선의 비용이 동일해야하지만, 다익스트라는 모든 간선의 비용의 동일하지 않아도 사용가능하다. 다익스트라 알고리즘은 min_heap 우선순위큐를 사용하고, 간선을 키값으로 사용한다. 다익스트라 알고리즘에서 핵심은 e = w-> x 이다. 즉,dist[x] 1->2->3이 될 것이다. 하지만 다익스트라 알고리즘은 음수를 처리하지 못하기 때문에 각각의 간선에 음수비용의 양수값인 9를 더해준다. 그렇면 모두 9씩 ..
📕그래프는 뭘까? 알고리즘에서의 그래프는 '간선들로 연결된 정점들의 집합'이라고 얘기할 수 있다. 그럼 정점은 뭐고 간선은 뭐냐? 정점(vertex)은 흔히 노드(node)라고 알려져 있는 점이다. 그리고 이 점과 점을 연결한 선이 바로 간선(edge)이다. 그리고 이 간선은 방향이 있을 수도 있고, 없을 수도 있다. 방향이 있는 그래프를 directed graph(방향 그래프)라고 하고 방향이 없는 그래프를 undirected graph(무방향 그래프)라고 한다. 그래프에는 '사이클'이라는 개념이 있다. 말 그대로 사이클, 즉 자기 자신으로 돌아오는 길이 있는 것을 사이클이라고 한다. 하지만 트리는 이 '사이클'이 존재하지 않는다. 정확히는 사이클이 존재하지 않는 그래프를 트리라고 한다. 📕그래프를 나..
📕기수정렬은 어떤 정렬인가 아마 card-sorting machine에 대해서 아는 사람은 드물 것이다. 오래전 IBM에서 만든 컴퓨터는 펀치 카드를 사용해서 결과값을 출력했는데, 이 카드를 정렬하는 기계가 바로 card-sortin machine이다. 그리고 이 기계에서 Radix sort를 사용했다! 📕LSD radix sort & MSD radix sort LSD radix sort를 알려면, 먼저 LSD가 무엇인지 알아야한다. LSD는 Least Significant Digit의 이니셜로 (환각물질 LSD가 아니다...) LSD radix sort는 가장 아래자리의 문자 혹은 숫자부터 정렬하는 정렬 알고리즘이다. 반대로 앞에서 부터 정렬하는 MSD도 있다. (MSD의 M은 Most) 그렇다면 어떻..
📕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로 표기하겠다) ..
📕그리디 알고리즘이란 ? 그리디 알고리즘은 코딩테스트에 자주 나오는 단골 문제이면서, 알고리즘 문제에 널리 사용되는 알고리즘이다. 그리디 알고리즘은 무엇일까? 그리디 알고리즘의 정의는 다음과 같이 말할 수 있다. "A greedy algorithm always makes the choice that looks best at the moment" 그리디 알고리즘은 '지금 당장 좋은 것을 고르는 방법'이다. 즉, 선택의 순간이 왔을 그때, 가장 좋은 것을 선택하는 것이다. ('Greedy'라는 이름을 보더라도 탐욕적인 것을 알 수 있다.) 📕 Greedy algorithm vs Dynamic programming 그리디 알고리즘과 다이나믹 프로그래밍을 언뜻 보면 비슷하다고 생각할 수 있다. 절차적으로 해결법..
