본문 바로가기

알고리즘(Algorithm)

 (45)
(재귀)Blob(Labeling) 알고리즘 Blob Labeling 알고리즘(Connected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction) )은 영상처리 분야에서 Labeling을 할 때 주로 쓰는 알고리즘인데, N*N 크기의 2차원이미지에서 인접한(상,하,좌,우,대각선모두포함) 화소에 모두 같은 번호(Label)을 붙이고 연결되지 않은 다른 성분(component)에는 다른 번호를 붙이는 알고리즘인데 주로 이미지 안에 연결되어 있는 객체가 몇개 인지 알아낼 때 사용하는 것이다. 문제는 픽셀 (x,y)가 포함된 blob의 크기를 알아내기 위해서 어떻게..
(재귀)미로(MAZE)찾기 미로(MAZE)찾기란 그림 1 처럼 출발지 (A)에서 도착지 (B)까지 가는 경로를 알고리즘적으로 푸는 방법이다. [출처] https://www.researchgate.net/figure/Ariadnes-Thread-Algorithm-The-thread-avoids-walking-in-cycles-The-Algorithm-produces_fig4_221437678 길찾기 알고리즘이 필요한 대표적인 사례는 네이게이션이나 마이크로마우스이다. [출처] https://www.hackster.io/jordanjameswong/micromouse-83dab7 마이크로마우스는 빠른시간 안에 미로의 정해진 구역에 도착해야 하는 문제를 풀기위해 길찾기 알고리즘이 성능이 매우 중요한데 미로를 탈출하려다가 막다른 길이 있을..
재귀함수(Recursive Function)란? 재귀함수에 관련된 글을 읽기전에 함수(function)가 무엇인지 잘 모르면 [JAVA] 함수(Function)란? 을 먼저 읽어보기 바란다. (물론 재귀함수를 읽으려고 들어온사람이 함수(funtion)이 무엇인지 모르는 분은 없을거라 생각한다) 재귀(순환)함수란? 바로 자기 자신을 호출하는 함수를 말한다. 예를들어 recursion() 이란 함수가 있다면 recursion() 함수 안에 또 recursion()을 호출(자기자신 호출)하는 형태를 말한다. 1 2 3 4 5 6 7 void recursion() { .... recursion(); ... } 그런데 만약 재귀함수 안에 자기자신을 호출하게 되면 어떤 일이 벌어질까? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 publ..
기수정렬((Radix Sort) 기수 정렬(radix sort)은 counting sort 처럼 비교연산(comparision operation)을 하지 않고 입력된 원소들간의 순서가 보장되는 stable 한 정렬 알고리즘이다. (comparision, stable 에 대해서는 여기 참고) 기수 정렬은 정렬 방법의 특수성(counting sort를 사용함) 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용(bucket sort가 부동소수점을 정렬할때 유용하다)할 수 없지만 정수와 같은 자료를 정렬할때 선형시간(lienar time)으로 정렬하기 때문에 시간복잡도가 O(dn)로 매우 빠른 정렬알고리즘이다. 그럼 정수 정렬시 counting sort도 선형시간으로 정렬이 가능한 정렬알고리즘이라고 하였고 radix so..
힙정렬(Heap Sort) 힙정렬(Heap Sort)는 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 따라서 힙(Heap) 자료구조를 잘 이해하고 있어야 하기 때문에 반드시 관련 POST를 읽고 이 글을 읽어야 한다. 알고리즘은 힙에 자료를 추가하고 최대값 또는 최소값을 하나씩 삭제하는 것과 동일한데 Note - 힙정렬 알고리즘 1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 2. 최대힙(내림차순정렬이 필요한경우) 인경우 루트노드가 자식노드보다 항상 크도록하고 최소힙(오름차순 정렬이 필요한경우)인경우 로트노드가 자식노드보다 항상 작도..
합병정렬(Merge Sort) 지난 강좌에서는 버블정렬(Bubble Sort), 선택정렬(Selection Sort), 삽입정렬(Insertion Sort)와 같이 비교적 간단하고 이해하기 쉬우나 큰 데이터 셋에는 효율적이라고 할 수 없는 기본적인 정렬 알고리즘에 대해서 알아 봤었다. 이번 시간에는 분할정복 알고리즘을 통해 정렬이 이루어지는 합병정렬(Merge Sort)에 대해서 설명하겠다. 분할정복 알고리즘 개념이 필요하니 분할정복(Divide & Conquer) 알고리즘 을 반드시 읽어 봐야 한다. 합병정렬을 하기위해 예를들어 아래와 같은 데이터가 있다고 하자. 합병정렬은 먼저 데이터 크기가 1개가 될때 까지 반복하여 같은 반으로 나누는 분할 단계를 거친다. 여기서는 8 개 항목의 배열을 크기가 4인 배열로 분할한다. 크기가 4개..
삽입정렬(Insertion Sort) 삽입 정렬( insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘인데 버블정렬(Bubble Sort)와 선택정렬(Selection Sort)와 마찬가지로 단순하고 이해하기 쉽지만 성능상으로는 느린 정렬 알고리즘 중 하나이다. 어떤 식으로 동작하는지 살펴보자. 위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다. 삽입정렬은 처음 2개의 원소들을 비교한다. 14와 33 2개의 원소를 비교하면 이미 오른차순으로 정렬되어 있고 정렬 서브리스트(sorted sub-list) 14를 가지게 된다. 이제 앞으로 이동하여 33과 27을 비교한다. 33..
버블(거품)정렬(Bubble Sort) 버블정렬은 데이터의 모든 원소를 하나씩 무식하게 비교해가면서 정렬하는 기법(부르트포스(Brute Force) 의 한 종류) 으로 정렬시 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블(거품)정렬이라고 부른다. 알고리즘을 살펴보기 전에 VisuAlgo 에서 어떤 방식으로 정렬되는지 시뮬레이션 해보자. 버블정렬은 모든 원소를 하나씩 비교해서 원하는 정렬 규칙에 맞게 두 원소를 서로 swap 하는 과정을 거친다. 쉽게 설명하기위해 정렬되지 않은 배열 numbers 가 아래처럼 있다고 할때 오름차순으로 버블정렬 하때 순서는 아래와 같다. (아래 이미지들의 출처는 튜토리얼 포인트 입니다.) 버블소트는 처음 2개의 원소(numbers[0], numbers[1])를 비교한다. 비교해서 만약 첫..

티스토리툴바