본문 바로가기

전체 글

 (154)
정렬 알고리즘 - 합병 정렬 합병 정렬 (Merge Sort) 분할 정복법- 분할정복법은 본질적으로 순환 함수를 사용하여 문제를 해결하려 한다.- 분할 : 해결하려하는 문제를 작은 크기의 동일한 문제들로 분할한다.- 정복 : 각각의 작은 문제를 순환적(Recursion)으로 해결한다.- 합병 : 작은 문제의 해를 합하여(Merge) 원래 문제애 대한 해를 구한다. 합병 정렬- 데이터가 저장된 배열을 절반 나눈다.- 각각을 순환(Recursion)방식으로 정렬한다.- 정렬된 두 개의 배열을 합쳐 전체를 정렬한다.- 합병 정렬의 진행 과정 - 분리된 두 배열을 병합- 이미 i배열과 j배열은 정렬이 되어있는 상태이고 k배열에 두 배열을 합치기 위해서는 작은 순서대로 넣어주어야 한다.- i와 j배열의 가장 작은 원소들끼리 비교하여 더 작은..
기초 정렬 알고리즘 기본 정렬 알고리즘 종류 예시- Bubble sort ┒- Insertion sort ├ simple, slow- Selection sort ┘- Quick sort ┒- Merge sort ├ fast- Heap sort ┘- Radix sort = O(N) Selection Sort- 각 루프마다1) 최대 원소를 찾는다.2) 최대 원소와 맨 오른쪽 원소를 교환한다.3) 맨 오른쪽 원소를 제외한다.- 하나의 원소만 남을 때까지 위 루프를 반복한다.- 선택 정렬의 진행 과정 - 슈도 코드selectionSort (A[], n) {for last = 1; i--) { save = 0; bw.write(Arrays.toString(array) + "\n"); bw.flush(); for (int j = 0; j
Recursion 응용(4) 멱집합 (powerset) 의미- 어떤 집합의 모든 부분집합들의 집합이다. - data = {a, b, c, d}의 모든 부분집합을 출력한다면(멱집합)∅, a, b, c, d, ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd가 있다.이는 $2^4$개로서 총 16개라 할 수 있다. 멱집합을 구하는 방법- {a, b, c, d, e, f}의 모든 부분집합을 나열하고자 한다.1) a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열한다.2) {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.-이는 곧 a를 포함하지 않은 부분집합의 수인 $2^5$와 포함한 부분집합의 수인 $2^5$가 합해져 총 $2^6$개가 된다. - {b, c..
N Queen Problem Using Recursive Backtracking(스크랩) https://codepumpkin.com/n-queen-problem/
문자와 숫자의 길이 구하기 - length(스크랩) https://huistorage.tistory.com/48
Recursion 응용(3) N Queens Problem 문제- N X N배열의 체스판에 N개의 말을 서로 동일한 행이나 열에 놓이지 않도록 배치하는 문제- 문제를 체계적으로 해결하기 위해서는 back tracking기법을 이용하는 것이 좋다. 상태 공간 트리- 찾는 해를 포함하는 트리이다.- 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당하고, 따라서 이 트리를 체계적으로 탐색한다면 해를 구할 수 있다.- 찾고자 하는 해를 위해 반드시 모든 노드를 탐색해야할 필요는 없다. 이는 가능성이 없는 노드는 생략하고 (non-promising, infeasible)탐색을 진행해 효율성을 높일 수 있다는 것을 의미한다. Back Tracking (되추적 기법)- 자신이 행했던 경로를 다시 되돌아간다는 것으로 가장 최근에 결정..
Recursion 응용(2) Counting cells in a Blob 문제 조건- Binary 이미지- 각 픽셀은 background pixel이거나 image pixel이다.- 서로 연결된 image pixel의 집합을 blob이라 칭한다.- 상하좌우뿐 아리라 대각으로 연결된것도 같은 집합이라 간주한다.- 인접한 8개 픽셀에 대해서 북, 북동, 동,... 순서의 시계방향으로 탐색한다.- 입력N * N크기의 2차원 그리드하나의 좌표 (x, y)- 출력픽셀 (x, y)가 포함된 blob의 크기(x, y)가 어떤 blob에도 속하지 않을 경우에는 0 순환적으로 생각해보기- 현재 픽셀이 속한 blob의 크기를 카운트하려면현재 픽셀이 image color가 아니라면0을 반환한다.현재 픽셀이 image color라면현재 픽셀을 우선 카운..
Recursion 응용(1) 미로찾기 순환적인 방식으로 생각해보기- 현재 위치에서 출구까지 가는 경로가 있기 위해서는 밑의 두 가지 조건 중 하나가 만족해야 한다.1) 현재 위치가 출구여야 한다.2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있어야 한다.- 순환 형식을 이용하여 프로그래밍할 경우에는 무한루프에 빠질 수 있는 경우를 주의해야 한다. - 슈도 코드boolean findPath (x, y)if (x, y) is the exitreturn true;elsefor each neighboring cell (x', y') of (x, y) doif (x', y') is on the pathwayif findPath(x', y')return true;return false;-> 이 경우 무한루프에 빠..

티스토리툴바