멍멍멍

Union-Find 란? Union-Find 란? Union-Find 의 구현 배열로 표현하기 트리로 표현하기 트리로 표현하기 : 실제 소스코드 최적화 하기 최적화 하기 : 실제 소스코드 Union-Find 정리 끝 Union-Find 란? Union-Find 란 Disjoint Set 을 표현할 때 사용하는 독특한 형태의 자료구조로, 공통 원소가 없는, 즉 "상호 배타적" 인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 입니다. 위의 상황을 표현하기 위해서는 초기화 과정과 다음과 같은 두 가지 연산을 지원해야 하기 때문에, Union-Find 자료구조 라고 부르게 되었다고 합니다. Union-Find 지원 연산 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화 ..

[기하]다각형의 내부 외부 판별 목차 [기하] 다각형의 내부 외부 판별 다각형의 내부 외부 판별이란? 아이디어 다각형의 내부에 위치하는 점의 특징은 뭘까? 구현 어떻게 반 직선과 다각형의 교점 개수를 구하지? 소스 코드 다각형의 내부 외부 판별이란?그림1에는 다각형과 두개의 점(점 A, 점 B)가 있습니다. 이 그림에서 눈으로 딱 보고 점A 는 다각형 외부에 있고 점B는 다각형 내부에 있다는 것을 쉽게 알 수 있습니다.이렇게 다각형에 대해 주어진 점이 다각형 내부에 있는지 외부에 있는지 판별하는 것을 다각형의 내부 외부 판별이라고 합니다. 아이디어 다각형의 내부에 위치하는 점의 특징은 뭘까? 눈으로 보고 직관적으로 점이 다각형 내부에 있는지 판별하는 것은 아주 쉽습니다. 5살 어린이들한테 이 문제를 내도..

[기하]외적을 이용해서 선분과 선분의 교차점 구하기 목차 [기하]외적을 이용해서 선분과 선분의 교차점 구하기 직선과 직선의 교차점 선분과 선분의 교차점 선분과 선분의 교차여부 판별 References 이 글은 포스팅 [기하]외적을 이용한 두 벡터의 상대적인 방향 판별에 설명 되어있는 배경지식을 전제로합니다. 또 이 글은 평면에서의 선분과 선분의 교차점에 대해 설명합니다. 계산 기하 문제에서 선분은 기하를 구성하는 기본 요소이기 때문에 선분의 교차점을 구하는 것은 기하문제를 풀 때 매우 자주 등장합니다.그러나 선분과 선분의 교차점을 구하는 것은 쉽지 않습니다. 교차점을 구하는 것은 고등학교1학년 수학책에 나오는 내용으로 개념 자체는 어렵지 않지만 모든 경우에 대한 일반해를 프로그래밍적으로 구하는 것이 까다..

[기하]외적을 이용한 두 벡터의 상대적인 방향 판별 [기하]외적을 이용한 두 벡터의 상대적인 방향 판별 [기하]외적을 이용한 두 벡터의 상대적인 방향 판별 두 벡터의 방향 판별이란? 벡터의 외적 정의 외적의 성분 표현 이차원에서 벡터의 외적 벡터의 방향성 판단 구현 어디에 활용되나? References 두 벡터의 방향 판별이란? 위 그림의 두 벡터 와 에 대해 는 로 부터 반시계 방향으로 약 90도 방향에 있습니다. 위 그림의 두 벡터 와 에 대해 는 로 부터 시계방향으로으로 약 115도 방향에 있습니다. 이렇게 두 벡터에 대해 한 벡터가 다른 벡터로 부터 시계 방향 또는 반시계 방향으로 몇도에 있는지 파악하는 것을 두 벡터의 방향 판별이라고 합니다. 계산기하 알고리즘에서 이러한 두 벡터 사이의 상대적인..

Bubble Sort : 거품 정렬 Bubble Sort : 거품 정렬 Bubble Sort : 거품 정렬 소개 정렬과정 알고리즘 분석 애니매이션 예시 구현 정리 끝 소개 Bubble Sort는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편이지만, 코드가 단순하기 때문에 자주 사용됩니다. 일반적으로 가장 빠른 정렬 알고리즘은 Quick Sort로 시간 복잡도 입니다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라는 이름을 가지게 되었다고 하네요^^ 아래 버블 소트의 애니매이션 예시에서 정말 거품 같은지 직접 확인해 보시기 바랍니다. 정렬과정 다음과 같이 다섯 개..

Counting Sort Counting Sort Counting Sort 소개 정렬 과정 애니메이션 예시 구현 정리 끝 소개 Counting Sort는 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 반면 일반적 상황에서 가장 빠른 정렬 알고리즘인 Quick Sort의 평균시간복잡도는 입니다 (최악의 경우는 n^2).Counting Sort는 어떻게 이렇게 빠를까요? 그럼 왜 대부분의 정렬이 필요한 상황에서 더 빠른 Counting Sort를 안 쓰고 Quick Sort를 쓸까요?Counting Sort가 어떻게 작동하는지 이해하고 나면 위 의문에 대한 답을 스스로 할 수 있을 겁니다! 정렬 과정 다음과 같은 수열 A를 정렬 해야하는 상황을 생각해봅시다. 위 수열을 정렬하면 아래와 같은 수열 B를 얻습니다..

문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을 때 결과를 캡쳐한 것입니다. 본문에서 89개의 "테이프"를 찾았다고 순식간에 알려주네요. 이렇게 텍스트내(본문)에서 특정 문자열, 패턴("테이프")를 찾는 것을 문자열 검색이라고 부릅니다. 이 문자열 검색은 어떤 방식으로 구현되는걸까요? 가장 단순한 문자열 검색 먼저 가장 단순한 방법의 문자열 검색을 생각해봅시다. 텍스트 "ABCABABCDE"에서 패턴 "ABC"가 어디서 등장하는지 찾아봅시다. 패턴 "ABC"를 한자리씩 옮기면서 같은지 비교합니다. 같아? A B C A B A B C D E A B C ->같아! ..

텍스처 패턴 인식(texture pattern recognition)이 뭐지? 텍스처 패턴을 인식하는 것을 소개해드리려고 합니다. 먼저 제가 소개해드릴 텍스처 패턴 인식(texture pattern recognition)은 다음 과정을 의미합니다. 1. 아래와 4개의 패턴처럼 같은 모양이 주기적으로 반복되는 텍스처 패턴을 미리 정합니다. 2. 컴퓨터가 이 패턴을 학습하도록 합니다. 3. 학습한 패턴의 중 하나가 아래 이미지 처럼 입력으로 주어지면, 학습된 데이터를 바탕으로 중 가장 가까운 패턴을 계산합니다. 4. 입력으로 주어진 패턴과 가장 가까운 패턴을 출력합니다. (앞으로 소개할 과정은 논의를 단순화 하기 위해 흑백 이미지(Grey Scale)에서 진행할 것입니다.) 이 문제가 어려운 이유는 뭘까? ..