검색결과 리스트
글
원 위에 나열된 수 제거하기
알고리즘.데이터구조
2011. 3. 23. 16:08
1부터 n까지의 수를 원 위에 차례로 나열하고 k 번째 수를 지워간다. k보다 적을 때까지 반복한다
입력: n, k (n > k > 0)
출력: 최종 남은 숫자들(지워진 순서로 출력, 역순으로 출력) / 지워진 숫자들
조건: 함수는 재귀적인 기법 이용 / n보다 적은 배열 하나만 이용
입력: n, k (n > k > 0)
출력: 최종 남은 숫자들(지워진 순서로 출력, 역순으로 출력) / 지워진 숫자들
조건: 함수는 재귀적인 기법 이용 / n보다 적은 배열 하나만 이용
1. 반복루프를 사용한 방법
(1) n크기의 배열을 사용. 어떤 수 n은 (n-1)배열요소에 위치한다
(2) K번째 배열요소에는 지워진 순서가 기록되고, 남아있는 수의 배열요소에는 0값을 저장하고 있다.
(3) 함수 종료 후, 기록된 순서를 통해 지워진 순서, 역순 출력을 할수 있고,
배열요소가 0인 것을 찾아 남아있는 수들을 출력 할 수 있다.
(2) K번째 배열요소에는 지워진 순서가 기록되고, 남아있는 수의 배열요소에는 0값을 저장하고 있다.
(3) 함수 종료 후, 기록된 순서를 통해 지워진 순서, 역순 출력을 할수 있고,
배열요소가 0인 것을 찾아 남아있는 수들을 출력 할 수 있다.
2. 재귀함수를 사용한 방법
(1) 단순히 위의 반복버전을 재귀함수로 변경한 버전
3. 최고 n - (n/k) 크기의 배열을 사용하는 재귀함수
(1) 첫번째, 두번째 재귀호출은 배열을 한번 순회하기 위해 루프문을 구현한 것이고,
(2) 세번째 재귀호출은 한번의 순회의 남아있는 수들로 재구성한 새 배열을 가지고, (1)과정을 재적용한다.
(3) 알고리즘이 종료하면 전역변소 $e에는 남아있는 수의 개수를 저장하고 있으면 array의 0~($e-1) 요소에 그 값이 위치한다
(2) 세번째 재귀호출은 한번의 순회의 남아있는 수들로 재구성한 새 배열을 가지고, (1)과정을 재적용한다.
(3) 알고리즘이 종료하면 전역변소 $e에는 남아있는 수의 개수를 저장하고 있으면 array의 0~($e-1) 요소에 그 값이 위치한다
3번에 대한 그림 설명
'알고리즘.데이터구조' 카테고리의 다른 글
| [알고리즘] 알고리즘 글 목록 (0) | 2013.07.08 |
|---|---|
| 프로그래밍 문제 접근법 (0) | 2011.04.26 |
| 원 위에 나열된 수 제거하기 (0) | 2011.03.23 |
| 합병정렬(Merge Sort) (0) | 2011.03.23 |
| HMAC-SHA1 (0) | 2011.03.11 |
| 문제5 그래픽편집기 (0) | 2011.02.18 |
