알고리즘:달팽이관

달팽이관 알고리즘

- 2차원 배열을 달팽이관 처럼 접근하는 알고리즘.

동작

- 아래와 같은 그림으로 동작하는 알고리즘을 작성

그림표현	숫자로 표현
	1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9

알고리즘 작성

- 보통 배열을 이용한 알고리즘의 경우 접근 순서대로 배열의 위치를 적어 보는 것이 편리하다.

- 배열 좌표

(0,0)	(0,1)	(0,2)	(0,3)	(0,4)
(1,0)	(1,1)	(1,2)	(1,3)	(1,4)
(2,0)	(2,1)	(2,2)	(2,3)	(2,4)
(3,0)	(3,1)	(3,2)	(3,3)	(3,4)
(4,0)	(4,1)	(4,2)	(4,3)	(4,4)

- 2차원 배열(5*5) 좌표의 위치를 보면 위 표와 같으며 2차원 배열에 접근하기 위해서 2중 반복문을 사용하겠다.

- 반복문을 토대로 접근 순서를 표시해보면 아래와 같다.

- 위 표를 보면 알 수 있는 것이 몇 가지 있다.

1. 배열의 F와 B 둘 중 하나의 인자만 값이 증가/감소하며 내부 반복문 시작 시 증가/감소되는 배열 인자의 위치가 변경된다.

- ex) [내부 반복문 시작]             

배열(F,B); //B값 변경 

  [내부 반복문 종료]  

  [내부 반복문 시작] 

배열(F,B);F값 변경

  [내부반복문 종료]

2. 배열 B 인자가 변경되고 반복문이 종료되면 내부 반복문의 횟수가 줄어든다.

ex) (0,0)~(0,4) : 5회 반복 후...

(1,4)~(4,4) : 4회 반복으로 횟수가 줄었다.

3. 배열 F 인자가 변경되고 반복문이 종료되면 값의 변경이 증가->감소, 감소->증가로 변한다.

ex) (1,4)~(4,4) : F 인자 값이 증가 

다음 Loop 에서 (4,3)~(4,0) : B 인자 값이 감소

4. 외부 반복문의 횟수

외부 반복문의 횟수는 [배열크기]*2-1 의 횟수입니다.

ex) 5*5 배열일 경우 외부 반복문 실행 횟수는 (5*2)-1 이 됩니다.

이제 위의 분석자료를 기반으로 직접 코딩해보자.

필요한 변수는

- 배열의 인자 값에 사용되는 F와 B, 

- 배열에 증가 값을 입력하기 위한 count=1,

- 배열 인자 값 증가/감소를 수행하기 위한 트리거 TR=1,

- 내부 반복문 횟수를 줄이기 위한 Start=0,

- 변경 할 배열 인자 값 구분과 내부반복문 횟수를 결정하는대 사용 될 변수 Condition=0.

*소스코드 작성은 그날 기분에 따라 c와 c++ 중 하나를 선택해서 작성합니다.

- c++을 평소 잘 사용하지 않으니 될 수 있으면 c++로 작성 할 생각입니다.

알고리즘 소스코드

- c++로 작성했습니다.

- 변수 선언 및 동적배열 할당/해제, 배열의 출력 부분은 기재하지 않았습니다.

소스코드

실행 결과

분석/코딩하는 시간에 비해 

표 작성과 이미지 때문인지 게시글 작성하는 시간이 너무 오래걸린다...

될 수 있으면 배열을 이용하는 코딩은 멀리하고 싶어졌다..

하지만 정렬 알고리즘을 생각하면 ㅠㅠㅠ