-
JUNGOL...48일지 2021. 3. 12. 10:36
Beginner_Coder/도형만들기2/파스칼삼각형
문제
파스칼 삼각형이란 아래 <표1> 과 같은 자신의 왼쪽 위의 좌표와 오른쪽 위의 좌표 값을 더해서 값을 계속 갱신해 나가는 형태의 삼각형을 말한다.
아래와 같은 파스칼 삼각형의 높이 n과 종류 m을 입력 받은 후 다음과 같은 형태의 파스칼 삼각형을 출력하는 프로그램을 작성하시오.
<처리조건>
m에 대한 파스칼 삼각형의 모습은 아래 <표2>의 모습과 같다.1
1 1
1 2 1
1 3 3 1
1 4 6 4 11 4 6 4 1
1 3 3 1
1 2 1
1 1
11
4 1
6 3 1
4 3 2 1
1 1 1 1 1종류1 종류2 종류3 입력 형식
삼각형의 높이n(1부터 30사이의 정수)과 종류m(1부터 3사이의 정수)을 입력받는다.
출력 형식
위에서 제시한 형태의 파스칼 삼각형을 입력에서 들어온 높이 n과 종류 m에 맞춰서 출력한다.
숫자는 한 칸의 공백으로 구분하여 출력한다.
입력 예
5 1 | 6 3
출력 예
1 | 1
1 1 | 5 1
1 2 1 | 10 4 1
1 3 3 1 | 10 6 3 1
1 4 6 4 1 | 5 4 3 2 1
| 1 1 1 1 1 1
Hint!
<생각하기>>
종류 1과 같이 배열에 저장을 한 후 m의 값에 따라 출력을 바꾸면 된다.
종류 2의 경우는 배열의 아래쪽부터 출력을 하면 된다.
종류 3의 경우는 각 위치에 출력되는 배열의 번호를 적어놓고 생각해 보자.
PascalTriangle.h
#include <iostream> class PascalTriangle: public Base { private: void Case1(int n); void Case2(int n); void Case3(int n); int** CreateArray(int n); void DeleteArray(int** arr, int n); void PrintArray(int** arr, int n, bool space = false); }PascalTriangle.cpp
void PascalTriangle::Code() { int n, m; std::cin >> n >> m; switch (m) { case 1: Case1(n); break; case 2: Case2(n); break; case 3: Case3(n); break; } } void PascalTriangle::Case1(int n) { int** arr{ CreateArray(n) }; arr[0][0] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j <= i; j++) { arr[i][j] = (j > 0 ? arr[i - 1][j - 1] : 0) + arr[i - 1][j]; } } PrintArray(arr, n); DeleteArray(arr, n); } void PascalTriangle::Case2(int n) { int** arr{ CreateArray(n) }; arr[n - 1][0] = 1; for (int i = n - 2; i >= 0; i--) { for (int j = 0; j <= n - i; j++) { arr[i][j] = (j > 0 ? arr[i + 1][j - 1] : 0) + arr[i + 1][j]; } } PrintArray(arr, n, true); DeleteArray(arr, n); } void PascalTriangle::Case3(int n) { int** arr{ CreateArray(n) }; arr[n - 1][n - 1] = 1; for (int i = n - 2; i >= 0; i--) { for (int j = n - 1; j >= i; j--) { arr[j][i] = (j < n - 1 ? arr[j + 1][i + 1] : 0) + arr[j][i + 1]; } } PrintArray(arr, n); DeleteArray(arr, n); } int** PascalTriangle::CreateArray(int n) { int** arr = new int* [n]; for (int i = 0; i < n; i++) { arr[i] = new int[n]; std::fill_n(arr[i], n, 0); } return arr; } void PascalTriangle::DeleteArray(int** arr, int n) { for (int i = 0; i < n; i++) { delete[] arr[i]; } delete[] arr; } void PascalTriangle::PrintArray(int** arr, int n, bool space) { for (int i = 0; i < n; i++) { if (space) { for (int j = 0; j < i; j++) { std::cout << ' '; } } for (int j = 0; j < n; j++) { if (arr[i][j] > 0) { std::cout << arr[i][j] << ' '; } } std::cout << '\n'; } }Beginner_Coder/도형만들기2/달팽이사각형
문제
정사각형의 크기를 입력 받은 후 시계 방향으로 돌면서 다음과 같은 형태로 출력하는 프로그램을 작성하시오.
< 처리조건 >
(1) 가장 왼쪽 위의 좌표부터 차례로 숫자를 대입 시킨다.
(2) 오른쪽으로 채워 나가다가 끝이면 다시 아래 → 왼쪽 → 위 →오른쪽의 순으로 모두 채워질 때까지 반복한다.
입력 형식
정사각형의 크기 n(1부터 100사이의 정수)을 입력받는다.
출력 형식
위에서 언급한 형태로 정사각형의 내부 숫자를 차례로 채운 후의 모습을 출력한다.
숫자 사이는 공백으로 구분한다.
입력 예
5 | 2
출력 예
1 2 3 4 5 | 1 2
16 17 18 19 6 | 4 3
15 24 25 20 7 |
14 23 22 21 8 |
13 12 11 10 9 |Hint!
<생각하기>
처음에는 (1, 1)의 위치에 숫자 1을 담으면 된다. 그리고 오른쪽으로 이동하면서 차례대로 숫자를 늘려가면서 n번을 반복하여 채워나가면 된다. 그런데 만약 다음과 같이 숫자를 먼저 채우고 오른쪽으로 이동을 한다면 가장 오른쪽을 채운 후 범위를 벗어나게 된다.
그러므로 오른쪽으로 먼저 이동을 한 후에 숫자를 채우도록 해야 마지막 위치에서 숫자를 채우고 멈추게 된다. 그러기 위해서는 y를 0으로 초기화 하면 된다.
오른쪽으로 이동이 끝난 후에는 아래쪽 , 왼쪽 , 위쪽 순으로 같은 방법으로 채워나가는 작업을 반복하면 된다.
각각의 이동 횟수가 조금씩 줄어들다가 더 이상 이동할 곳이 없다면 즉, 이동할 횟수가 0이 되면 끝나게 된다.
즉 아래나 위로 이동할 때마다 횟수가 한 번씩 줄어드는 것이다.
그러면 다음과 같이 채우는 작업을 설계할 수 있다.
이동횟수 = n
수 = 1
행 = 1, 열 = 0
n이 0보다 큰동안 반복
이동횟수 만큼 열 증가하고 채우기
이동횟수 감소
이동횟수 만큼 행 증가하고 채우기
이동횟수 만큼 열 감소하고 채우기
이동횟수 감소
이동횟수 만큼 행 감소하고 채우기
void fill() { int i; int num = 1; int m = n; // m은 이동횟수, 처음에는 오른쪽으로 n번 이동해야 한다. int x = 1, y = 0; // 출발지는 (1, 0)이다. // 처음에 오른쪽으로 이동해야 하므로 y = 0이다. while (m > 0) { // 이동횟수가 1번 이상인 동안 반복한다. for (i = 1; i <= m; i++) { // 오른쪽으로 m번 이동하면서 배열을 채운다. y++; arr[x][y] = num++; } m--; // 아래쪽으로 이동하는 횟수는 오른쪽보다 한번 줄어든다. for (i = 1; i < = m; i++) { // 아래쪽으로 m번 이동하면서 배열을 채운다. x++; arr[x][y] = num++; } for (i = 1; i <= m; i++) { // 왼쪽으로 m번 이동하면서 배열을 채운다. y--; arr[x][y] = num++; } m--; // 윗쪽으로 이동하는 횟수는 왼쪽보다 한번 줄어든다. for (i = 1; i <= m; i++) { // 윗쪽으로 m번 이동하면서 배열을 채운다. x--; arr[x][y] = num++; } } }<생각하기>
또 다른 방법을 생각해 보자.
매번 이동하는 횟수를 계산하는 게 귀찮다면 그냥 진행 방향으로 이동을 하다가 벽을 만나면 방향을 바꾸는 방법으로 프로그래밍 할 수 있다. 배열 전체를 0으로 초기화 한 후 출력할 영역 바깥 부분을 모두 1로 채워서 테두리를 만든다. 그리고 진행방향으로 이동을 하면서 채워나가다가 다음에 이동할 위치에 채울 수 없다면(0이 아니라면) 이동을 멈추고 방향을 바꾼다.
아래의 프로그램을 보면서 잘 생각해 보면 어렵지 않게 작성할 수 있다.
이런 방법을 잘 알아두면 수식으로 처리하기 복잡한 문제에서 매우 유용하게 활용할 수 있다.
void fill() { int i; int x = 1, y = 0, num = 1; for (i = 0; i <= n + 1; i++) { arr[0][i] = arr[n+1][i] = 1; // 0행(맨위), n+1행(맨아래) 모두 1로 채우기 arr[i][0] = arr[i][n+1] = 1; // 0열(맨앞), n+1열(맨뒤) 모두 1로 채우기 } while (num <= n*n) { // 채울 수가 n*n 이하인 동안 while(arr[x][y+1]==0) { // 오른쪽이 0인동안 y++; // 오른쪽으로 이동 arr[x][y]=num++; } while(arr[x+1][y]==0) { // 아래쪽이 0인동안 x++; // 아래쪽으로 이동 arr[x][y]=num++; } while(arr[x][y-1]==0) { // 왼쪽이 0인동안 y--; // 왼쪽으로 이동 arr[x][y]=num++; } while(arr[x-1][y]==0) { // 위이 0인동안 x--; // 위쪽으로 이동 arr[x][y]=num++; } } }
SnailSquare.h
#include <iostream> class SnailTriangle : public Base { private: enum class SnailDirection { RightDown, Left, Up, Done }; SnailDirection RightDown(int** arr, int n, int& i, int& j, int& num); SnailDirection Left(int** arr, int n, int& i, int& j, int& num); SnailDirection Up(int** arr, int n, int& i, int& j, int& num); }SnailSuqare.cpp
void SnailSquare::Code() { int n; std::cin >> n; int limitCount = n * n; n += 2; int** arr = new int* [n]; for (int i = 0; i < n; i++) { arr[i] = new int[n]; std::fill_n(arr[i], n, 1); } for (int i = 1; i < n - 1; i++) { for (int j = 1; j < n - 1; j++) { arr[i][j] = 0; } } int num{ 1 }; int i{ 1 }, j{ 1 }; arr[i][j] = num++; while (num <= limitCount) { while (arr[i][j + 1] == 0) { j++; arr[i][j] = num++; } while (arr[i + 1][j] == 0) { i++; arr[i][j] = num++; } while (arr[i][j - 1] == 0) { j--; arr[i][j] = num++; } while (arr[i - 1][j] == 0) { i--; arr[i][j] = num++; } } for (int i = 1; i < n - 1; i++) { for (int j = 1; j < n - 1; j++) { std::cout << arr[i][j] << ' '; } std::cout << '\n'; } for (int i = 0; i < n; i++) { delete[] arr[i]; } delete[] arr; }NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)
NadanKim/CodingTest_JUNGOL
JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.
github.com