삽입(2)
-
순열 (Permutation) - 삽입방식 | (+중복순열, +함수사용)
- 순열 (Permutation) - n개의 수를 중복을 허용하지 않고(visited) r개를 나열할 수 있는 모든 경우의 수 (1 ≤ r ≤ n) 문제인식) 0부터 9(n)까지의 수가 있다. 이들을 이용하여 4(r)개의 수를 중복없이 나열하고자 할 때 가능한 모든 경우를 각각 한 줄씩 출력하고자 한다면 어떻게 해야할까? int n=9, r=4; 해결과정) 1) 출력에 이용할 배열(a[4]-주황)과 숫자의 중복방지를 위한 방문여부배열(visited[10]-파랑)을 준비한다. 2) 이 배열의 인덱스(idx)마다 0~9까지 삽입하는 반복문을 실행한다. idx는 재귀를 위한 인덱스. 3) 현재 인덱스(idx)에서 사용한 수(i)를 다음 인덱스(idx+1)에서 사용하지 않기 위해 방문처리(visited[i]=1..
2022.04.10 -
삽입정렬 (Insertion Sort)
- 삽입정렬(Insertion Sort) - 정렬을 수행할 위치(i)의 값을 저장(tmp)하고 미리 정렬된 왼쪽 부분(j) 중 적절한 위치에 삽입하는 정렬 문제인식) 다음 그림과 같은 수(數)의 배열이 있다. int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 6, 3}; 이 배열을 오름차순 정렬, 즉 가장 작은 수부터 차례대로 정렬하기 위해선 어떻게 프로그래밍 해야할까? 해결과정) 0) 아래 그림은 이미 4번의 정렬이 이뤄졌다고 가정한 상태이다. 즉, 5번째의 정렬이 이뤄져야 할 상태이며, 4번째 원소까지는 이미 오름차순 정렬이 되어있는 부분이다. 1) 정렬을 수행할 위치를 선정하고 그 값을 저장한다. 2) 왼편에 있는 원소들이 저장한 값보다 크다면 한 칸씩 뒤로 밀어둔다. 3) 적절..
2022.03.29