본문 바로가기

분류 전체보기

 (79)
(재귀)N-Queen 문제 N-Queen 문제는 재귀문제중 매우 대중적인 문제인데 어떤 문제인지 파악부터 해보자. N-Queen 문제는 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 솔류션을 구하는 문제이다. 예를들어 8x8 체스판이 있다면 그림1. 처럼 Queen은 N=8개가 놓일 수 있는데 이게 맘대로 배치하면 안되고 특정 규칙에 따라 배치해야 한다. 특정 규칙이라는것은 그림2처럼 Queen 이 배치 될때 같은 행(row), 열(column)에 다른 Queen이 있으면 안되고 대각선(diagonal) 으로도 있으면 안된다는 것이다. [출처] https://helloacm.com/n-queen-problem-in-back-tracing-bit-logics/ 여기까지 왔으면 문제는 다 파악된것이다. 요..
(재귀)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 마이크로마우스는 빠른시간 안에 미로의 정해진 구역에 도착해야 하는 문제를 풀기위해 길찾기 알고리즘이 성능이 매우 중요한데 미로를 탈출하려다가 막다른 길이 있을..
[JAVA] 함수(Function)란? 함수(function) 란 무엇일까 ? 우선 수학에서 함수는 첫 번째 집합의 임의의 한 원소를 두 번째 집합의 오직 한 원소에 대응시키는 대응 관계라고 얘기하고 있다. 임의의 한 원소는 주어진 입력(input) X 으로 볼 수 있고 대응되는 두 번 째 집합을 출력(ouput) Y로 본다면 대응 관계를 아래 그림 처럼 나타낼 수 있고 수학적 표기는 f : X -> Y 로 한다. f가 정의역 X, 공역 Y를 갖는 함수라는 뜻이고 f : x -> y 는 f(x) = y 처럼 표기할 수도 있다. 프로그래밍에서도 함수는 수학적인 개념과 어찌 보면 비슷하다고 볼수 있다. 프로그래밍에서 함수는 최종적으로 수행해야 할 목표를 위해 다양한 문장(Statement), 수식(expression), 연산자(operator) ..
재귀함수(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개..

티스토리툴바