전공/C++ 검색 결과

13 개의 검색 결과가 있습니다.

전공/C++

알고리즘 : 완전 탐색 #2 (BFS, DFS)

그래프 탐색 마지막으로 그래프 탐색(Graph Traversal)이 있습니다. 그래프란, 어떠한 현상이나 사물을 아래 그림처럼 정점(vertex)과 간선(edge)로 표현한 것으로, 두 정점이 간선으로 연결되어 있으면 인접하다고 합니다. 그래프 또는 트리를 탐색하기 위해 BFS와 DFS라는 기법이 쓰이게 되는데, BFS(Breadth-First Search, 너비 우선 탐색)란 방문한 정점에 인접한 정점들을 우선 방문하는 방식이고, DFS(Depth-First Search, 깊이 우선 탐색)란 인접한 정점 중 하나를 방문하되 그 정점에 인접한 정점을 계속 방문하여, 더 이상 방문할 정점이 없을 때 다시 처음 방문했던 정점에 인접한 또 다른 정점을 방문하게 됩니다. 그림으로 나타내면 다음과 같습니다. 둘 ..

2023. 6. 29. 18:54

전공/C++

알고리즘 : 완전 탐색 #1 (Brute-Force, 순열, 재귀)

완전탐색(Exhaustive search)이란, 어떤 문제를 해결하기 위해 모든 경우의 수를 시도하며 정답을 찾아가는 방법입니다. 완전탐색은 일반적으로 모든 문제를 해결할 수 있지만, 아무리 컴퓨터의 성능이 뒷받침 한다 하여도 그 시간이 천문학적으로 걸릴 수 있습니다. 완전탐색 알고리즘으로는 다음의 다섯 가지가 쓰입니다. 1. Brute-Force : 노가다 2. 순열(Permutation) 3. 재귀(Recursive) 4. 비트마스크(Bitmask) 5. 그래프 탐색(Graph Traversal) : BFS, DFS Brute-Force Brute-Force 기법은 for, while, if ... 등의 반복문, 조건문을 활용하여, 가능한 모든 방법을 단순히 찾는 기법입니다. 예를 들어 숫자로만 이루..

2023. 6. 29. 12:20

전공/C++

알고리즘 : 허프만 인코딩

텍스트 혹은 여러가지 파일에는 중복된 데이터가 있기 마련입니다. 이러한 중복된 데이터를 압축하여 공간을 절약하는 것이 화일 압축 알고리즘이라고 하는데, 여러분이 자주 사용하시는 알집 혹은 반디집과 같은 압축 프로그램에 쓰이는 알고리즘입니다. 이번 시간에는 이런 화일 압축 알고리즘에 쓰이는 허프만 인코딩에 대해 소개하려 합니다. 트라이(trie) "AAAAABBCDE" 다음과 같이 다섯개의 문자가 등장하는 텍스트 파일이 있습니다. A를 0, B를 1, C를 10, D를 11, E를 101로 변환하고 표로 나타내면 아래와 같습니다. 변환된 코드로 텍스트 파일을 변경(디코드, decode)하면 다음과 같죠. "00000111011101" 이렇게 빈도수에 따라 적고 많은 비트를 사용하여 인코딩하는 기법을 가변 ..

2022. 6. 7. 21:58

전공/C++

알고리즘 : 패턴 매칭 알고리즘

패턴 매칭 알고리즘이란, 텍스트에서 원하는 문자 패턴을 찾아 내는 것입니다. 들어가기 전에, 정규식에 대해 간단히 소개하겠습니다. 정규식 (regex) 정규식이란, 세 가지 기본 연산들로 이루어진 심볼들의 스트링입니다. 여기서 심볼이란, 아래의 세 가지를 들 수 있습니다. * : 앞의 문자 혹은 괄호 안의 문자들이 0번 이상 반복됨. ? : 어떤 문자와도 매칭됨. 조커. + : OR 그렇다면 이 심볼들이 어디에 사용되는지 정규식의 예를 살펴보겠습니다. ?*(ie+ei)?* : ie 또는 ei를 가지고 있는 모든 단어. - ???ie??? : billie eilish, kittie, ... - ???ei??? : keith ape, weight, ... (1+01)*(0+1) : 연속적으로 두개의 0이 나..

2022. 6. 7. 19:29

전공/C++

알고리즘 : 스트링 탐색 #2 (KMP 알고리즘)

지난 시간에는 한 글자씩 대조하여 스트링을 탐색하는 직선적 알고리즘을 알아보았습니다. 이번에 소개할 KMP 알고리즘은 이와 달리 패턴에서 얻은 어떠한 정보를 바탕으로 텍스트를 껑충껑충 넘어가며 패턴과 비교를 진행하는데, 어떻게 진행되는 지 알아보도록 하겠습니다. 위의 그림과 같이 "ABCDABCDABEF" 에서 "ABCDABE" 를 찾으려 합니다. 지난 시간에 알아본 직선적 알고리즘으로 탐색하다 보면 마지막 C, E에서 불일치가 일어나죠. 그렇다면 아래와 같이 딱 한 칸만 이동하여 또 비교를 진행합니다. 이렇게 진행하면 시간낭비가 된다는 걸 그냥 봐도 알 수 있습니다. 이런 시간낭비를 개발자 형님들은 그냥 두고 볼 수가 없었죠. 결국 더 간결하고 시간이 훨씬 적게 드는 탐색 알고리즘을 발견했으며, 발견자..

2022. 6. 4. 02:49

전공/C++

알고리즘 : 스트링 탐색 #1 (Naive, 직선적 알고리즘)

이 페이지에서 "KMP" 라는 글자를 찾고 싶다면 어떻게 해야할까요? Ctrl + F 를 눌러서 "KMP"를 검색하면 됩니다. 이렇게 글에서 특정 단어를 탐색하는 과정을 지금부터 소개할 텐데요, 바로 스트링 탐색 알고리즘입니다. 직선적 알고리즘 "Choi Yena is cute." 라는 문장에서 cute를 찾으려고 할 때, 어떻게 해야 할까요? 우선 여기서 "Choi Yena is cute."는 Text, "cute"는 Pattern이 라고 부릅니다. 각 스트링의 글자 갯수를 N, M이라 할 때, t[N] 배열과 p[M] 배열을 대조하면서 텍스트 내의 패턴을 찾는 것이 스트링 탐색 알고리즘이죠. 여기에는 대표적으로 네 가지 알고리즘이 있습니다. 1. 직선적 알고리즘 (Naive Search) 2. KMP..

2022. 5. 17. 02:41