전체 글
-
트라이(Trie)카테고리 없음 2021. 2. 3. 16:24
위키백과에 트라이는 "검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조" 라고 정의 되어있다. 트라이는 실무에 매우 유용하게 쓰이는 자료구조로서, 특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 트라이는 검색을 뜻하는 'retrieval' 의 중간 음절에서 용어를 따왔다. 트라이는 트리와 유사하지만 지금까지 우리가 주로 살펴본 이진 트리의 모습이 아닌 다진 트리(m-ary Tree)의 형태를 띤다. 트라이는 각각의 문자 단위로 색인을 구축한 것과 유사한데, 예를 들어 다음과 같은 trie에서 단어 apple을 찾는다고 가정해보자. 수백 개의 문자가 있다고 할 때 이 경우 트라이 탐색을 하면 단 다섯번 만에..
-
트리자료구조 2021. 2. 3. 15:49
트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다. 트리는 하나의 뿌리에서 위로 뻗어 나가는 형상처럼 생겨 '트리' 라는 명칭이 붙었는데, 트리 구조를 표현할 때는 나무의 형상과는 반대 방향으로 표현한다. 트리 구조는 ㄴ우리 주변 일상에서 쉽게 볼 수 있는 위아래 개념을 컴퓨터에서 표현한 구조다. 한 가족의 계보를 나타내는 족보나 회사의 조직등을 보면 보통 트리 구조 형태로 되어있다. 좀 더 중요한 트리의 속성중 하나는 재귀로 정의된 자기 참조 자료구조라는 점이다. 쉽게 말하면, 트리는 자식도 트리고 또 그지삭도 트리다. 즉 여거 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 궝된다고 표현하는데, 앞서 트..
-
Variable Scope언어/파이썬 2021. 1. 30. 14:48
파이썬에서 변수의 scope에 대해서 궁금한게 계속 쌓인 상태였다. 이번기회에 확실히 정리 하는게 좋을 것 같다고 생각하여 정리 하고자 한다. 스코핑 룰 변수의 생존범위에 관련도니 규칙이다. 파이썬에서의 함수는 별도의 namespace를 가지며, 이 namespace라는 것은 말 그대로 이름이 모여있는 공간을 의미한다. 예를 들어서 변수를 선언하면 그 변수의 이름이 namespace에 생성된다. 파이썬에서 변수명을 가지고 값을 얻어낼 수 있던 것은 사실 이름공간에 있는 이름을 가지고 특정 객체에 접근하여 얻어오는 것이었다. namespace는 위처럼 총 3가지의 공간으로 나뉜다. 함수 내부의 공간은 지역(local) 영역이라 하고, 함수 외부의 공간은 전역(Global) 영역이라고 하고, 파이썬 자체에서..
-
객체 복사카테고리 없음 2021. 1. 25. 01:40
파이썬의 중요한 특징은 모든 것이 객체라는 점이다. 심지어 숫자, 문자 까지도 모두 객체이다. 숫자, 문자가 리스트. 딕셔너리 같은 객체와의 차이점이라면 불변 객체라는 차이뿐이다. 그러다 보니 별도로 값을 복사하지 않는 한변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조가 된다. 이 말은 참조가 가리키는 원래의 값을 변경하면 모든참조, 즉 모든 변수의 값 또한 함께 변경된다는 말이다. 그렇다면 참조가 되지 않도록 값 자체를 복사 하려면 어떻게 해야할까? 바로 [:]로 처리하는 것이다. [:]로 처리한 변수 c는 다른 ID를 갖는 것을 확인 할 수 있다. 참조로 처리된 변수 b는 a와 동일한 ID를 갖지만 변수 c는 값 자체가 복사되어 새로운 개체가 되었다. 이외에도 좀 더 직관적으로 처리 하는 방법..
-
중첩 함수(Nested Function)언어/파이썬 2021. 1. 24. 23:11
중첩함수란 함수 내에 위치한 또 다른 함수로, 바깥에 위치한 함수들과 달리 부모 함수의 변수를 자유롭게 읽을 수 있다. 실무 보다는 단일 함수로 해결해야하는 경우가 잦은 코테에서 매우 자주 쓰인다. 여기서 outer_function()은 inner_function을 호출했고, 아무런 파라미터도 넘기지 않았지만 부모 함수의 text 변수를 자유롭게 읽어 들여 그 값인 "Hello"를 출력했다. 이처럼 매번 파라미터를 전달하지 않아도 되기 때문에 구현이 깔끔해진다는 장점이 있다. 또한 가변 객체(list, dict, set)인 경우 append(), pop(), 원소 변경(a[i][j] = 1)등 여러가지 연산으로 조작도 가능하다. 그러나 재할당(=)이 일어날 경우 참조 ID가 변경되어 별도의 로컬 변수로 ..
-
서브워드 토크나이저머신러닝 및 딥러닝 2021. 1. 23. 21:55
기계에 아무리 많은 단어들을 학습시킨다고 하여도 신조어와 단어사이즈의 한계등으로 인하여 Out-Of-Vocabularay가 발생한다. 이를 해결하기 위해서 서브워드 분리작업이라는 것이 만들어 졌다. 서브워드 분리 작업은 하나의 단어는 더 작은 단위의 의미있는 여러 서브워드들의 조합으로 구성된 경우가 많기 때문에, 하나의 단어를 여러 서브워드로 분리해서 단어를 인코딩 및 임베딩 하겠다는 의도를 가진 작업이다. 이를 통해 OOV, 희귀 단어, 신조어 문제를 완화 시킬 수 있다. 이런 서브워드 토크나이저에는 대표적으로 Sentencepiece 알고리즘과 BPE를 활용한 WordPiece가 있다. BPE(Byte Pair Encoding) BPE는 1994년에 제안된 데이터 압축 알고리즘으로 연속적으로 가장 많..
-
그래프 순회자료구조 2021. 1. 23. 13:43
그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정을 이야기 한다. 그래프 순회는 크게 깊이 우선 탐색(Depth First Search)와 너비 우선 탐색(Breadth First Search)의 2가지 알고리즘이 있다. DFS - 일반적으로 BFS에 비해 더 널리 쓰인다. - 코테에서도 그래프 탐색은 주로 DFS로 구현하게 된다. - 주로 스택이나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보인다 앞서 말했듯 DFS는 스택으로 구현하며 재귀를 이용 하면 좀 더 간단하게 구현 할 수 있다. 코테에서도 재귀 구현이 더 선호된다. 재귀 구조로 구현 해당 사진은 위키피디아에 제시된 수도코드이다. 이 수도코드에서 정점 v(vertex)의 모든 인접 유향(Directed) 간선들을 반..