C.1 달팽이 문제

1. 프리뷰

주제

n x n 큐브에 시계방향으로 수 배열하기 (달팽이 문제)

알고리즘(Pseudo)

  1. 모서리 90도 커브를 구현할 방법이 없기에 큐브를 기준으로

    상단 가로1 ➡️
    하단 가로2 ⬅️
    우측 세로1 ⬇️
    좌측 세로2 ⬆️

    로 수가 출력될 array variable을 지정해 준다.

  2. if문을 이용, 각 배열에 해당될 때 숫자 ~부터 ~까지 배열에 저장될지 결정해 준다.

  3. set value of j as 0, let j++ until it reaches number = n x n (j는 입력될 수를 의미하며 네 배열변수에 공통으로 사용한다.)

4. 큐브 속껍질로 들어갈수록 저장되는 수의 개수가 줄어듦을 고려한다.


2. 문제점 / 해결방법

  • What kind of Problem?
    • Algorithm 설계 실수
    • Algorithm 의 비효율
    • Syntax에 대한 이해 부족
    • Function 사용에 대한 이해 부족
    • Compiler 호환 문제
    • 잔실수
  • How did you Solved?
    • By searching Google
    • On my own
    • Ask to Friends or People

3. 코드

#include <stdio.h>

int main()
{
  int n;
  printf("enter \"n\" : ");
  scanf("%d", &n);
// **가로1,가로2,세로1,세로2 구분장치** i, h, v & **배열될 수** j & **행배열 위치 지정** h1 ~ v2
  int i=0, h=0, v=0 j=1, h1=0, h2=0, v1=0, v2=0; 
// **열배열 위치 지정**count1 ~ count4
  int count1=0, count2=n-2, count3=1, count4=n-2;
// **2차원 배열 지정** 
  int arr[n][n]; 

  for(i=0 ; j <= n*n ; i++) // 반복문, condition 설정(~ n x n)
  {
/*가로1*/
    if(i % 2 == 0 && h % 2 == 0) 
// condition of '가로1'(i=**0** : 가로1 -> **1** : 세로1 -> **2** : 가로2 -> **3** : 세로2)
    {
      while(count1 < n- (2*h1)) // 해당 행에 입력될 숫자(j)의 수
      {
        arr[0+h1][h1+count1] = j; // 해당 행-열 배열에 j 순차적 저장
        count1++; // 열 증가  
        j++; // 1 ~ 증가
      }
      h1++; // 다음 가로1로 가기 위한 장치(한겹 내부로 진입한다는 의미)
      h++; // h % 2==0 -> 가로1 , h % 2==1 -> 가로2 and so forth...
      count1=0; // 다음번 가로1 입력 시에도 활용될 count=0 으로 초기화
    }
/*가로2*/
    else if(i % 2 ==0 && h % 2 ==1) // 가로2
    {
      while(count2 > (n-1) - (n-2*h2))
      {
// discrete하지 않고 continuous 하게 이어지는 j를 해당하는 행-열 배열에 초기화 시켜준다.
        arr[n-1-h2][count2-h2] = j;
        count2--; // 열 감소 & if condition false -> break the loop 
        j++; // x ~ (x = 가로 2 진입 이전 마지막 j 값)
      }
      h2++; // 다음 가로2로 가기 위한 장치(내부로 진입함)
      h++; // 가로1로 갈 차례임을 의미
      count2=n-2; // 다음 가로2에서도 활용될 '열'관련 변수를 초기값으로 초기화하는 모습
    }
/*세로1*/
    else if(i % 2 == 1 && v % 2 == 0) // 세로1,세로2 구분변수인 v를 사용한 모습
    {
      while(count3 < n-2*v1) // recursion condition
      {
        arr[0+count3+v1][n-1-v1] = j; // 방위로 배열의 '동쪽' 의미
        count3++; // 행입력 & 반복문 탈출 장치
        j++; // 배열될, 전부터 이어지는 수
      }
      v1++; // 세로1-1 -> 세로1-2, 한겹 내부로 진행
      v++; // 세로2로 갈 차례임을 의미
      count3=1; // 초기값으로 초기화

    }
/*세로2*/
    else if(i % 2 ==1 && v % 2 == 1) 
    {
      while(count4 > (n-1) - (n-1-2*v2)) // 가로2에 의해서 공유지점 배열권한을 잃은모습(-1)
      {
        arr[count4-v2][0+v2] = j; 
        count4--; // 조건만족, 행감소
        j++; // 초기화될 수
      }
      v2++; // 한겹 내부로 이동
      v++; // 세로1 차례 의미
      count4=n-2; // 초기값 초기화
    }
  }
/*결과 확인*/
printf("\n\n <Result>\n");
for(int i=0 ; i < n ; i++)
 {
  for(int j=0 ; j < n ; j++)
  {
    printf("%4d", arr[i][j]);
  }
   printf("\n");
 }
return 0;
} // main함수의 종료

4. 결과

When Entered number 7


5. 결론

2차원 배열 초기화 문제에서 순차적 방법 이외(위 90도 달팽이 모양 등)의 방법은 별도 함수 생성을 통해 이뤄진다. 이 문제 알고리즘 구상의 핵심 포인트는 가로와 세로 영역을 조건으로 나누고, 그 안에서 1,2로 다시 분류하는 것이라 생각한다. 다음엔 3차원 배열의 문제도 알아보자!

좋은 웹페이지 즐겨찾기