CS/Alogrithm
-
11. HashCS/Alogrithm 2021. 12. 16. 14:06
해시 함수(hash function) 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 해시는 매핑을 통해 원하는 데이터를 더욱 빠르게 접근해 사용할 수 있도록 돕습니다. 또한, 해시는 복호화가 어렵다는 특징을 가지기 때문에 암호학 및 블록 체인 구현에 있어 중요한 요소입니다. 대표적인 알고리즘으로 MD5, SHA 등이 있습니다. 입력한 데이터와 출력된 데이터 'input - key / output - value' 이렇게 표현합니다. 크기는 동적으로 변화하며, 해시 값 자체를 index로 사용하기 때문에 탐색 시간 복잡도는 O(1)입니다. 충돌과 관련된 방법을 익히고 계셔야 O(1)라고 말할 수 있는 근거가 있다고 생각합니다. 각 방식을 단순 외우기보단 꼭 이해해 보시기 바랍니다. 아래와 같이..
-
10. Prefix SumCS/Alogrithm 2021. 1. 28. 16:55
Prefix Sum, 유명하고 상당히 쉬운 측에 속하는 알고리즘입니다. 물론.. 알고리즘이라 부르기도 조금 민망할 정도로 간단한데.. 활용하기 좋은 방법이라 소개드립니다. Prefix Sum 누적합, 구간합이라 불리며 누적합 또는 구간합을 빠르게 구하는 알고리즘입니다. Prefix라는 단어를 사전에서 찾아보면 '접두사'라는 뜻을 갖습니다. 접두사라는 용어보다는 단어를 분해해 이해하는 것이 좀 더 와 닿습니다. pre- ~ 이전의, 미리 fix 고정시키다. 정하다. 즉, 미리 어떤 것을 고정시킨다. Sum, 합을 미리 고정시킨다로 받아들이시면 이해가 더 빠를 수도 있겠습니다. 어떻게 고정시키고 어떻게 활용할 것인지 알아봅시다. 우선, 어떤 수들의 합을 구하는 문제를 해결해 보겠습니다. arr = {0, 8..
-
9. Dijkstra (최단 경로 알고리즘)CS/Alogrithm 2021. 1. 26. 16:05
최단 경로 알고리즘 중 가장 많이, 자주 접할 수 있는 다익스트라 알고리즘에 대해 설명합니다. Dijkstra Alogrithm 그래프 내에서 꼭짓점간 최단 경로를 찾는 알고리즘이다. 알고리즘을 고안한 에츠허르 다익스트라의 이름을 따 다익스트라 알고리즘이라 불립니다. 일반적으론 하나의 노드에서 다른 하나의 노드까지의 최단 경로를 구하는 알고리즘입니다. 파생된 방식으로 1:1 탐색이 아닌, 1:N, N:1, N:M 탐색 방식이 있습니다. 기초는 1:1 방식이나, 하나의 노드에서 다른 모든 노드로 향하는 최단 경로를 찾아 트리를 구성하는 방식 또한 주로 쓰입니다. 사실 1:N 방법이 더 많이 쓰이긴 합니다. 우선 자주 쓰일 용어에 대해 살짝 짚고 넘어가겠습니다. V: Vertex를 의미합니다. Node, 꼭..
-
8. Huffman's Code (허프만 부호화)CS/Alogrithm 2020. 11. 18. 19:28
막상 찾아보니 알아두면 좋을 것 같아서 후다닥 정리하고 써봅니다. 우선 위키의 정의를 살펴보겠습니다. Huffman's Code 전산학과 정보 이론에서 허프먼 부호화(Huffman coding)는 무손실 압축에 쓰이는 엔트로피 부호화의 일종으로, 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘이다. 1952년 당시 박사과정 학생이던 데이비드 허프먼이 《A Method for the Construction of Minimum-Redundancy Codes》란 제목의 논문으로 처음 발표했다. (출처 wiki) 박사 과정은 역시 넘4.. 생소한 단어가 좀 있는데, 알고 보면 간단한 개념입니다. 우선 엔트로피 부호화는 '심볼이 나올 확률에 따라 심볼을 나타내는 코드의 길이를 달리하는 부호..
-
7. Greedy (그리디 알고리즘, 탐욕법)CS/Alogrithm 2020. 11. 17. 18:06
제가 원래 수학 관련 문제를 좀 좋아합니다. 특히 고등학교 때부터 공간도형 문제를 좋아하고 잘 풀기도 했는데요. Greedy, DP 이런류의 알고리즘도 수학적 지식이 기반되는 데 반해 항상 감으로만 풀게 되더라구요. 따라서, 잘 푸는 문제는 잘 푸는데 못 푸는 문제는 거의 손도 못 대는 경우가 많습니다. 어떤 분류에서 문제 해결에 기복이 있다면, 저는 항상 개념부터 다시 공부하곤 했습니다. 정확한 개념이 잡혀 있어야, 어떤 어려운 응용문제도 하나씩 해결해나갈 수 있으니까요. 같은 어려움을 겪는 분들에게 조금이나마 도움이 될 수 있으면 좋겠네요. 물론 공부하고 학습하기 위한 글로 개념이나 증명적인 부족함이 많을 수 있습니다. 다른 자료들도 많이 참고해보시는 게 좋을 듯합니다. Greedy '탐욕스러운, 욕..
-
6. KMP, Knuth-Morris-PrattCS/Alogrithm 2020. 6. 19. 18:30
대표적인 문자열 처리 알고리즘 중 하나인 KMP를 소개해보려 합니다. 알고리즘 이름은 해당 알고리즘을 고안한 분들의 이름을 따서 만들어졌습니다. 문자열 관련 알고리즘 또한 다양한데요. 해당 알고리즘은 문자열 A를 기준으로 문자열 B에 포함된 개수를 찾는 것이 핵심입니다. 해당 알고리즘의 대표 문제인 찾기(백준 1786번)에도 관련 내용에 대한 설명이 나와 있습니다. 알고리즘을 이해한 후에 해당 문제도 한번 풀어보시면 좋을 것 같습니다. 간단한 예시를 들면 아래와 같은 문자열에서 문자열 A가 총 몇 개 포함되어 있는지 찾는 문제입니다. 문자열 B: Apple is not green Apple but, red one. 문자열 A: Apple 역시나 눈으로 찾긴 쉽습니다. 간단하게 2개가 바로 보이네요. 컴퓨..
-
5. LCA, Lowest Common Ancestor (최소 공통 조상)CS/Alogrithm 2020. 3. 5. 17:28
몇 달간 많은 일이 있었습니다. 수료도 했고, 해외 연수와 CES 참관... 스프링 인강, 알고리즘 스터디 등등.. 그중에 소마 친구들과 같이 알고리즘 스터디를 하다가 공부하게 된 LCA라는 알고리즘을 소개해볼까 합니다. LCA는 기본적으로 트리에서 사용되는 알고리즘입니다. 간략하게, 트리에 대한 내용은 트리와 그래프 포스팅을 참고해 주세요. exponential-e.tistory.com/33 트리와 그래프 컴퓨터공학 전공 중이시라면 당연히 두 자료구조의 이름은 들어보셨을 겁니다. 하지만 뭐.. 저는 학교 다니면서 그 차이점에 대해 전혀 알지 못했었는데요. 그렇게 여러 문제를 접하며 박살 exponential-e.tistory.com 일상생활에서 트리구조는 족보 또는 가계도를 예로 들을 수 있습니다. 이..
-
4. Disjoint-set, Union-find (서로소 집합)CS/Alogrithm 2019. 5. 22. 22:05
SW 마에스트로 합격 이후로 정신없이 지내서.. 이제야 글 하나를 씁니다. 올해는 이 글이 마지막 글이 될 것 같아요... (그래도 가능하면 관련 문제에 대한 글 한두 개 정돈 쓰도록 하겠습니다.) 오늘 설명드릴 알고리즘은 서로소 집합입니다. Union-find, Disjoint-set 모두 서로소 집합을 의미하는 용어인데요. 후자가 좀 더 의미에 와 닿는 것 같아요. 사실 이 알고리즘에 대한 설명을 쓸지 말지 고민을 많이 했습니다. 제가 가장 좋아하는 알고리즘(이를 응용한 MST 포함해서요) 중 하나인데요. '이렇게 글을 쓸 정도로 잘 알고 있나?' 라고 생각을 해보면 그건 아닌 것 같아서요. 최대한 자세하게 적도록 해볼게요. DisJoint-Set, Union-find 말 그대로 서로소 집합입니다. ..