기본적인 정렬 알고리즘
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,..
미로찾기 Maze
[[0,0,0,0,0,0,0,1], [0,1,1,0,1,1,0,1], [0,0,0,1,0,0,0,1], [0,1,0,0,1,1,0,0], [0,1,1,1,0,0,1,1], [0,1,0,0,0,1,0,1], [0,0,0,1,0,0,0,1], [0,1,1,1,0,1,0,0]]위는 미로를 표현한 2차원 리스트이다. 1은 벽이라 통과할 수 없고 0은 통로이다. 출발점은 [0][0]이고 출구는 [n-1][n-1]인 지점이다. 순환적 사고현재 위치에서 출구까지 가는 경로가 있으려면1) 현재 위치가 출구이거나 혹은2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 def findpath(x,y):if maze[x][y] == exit: return True #현 위치가 출구라면 Tru..
순환의 개념과 기본 예제 3
순환 함수의 기본 조건적어도 하나의 base case, 순환되지 않고 종료되는 case가 있어야 함.모든 case는 base case로 수렴해야 함. 암시적 매개변수가 아닌 명시적 매개변수를 사용해야 함 def search(data,n,target): for i in range(n): if data[i] == target: return i return -1 data = [1,2,3,4,5,6,7] print(search(data,7,4))암시적 : 리스트 data의 인덱스는 0부터 n-1이라고 생각하고 시작 인덱스는 생략함. def search(data,begin,end,target): if begin > end: # base case return -1 elif target==data[begin]:ret..
