개발자의 기록습관

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-2. 합병정렬(Merge sort)simple, slowBubble sortInsertion sortSelection sortfastQuick sortMerge sortHeap sortO(n)Radix sort 분할 정복법 "Divide and Conquer"merge sort와 quick sort는 분할 정복 알고리즘을 사용한다.기본적으로 resursion을 사용하여 문제를 해결하는 기법이다.아래의 세가지 단계를 거쳐서 문제를 해결한다.분할해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할크기는 작은 사이즈의 문제이지만, 문제..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-1. 정렬simple, slowBubble sortInsertion sortSelection sortfastQuick sortMerge sortHeap sortO(n)Radix sort기본적인 정렬 알고리즘Selection Sort각 루프마다최대 원소를 찾는다최대 원소와 맨 오른쪽 원소를 교환한다.맨 오른쪽 원소를 제외한다.하나의 원소만 남을 때까지 위의 루프를 반복한다.pseudocodeselectionSort(A[], n) { for last

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크2-7. Recursion의 응용 4 - 멱집합멱집합 - Powerset어떤 집합의 모든 부분집합을 멱집합이라고 부른다.임의의 집합 data = {a, b, c, d}의 모든 부분집합은2ⁿ = 16개 이다. Recursion을 이용하여 모든 부분집합을 나열{a, b, c, d, e, f}의 모든 부분집합을 나열하려면먼저 a를 포함하지 않는 부분집합과a를 포함하는 부분집합으로 나눌 수 있다.따라서, 아래와 같이 표현할 수 있다.a를 포함하지 않는 부분집합a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열하고a를 포함하는 부분..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크2-6. Recursion의 응용 3 - n queens problemN-Queens problem(n=8)아래의 예(n=8)에서는 8 x 8 체스보드에 8개의 말을 놓는데,그중에 어떤 말들도 동일한 행, 동일한 열, 동일한 대각선 상에 오지 않도록n개의 말을 놓을 수 있는가에 대한 문제이다.위의 방법대로 n개의 말을 놓으려면, 결국 조건을 만족하면서 하나의 행에 하나의 말이 와야한다.Backtracking내가 지나온 길을 다시 되돌아 가면서 문제를 해결한다.어떠한 결정들을 내려가다가, 결정이 막다른 길이다. 즉, 그 결정을 내려서는 안..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크2-5. Recursion의 응용 2 - Counting Cells in a BlobCounting cells in a Blob입력으로 Binary 이미지가 주어진다.각 픽셀은 background pixel(흰색)이거나 혹은 imagepixel(파란색)이다.서로 연결된 image pixel들의 집합을 Blob이라고 부른다.상하좌우 및 대각방향으로도 연결된 것을 Blob으로 간주한다. 따라서 위의 그림에서는 아래와 같은 Blob 집합이 존재한다.총 4개의 Blob 존재특정 좌표가 속한 Blob의 크기 count입력N * N 크기의 2차원 ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크2-4. Recursion의 응용 1 - 미로찾기Maze - 미로찾기(n-1, n-1)의 좌표를 출구로 가정흰색이 지날 수 있는 길, 파란색이 벽입구에서 출구까지의 경로를 찾는 문제Recursive Thinking현재 위치에서 출구까지 가는 경로가 있으려면현재 위치가 출구이거나(이미 내가 출구에 와 있거나). 혹은,이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나.위의 경우를 Recursive하게 생각한다. 전체 문제를 해결하려고 하면 부분 문제의 해결이 이루어 지면서 전체 문제가 해결된다.위의 둘중에 하나가..