전체 글

[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) 두 점 사이의 거리를 계산할 때 흔히 쓰는 방법으로, 이 거리에 대응..

[패턴인식] 특징 기술(2): 특징 기술자, 영역 기술자

Feature Describe 목차 0. PREVIEW 1. 특징 기술자의 조건 2. 관심점을 위한 기술자 3. 영역 기술자 4. 텍스쳐 5. 주성분 분석 6. 얼굴 인식: 고유 얼굴 는 이전 게시글을 참고해주세요 https://codingsmu.tistory.com/120 [패턴인식] 특징 기술(1): 특징 기술자, 영역 기술자 codingsmu.tistory.com 4. 텍스쳐 텍스처(Texture)란? 일정한 패턴의 반복 구조적 방법과 통계적 방법 텍스처(Texture) 특징 활용 위조 얼굴 검출(face anti-spoofing) 분야 4.1 전역 기술자 에지 기반 명암 히스토그램 기반 한계 지역적인 정보는 반영하지 못함 4.2 지역 관계 기술자 원리 화소 사이의 이웃 관계를 규정하고, 그들이 형..