본문 바로가기

Data Structure & Algorithm36

[자료구조] Directed Graph References Data Structrue : A Pseudocode Approach with C Contents Graph Directed Graph Graph 그래프는 정점(vertex, vertices)라고 불리는 노드(node)들과 이 정점들을 연결해주는 간선(edge)로 이루어진 자료구조입니다. 아래 그림에서 A, B, ..., E, F에 해당하는 것들을 정점(vertex)라고 부르고, 이 vertex 사이의 선을 간선(edge)라고 합니다. 그리고 그래프는 여러 종류가 있지만, 위 그림처럼 크게 directed graph, 방향을 가지는 그래프와 undirected graph, 방향을 가지지 않는 그래프로 분류할 수 있습니다. 즉, 간선(edge)가 방향을 가지느냐 가지지 않느냐로 나누어 .. 2021. 10. 4.
[암호] 디피-헬먼 키 교환 (모듈러 거듭제곱) References 리얼월드 알고리즘 Contents 디피-헬먼 키 교환 모듈러 거듭제곱 2021.09.23 - [Data Structure & Algorithm/알고리즘] - [암호] AES (Advanced Encryption Standard) - 1 [암호] AES (Advanced Encryption Standard) - 1 References 리얼월드 알고리즘 Contents AES란? AES 암호화/복호화 알고리즘 Key Scheduling C++ 구현 AES (Advanced Encryption Standard) ? 현대 암호 기술은 특정한 수학적 방법을 사용하여 암호문을 생성합니.. junstar92.tistory.com 이전 글에서 암호화 알고리즘인 AES에 대해서 알아봤습니다. AES는.. 2021. 9. 27.
[암호] AES (C++ 구현/private 함수) - 3 2021.09.23 - [Data Structure & Algorithm/알고리즘] - [암호] AES (C++ 구현/멤버 변수, public 함수) - 2 [암호] AES (C++ 구현/멤버 변수, public 함수) - 2 2021.09.23 - [Data Structure & Algorithm/알고리즘] - [암호] AES (Advanced Encryption Standard) - 1 [암호] AES (Advanced Encryption Standard) - 1 References 리얼월드 알고리즘 Contents AES란? AES 암호.. junstar92.tistory.com 이전 글에 이어서 AES Class의 private 멤버 함수들에 대해서 살펴보겠습니다. 내부에서 변환/출력 용으로 사용.. 2021. 9. 25.
[암호] AES (C++ 구현/멤버 변수, public 함수) - 2 2021.09.23 - [Data Structure & Algorithm/알고리즘] - [암호] AES (Advanced Encryption Standard) - 1 [암호] AES (Advanced Encryption Standard) - 1 References 리얼월드 알고리즘 Contents AES란? AES 암호화/복호화 알고리즘 Key Scheduling C++ 구현 AES (Advanced Encryption Standard) ? 현대 암호 기술은 특정한 수학적 방법을 사용하여 암호문을 생성합니.. junstar92.tistory.com 이번 글에서는 이전 글에 이어서 AES를 C++로 구현해보도록 하겠습니다. AES 구현에 대해서 검색해보면 최적화된 코드들이 많지만, 제가 아직 수학적으로 완.. 2021. 9. 23.
[암호] AES (Advanced Encryption Standard) - 1 References 리얼월드 알고리즘 Contents AES란? AES 암호화/복호화 알고리즘 Key Scheduling C++ 구현 AES (Advanced Encryption Standard) ? 현대 암호 기술은 특정한 수학적 방법을 사용하여 암호문을 생성합니다. 이러한 방법에는 상대적으로 짧은 몇백 또는 몇천 비트 길이의 키를 사용하는데, 평문과 이 암호화 키를 함께 취하여 암호화 키가 없다면 역으로 평문을 얻을 수 ㅇ벗는 복잡한 방식으로 암호화합니다. AES 또한 이 방법을 사용하고 있으며, 거의 모든 곳에서 사용되는 방법입니다. AES는 미국 국립표준기술연구소에서 2001년에 채택한 표준으로, 기존 데이터 암호화 표준인 DES를 대체하기 위해 채택되었습니다. 이 프로세스에서 Rijndael(레.. 2021. 9. 23.
LZW 압축 (C++ 구현) References 리얼월드 알고리즘 Contents LZW 인코딩/디코딩 과정 LZW 디코딩에서 코너 케이스 C++ 구현 지난 글에서 다루었던 허프만 코딩은 압축하고자하는 아이템의 빈도에 따라서 인코딩의 길이를 다르게하여 압축하는 방식이었습니다. 2021.08.05 - [Data Structure & Algorithm/알고리즘] - 허프만 코딩 (C++ 구현) 허프만 코딩 (C++ 구현) References 리얼월드 알고리즘 허프만 코딩 허프만 코드는 (최소)우선순위 큐와 이진 트리로 만들 수 있는 유일 접두어 코드를 의미합니다. 1951년 데이비드 허프만(David A. Huffman)이 25살 때 고안한 방 junstar92.tistory.com 즉, 자주 나오는 아이템의 경우에는 짧은 인코딩으로 .. 2021. 8. 29.
허프만 코딩 (C++ 구현) References 리얼월드 알고리즘 허프만 코딩 허프만 코드는 (최소)우선순위 큐와 이진 트리로 만들 수 있는 유일 접두어 코드를 의미합니다. 1951년 데이비드 허프만(David A. Huffman)이 25살 때 고안한 방법으로, 허프만 코딩은 기호들의 빈도를 활용하여 정보를 압축하는 무손실 압축 시스템입니다. 허프만 코딩은 우선순위 큐로 인코딩을 시작하며, 큐의 원소는 이진 트리입니다. 이 이진 트리의 리프노드들은 문자와 텍스트에서 그 문자의 빈도를 가지고 있습니다. 그럼 어떻게 허프만 코드로 변환이 되는지 단어 'effective'를 통해서 살펴보겠습니다. 인코딩 과정 허프만 코딩은 먼저 각 문자의 빈도를 측정하고, 문자와 빈도를 데이터로 갖는 이진 트리를 원소로 갖는 우선순위 큐로 시작합니다. .. 2021. 8. 5.
Rabin-karp(라빈 카프) 알고리즘 두번째로 살펴볼 문자열 탐색 알고리즘은 Rabin-Karp 입니다. 라빈카프 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾아주는 알고리즘입니다. 기본적인 아이디어는 (1)비교할 문자열과 패턴을 Hash function을 통해 해시값으로 변환하고, (2)해시값의 비교를 통해서 문자열이 일치하는지 확인하는데, 일치하지 않으면 다음 문자열로 넘어가고, 일치한다면 해당 문자열과 패턴의 1:1 매칭을 통해서 최종적으로 일치하는지 확인합니다. 즉, 해시값이 일치하면 문자열이 같다라고 판단할 수 있는데, 이는 해시 충돌(hash collison)이 없는 경우에 해당하긴 하지만 대부분 유효하다고 볼 수 있으며, 혹시나 해시값이 같지만 다른 문자열인 경우를 대비해서 해시값이 일치하는 경.. 2020. 12. 17.
KMP 알고리즘 문자열에 조금 약한 편이라서 한동안 문자열과 관련된 알고리즘에 대해서 공부해보려고 합니다. 첫 번째로는 KMP(Knuth-Morris-Pratt) 알고리즘입니다. KMP는 문자열을 탐색하기 위한 것인데, 어떤 문자열 A와 B가 있을때, 문자열 A에서 B를 포함하고 있는지 탐색하는 것입니다. "This is a pen. I have a pen." 이라는 문장에서 have라는 단어를 찾는다고 한다면, 사람이야 그저 눈으로 훑어보고 바로 어디 있는지 찾을 수 있지만, 컴퓨터로 단순하게 찾는다면 이중for문으로 완전탐색을 통해서 찾을 수 있습니다. 완전탐색으로 찾는다면, 시간복잡도는 O(NM)이며, 문자열의 길이가 길어질수록 급격하게 걸리는 시간이 증가해서 시간초과가 발생하기 십상입니다. 그러나, KMP 알고리.. 2020. 11. 25.
투 포인터(Two Pointer), 슬라이딩 윈도우(Sliding Window) 이번 게시글에서 정리할 기법은 투포인터와 슬라이딩 윈도우 입니다. 두 기법은 유사해서 하나로 묶었는데, 우선 투 포인터를 살펴보겠습니다. 투포인터는 1차원 배열에서 배열 원소를 가리키는 두 개의 포인터를 조절해가면서 원하는 답을 찾는 기법입니다. 문제를 보면서 살펴보겠습니다. www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 2003번 문제는 N개의 수로 이루어진 배열이 있을 때, 연속된 부분 수열의 합이 M을 만족하는 경우의 수를 .. 2020. 9. 20.
​

티스토리툴바