개발 이야기

정렬 알고리즘은 다양하게 존재합니다. 대표적은 정렬 알고리즘인 합병정렬은 분할정복법를 사용하는 Sort 알고리즘입니다. 분할정복법은 분할, 정복, 합병으로 나눠 작업 합니다. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제를 순환적으로 해결 합병 : 작은 문제의 해를 합하여(merge) 원래 문제를 대한 해를 구함 Merge sort는 두 배열을 합병정렬하는 방법입니다. 그림을 참고하시면 좀 더 이해하기 편하실 것입니다. 수도코드 mergeSort(A[], p, r) //A[p ... r] 을 정렬한다 { if (p < r) then { q

정렬 알고리즘 중 Bubble, Insertion, Selection Sort 의 개념 및 코드로 어떻게 표현하는지 공유드립니다. Bubble sort Bubble Sort은 두 인접한 원소를 검사하여 정렬하는 방법입니다. 냇가에서 물고기 잡을 때 물고기 몰이 하는 것처럼 앞에서부터 마지막 항목까지 인접한 두 항목을 비교해서 정렬하는 방법입니다. 수도코드 bubbleSort(A[], n) 배열 A[1..n] 을 정렬한다. { for last

Recursion으로 먹집합을 구성해보겠습니다.멱집합이란? 모든 부분 집합을 모은 집합을 의미합니다. 멱집합 A가 존재한다고 할 때 A을 나타내는 기호는 P(A) 나 이다. 예를 들어, { A={1,2}} A = {1, 2} 의 멱집합은 P(A) = {공집합, {1}, {2}, {1,2}} 이다. 멱집합의 특징을 고려해서 다음과 같이 규칙을 만들 수 있습니다. 규칙 1. 부분집함을 구성 시 부분집합의 각 요소는 포함 하는 경우와 포함하지 않는 경우로 나눈다. 규칙 2. 공집합도 집합으로 구분되며, P(A)는 2^A이다. 규칙 1을 그래프로 표시하면 다음과 같이 표시할 수 있습니다. 가장 상단부터 해서 왼쪽은 포함되지 않는 것, 오른쪽은 포함된 것으로나눠서 표시한 그래프입니다. 각 원소의 포함 여부를 저장..

미로찾기(Decision Problem)Decision Problem 답이 yes or no 인 문제 미로 찾기에 대해서 알아보겠습니다. 현재 위치에서 출구까지 가는 경우는 2가지로 나눠집니다. 1) 현재 위치가 출구 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 경로이것을 수도 코드로 표현하면 다음과 같습니다. 수도코드boolean findPath(x,y) if (x,y) is either on the wall or a visited cell //1) return false; else if (x,y) is the exit // 2) return true; else mark (x,y) as a visited cell; // 3) for each neighbouring cell(x',y'..