반응형 알고리즘 문제풀이101 [알고리즘] Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) 컴퓨터 알고리즘의 가장 기본이 되는 것이 정렬 알고리즘이다.그 종류는 여러가지가 있는데 위와 같은 특징이 있다. 이 중에서 3개의 기본적인 정렬 알고리즘을 살펴 보자 선택 정렬 먼저 선택정렬이다이중에서 가장 큰 값을 찾는다그 후에 가장 큰 값과 맨 마지막 값의 자리를 바꾼다.그럼 결과적으로 가장 큰값이 맨 끝자리로 오게 된다. 그렇다면 마지막 값에 대해서는 더이상 신경쓰지 않아도 된다.이후에 남아있는 4개의 데이터에 대해서다시 가장 큰 값을 찾아 4번째 위치에 있는 값과 자리를 바꿔 준다. 이와 같은 알고리즘을 마지막 1개의 값이 남을 때까지 반복해준다면결론적으로 오름차순, 작은값을 맨 끝자리로 보내면 내림차순의 순서로정렬이 가능하다. 12345678.. 2017. 4. 19. [알고리즘] Recursion의 응용 - 멱집합(power set) Recursion의 응용 - 멱집합(power set) 어떤집합의 모든 부분 집합의 집합을 멱집합이라고 한다. 멱집합을 계산하기에 앞서 기본적으로, 집합의 부분집합을 살펴보자원소의 개수가 n개인 모든 가능한 부분집합의 개수는 2^n개이다.각각의 원소에 대해서 그 원소를 포함하던가, 포함하지 않던가라는 2개의 경우의수를 적용한다면 2x2x...xN 이므로 결국 2^n이 된다. 그렇다면 크기가 N인 모든 부분집합의 집합을 어떤식으로 구하는 것일까 Recursion을 이용한다면 다음과 같은 조건을 세운다{a,b,c,d,e,f} 의 모든 부분집합을 나열한다고 했을 때 1) a를 제외한 {b,c,d,e,f}의 모든 부분집합을 나열하고2) {b,c,d,e,f}의 모든 부분 집합에 {a}를 추가한 집합을 나열한다. .. 2017. 4. 19. [알고리즘] Recursion의 응용 - n queens Recursion의 응용 - n queens 가로세로 크기가 N인 2차원 배열(체스판)이 주어진다이 체스판에 N개의 말을 놓는데, 그중에 어떤 2개의 말도 동일한 행이나 열, 대각선에 오지 않게 배치하는것이 n queens 문제이다. 가장 기본적으로 생각 되는것은동일한 행, 열에 배치가 되지 않으므로 한 행, 열당 1개의 말을 배치할수 있다는 것이다 행을 기준으로 생각해 봤을때1개의 행에 놓일수 있는 경우의 수는 4 가지이다. 따라서, 1개의 행에 하나씩 놓으며 그것이 해가 아닐경우 체스말을 치우고바로 전의 행으로 돌아와 다른 경우의 수를 살핀다.이와 같은 방법을 backtracking이라고 한다. backtracking은 자신이 지나온 궤적을 되돌아온다는 것이다즉, 어떠한 결정을 내리다가 안된다는 것이.. 2017. 4. 19. [알고리즘] Recursion의 응용 - Counting Cells in a Blob Recursion의 응용 - Counting Cells in a Blob Counting Cells in a Blob(인접한 셀의 개수 찾기)의 조건 1) 입력으로 하나의 바이너리 이미지가 주어진다(흑백 이미지라고 생각)2) 각 픽셀은 background pixel(흰색) 이거나 image pixel(파란색)이다3) 서로 연결된 image pixel들의 집합을 blob이라고 한다.4. 상하좌우, 대각선 방향도 연결된 것으로 간주 입력- NxN의 2차원 배열 그리드- 하나의 좌표(x,y) 출력- 픽셀(x,y)가 포함된 blob의 크기- (x,y)가 어떤 좌표에도 속하지 않을 경우에는 0을 리턴 123456789현재 픽셀이 속한 blob의 크기를 카운트 하려면 현재 픽셀이 image color가 아니라면 0.. 2017. 4. 18. 이전 1 ··· 18 19 20 21 22 23 24 ··· 26 다음 반응형
