합병 정렬 merge sort
분할 정복 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복 : 각각의 작은 문제를 순환적으로 해결합병 : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함 ALGORITHMS 이 단어를 반으로 쪼개고 ALGOR ITHMS devideAGLOR HIMST recursively sort 각각 정렬한 뒤AGHILMORST merge 합병한다. 1,2,2,3,4,5,6,7 2,4,5,7 1,2,3,6 2,5 4,7 1,3 2,6 5 2 4 7 1 3 2 6 mergeSort(A,p,r): if p0 and len(R)>0: #L과 R에 원소가 남아있을 때 if L[0]>R[0]: #R의 값이 작다면 tmp.append(R[0]) #R을 먼저 tmp에 삽입 R.pop(0) #R의 첫번째 ..
기본적인 정렬 알고리즘
simple, slow - Bubble sort, Insertion sort, Selection sortfast - Quick sort, Merge sort, Heap sortO(N) - Radix sort selection sort29 10 14 37 13 중에서 가장 큰 값을 찾는다. 이 값을 맨 마지막 자리와 바꾼다. 맨 마지막 자리를 제외한 나머지 수 중에 가장 큰 수를 맨 뒤에 넣는다. 반복한다.data=[29,10,14,37,13] for i in range(4,0,-1): m = max(data[:i+1]) data[i],data[data.index(m)] = m,data[i] print(data)수행시간:for문은 n-1번 반복, 가장 큰 수를 찾기 위한 비교 횟수 n-1,n-2,n-3,...
멱집합 powerset
멱집합은 집합의 모든 부분집합이다. {a, b}가 있으면 {}, {a}, {b}, {a,b} 가 멱집합이다.원소 a를 하나 빼고 나머지 원소들로 부분집합 A를 만들고 a와 A를 합한 것, a가 없고 A만 있는 것을 찾아내면 된다. 원소가 있는지 없는지에 따라 트리를 만들면 저런 모양이 된다. 리프 노드를 보면 {}, {a}, {b}, {a,b}가 있으므로 멱집합이 완성된다. 왼쪽 가지와 오른쪽 가지를 include[k] = True, include[k] = False로 표현했다. True면 해당 인덱스의 원소가 있는 것이고 False면 해당 원소를 제외하고 부분 집합을 만드는 것이다. 계속 돌리다보면 공집합부터 모든 원소가 있는 집합이 만들어진다. include의 인덱스 i가 True라면 arr에서 해당..
Counting Cells In A Blob
각 픽셀은 background pixel(0)이거나 image pixel(1)이다.서로 연결된 image pixel들의 집합을 blob이라고 부른다.8방향으로 연결이 가능하다. 입력 2차원 grid[N][N], 하나의 좌표 x,y출력 blob의 크기, pixel이 blob에 속하지 않으면 0 현재 픽셀의 blob 크기를 세려면 픽셀이 1이어야한다. 그러므로 1이 아니라면 0을 리턴한다.픽셀이 1이면 1을 카운트하고 중복 카운트를 방지하기 위해 2를 대입한다.8방향으로 이웃한 픽셀에 대해 그 픽셀의 좌표를 인자로 갖는 함수를 재귀적으로 호출한다.s=[ [1,0,0,0,0,0,0,1], [0,1,1,0,0,1,0,0], [1,1,0,0,1,0,1,0], [0,0,0,0,0,1,0,0], [0,1,0,1,0,..
