전체 글

파이썬으로 구현하는 병합정렬(Merge Sort)

Concept 병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다. 이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다 - 분할(Divide): 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다 - 정복(Conquer): 부분 리스트를 정렬한다 - 결합(Combine): 정렬된 부분 리스트를 하나의 리스트에 통합한다 *이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다 구현 코..

[SWEA] 분할 정복(Divide and Conquer)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 분할 정복 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYFsQq11kDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 분할 정복(Divide and Conquer) 목차 01 분할 정복 기법 02 병합 정렬 03 퀵 정렬 04 이진 검색 05 분할 정복 사례 01 분할 정복 기법 분할 정복(DnQ)이란? 탑다운 접근(Top-down approac)으로, 문제..

[SWEA] 완전 검색(Brute-force search)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYDrI61lYDFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 완전 검색(Brute-force search, 브루트 포스 서치) 목차 01 완전 검색 기법 02 조합적 문제 01 완전 검색 기법 완전 검색(Brute-force search)이란? 문제의 해(Solution)를 얻기 위해 가능한 모든 경..

[LM 평가지표] Perplexity, PPL

유원준님의 딥러닝을 이용한 자연어 처리 입문의 펄플렉서티(Perplexity, PPL) 글을 요약한 게시글입니다 언어모델의 평가 방법(Evaluation metric of Language Model), Perplexity PPL은 문장의 길이로 정규화된 문장 확률의 역수로, 문장 W의 길이가 N이라고 했을 때, PPL은 아래와 같다 $PPL(W)=P(w_1,w_2, \cdots, w_N)^{-\frac{1}{N}} = \sqrt{\frac{1}{P(w_1,w_2, \cdots, w_N)}}^N$ 문장의 확률에 체인룰(chain rule)을 적용하면 아래와 같다 $PPL(W)=\sqrt{\frac{1}{P(w_1,w_2, \cdots, w_N)}}^N=\sqrt{\frac{1}{\Pi_{i=1}^N P(w..

[그래프 이론] 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘이란? 모든 두 노드 u,v 사이에서 가장 최단 거리를 찾는 알고리즘 시간복잡도 $O(n^3)$으로 그래프의 크기가 작을 때만 사용 가능 음의 에지(negative edge)가 있어도 계산이 가능한 알고리즘 단, 음의 사이클(negative cycle)이 있을 경우 불가능 기본 개념: $A^k$[i][j] 노드 i에서 j까지의 최단거리 비용에는 $index

파이썬으로 구현하는 덱(Deque)

덱(Deque)이란? double-ended queue로, 큐의 앞과 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미한다. 덱은 원형 큐(Circular Queue)를 확장하면 손쉽게 구현할 수 있다. 원형 큐 구현에 관해서는 해당 게시글을 참고하시면 좋습니다 https://codingsmu.tistory.com/123 파이썬으로 구현하는 원형 큐(Circular Queue) 원형 큐(Circular Queue)란? 배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 codingsmu.tistory.com 0. 멤버 변수&초기화 먼저 덱 클래스의 멤버 변수(member var..

파이썬으로 구현하는 원형 큐(Circular Queue)

원형 큐(Circular Queue)란? 배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 선형 큐의 단점을 극복한 구조가 원형 큐이다 0. 멤버 변수&초기화 먼저 원형 큐 클래스의 멤버 변수(member variable)화 초기화하는 과정을 살펴보자 class CircleQueue: rear = 0 front = 0 MAX_SIZE = 100 queue = list() def __init__(self): self.rear = 0 self.front = 0 self.queue = [0 for i in range(self.MAXSIZE)] 1. 공백 상태 원형큐가 비워져 있..

[패턴인식] 매칭

Matching 목차 0. PREVIEW 1. 매칭의 기초 2. 기하 정렬과 변환 추정 3. 웹과 모바일 응용 0. PREVIEW 매칭 어떤 대상을 다른 것과 비교하여 같은 것인지 알아내는 과정 여러가지 문제를 해결하는 열쇠(물체인식, 자세 추정, 스테레오, 증강 현실 등) 생각해 볼 점 거짓 긍정(False Positive)을 어떻게 찾아 배제할 것인가? 매칭 속도 두 영상의 특징점 개수가 m,n이고 특징 벡터의 차원이 d라면, 두 영상을 매칭하는데 $\theta(mnd)$시간 소요 실시간 처리가 가능할까? 1. 매칭의 기초 1.1 거리 척도 유클리디안 거리 vs. 마할라노비스 거리 유클리디안 거리(Euclidean Distance) 두 점 사이의 거리를 계산할 때 흔히 쓰는 방법으로, 이 거리에 대응..