☝️문제 - 빙빙 돌며 사각형 채우기

코드트리 문제 링크

n * m크기의 직사각형에 대문자 알파벳을 A부터 Z까지 순서대로 증가시키며 달팽이 모양으로 채우는 코드를 작성해보세요.

달팽이 모양이란 왼쪽 위 모서리에서 시작해서, 오른쪽, 아래쪽, 왼쪽, 위쪽 순서로 더 이상 채울 곳이 없을 때까지 회전하는 모양을 의미합니다.

Z 이후에는 다시 A부터 채우기 시작합니다.

n : 행(row), m : 열(column)을 의미합니다.

✌️생각해보기

달팽이 모양으로 돌면서 숫자나 문자를 채우는 것은 달팽이 모양의 움직임만 잘 안다면 어렵지 않은 문제이다. 달팽이 모양을 90도 방향으로 회전하는 것는 것이라고 보면 다음과 같은 그림으로 설명이 된다.

dx, dy 배열을 다음과 같이 둔다면

           //동  남  서  북
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

dir = 0 일 때 x = 0, y = 1 dir = 1 일 때 x = 1, y = 0 dir = 2 일 때 x = 0, y = -1 dir = 3 일 때 x = -1, y = 0 이다.

회전하고 싶을 때는 dir = (dir + 1) % 4라고 하면 된다. 그러면 3 -> 0이 될 수 있다!

dx, dy문제를 풀던 어느 날 갑자기 dx, dy를 수학의 x, y 좌표와 헷갈려서 동 남 서 북의 방향을 dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1}으로 코드를 짰던 적이 있다... 아무리 풀어도 안되길래 곰곰이 보니 dx, dy가 아예 잘못 썼던 것...! (코드트리에서도 x, y을 행, 열로 생각해야 한다고 나와있었다!!)

이 방향만 잘 설정해주고 문제를 접근하면 어렵지 않다.

해설에서는 A~Z 문자를 (char)(i % 26 + 'A')로 썼지만 나는 문자를 ++해주고 Z가 넘어가면 다시 A로 바꿔주는 형태로 만들었다.

🤟 코드 보기

#include <iostream>
#define MAX 100

using namespace std;

int n, m, x, y;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char arr[MAX][MAX] = {0};

bool InRange(int x, int y){
    return 0 <= x && x < n && 0 <= y && y < m;
}

int main() {
    cin >> n >> m;

    arr[x][y] = 'A';
    char alphabet = 'B';
    int dir = 0;
    for(int i = 1; i < n * m; i++){
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(!InRange(nx, ny) || arr[nx][ny] != 0){
            dir = (dir + 1) % 4;
        }

        x += dx[dir];
        y += dy[dir];
        arr[x][y] = alphabet++;

        if(alphabet > 'Z'){
            alphabet = 'A';
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

이번의 실력진단 결과는..... 쬐끔... 올랐다.....ㅋㅋㅋ.... (완전탐색 문제 못풀고 있다.. dx, dy문제도... 아직 익숙하지가 않다 ㅠㅠ 더 열심히 해야된다...!!! 크앙) 그래서 오늘은 dx, dy 문제 풀이에 대해 포스팅하려고 한다!!!

☝️ dx, dy 테크닉

dx, dy 테크닉의 가장 중요한 포인트는.. 각 방향에 맞는 _x좌표의 차를 dx_에 _y좌표의 차를 dy_에 적어두는 것

오른쪽으로 이동한다는 것은 x좌표에 +1, y좌표에 +0 아래로 이동한다는 것은 x좌표에 +0, y좌표에 -1, 왼쪽으로 이동한다는 것은 x좌표에 -1, y좌표에 +0, 위쪽으로 이동한다는 것은 x좌표에 +0, y좌표에 +1 해주면 된다.

이걸 dx, dy 배열에 옮겨놓고 이동하는 방향에 맞춰서 dx, dy 값을 가져와 좌표에 더해주면 된다.

✌️ 되돌아오기 문제

코드트리 문제 링크

문제 형식

(0, 0)에서 시작하여 총 N번 움직여보려고 합니다. N번에 걸쳐 움직이려는 방향과 움직일 거리가 주어지고, 1초에 한 칸씩 움직인다고 했을 때, 몇 초 뒤에 처음으로 다시 (0, 0)에 돌아오게 되는지를 판단하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

두 번째 줄부터는 N개의 줄에 걸쳐 각 줄마다 이동방향과 이동한 거리가 공백을 사이에 두고 주어집니다. 방향은 W, S, N, E중에 하나이며 각각 서, 남, 북, 동쪽으로 이동함을 의미합니다.

1 ≤ N ≤ 100 1 ≤ 한 번에 움직이는 거리 ≤ 10

출력 형식

첫 번째 줄에 다시 시작점으로 되돌아오는 데 걸리는 시간을 출력합니다. 만약 N번 이동을 진행했는데도 시작점으로 돌아오지 못했다면 -1을 출력합니다.

🤟 문제 풀어보기

dx, dy 문제를 풀었다면 어렵지 않은 문제였다.. 다만 나는 0, 0 위치에서 부터 시작하는 걸 배열의 인덱스로 생각하고 100x100 배열을 만들고 시작했다. 풀이 코드를 보면 알 수 있지만 이건 배열을 쓰지 않고도 풀 수 있는 문제이다. 그리고 시작 지점으로 돌아왔다는 것을 확인하는 flag 변수를 썼지만 이것 역시 굳이 없어도 되는 문제이다. 풀이 코드를 보고 또 배운다...

#include <iostream>
#define MAX_N 100

int arr[MAX_N][MAX_N];

//북, 동, 남, 서순으로 dx, dy 정의 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int time; //소요 시간

using namespace std;

int get_dir(char c){
    if(c == 'S'){
        return 0;
    }else if(c == 'E'){
        return 1;
    }else if(c == 'N'){
        return 2;
    }else{
        return 3;
    }
}

int main() {
    int time = 0; //소요 시간
    int n;
    cin >> n;

    int cx = 0, cy = 0; //시작점 좌표
    bool is_zero_start = false; //시작점으로 돌아왔는지 확인하는 변수
    for(int i=0; i<n; i++){
        char dir;
        int dis;
        cin >> dir >> dis;

        while(dis--){
            cx += dx[get_dir(dir)]; //dir방향으로 x좌표 이동
            cy += dy[get_dir(dir)]; //dir방향ㅇ로 y좌표 이동
            time++; //이동 시간 기록

            if(cx == 0 && cy == 0){ //시작점으로 돌아왔다면 break
                is_zero_start = true;
                break;
            }
        }
        if(is_zero_start){
            break;
        }
    }
    if(!is_zero_start){
        cout << -1;
    }else{
        cout << time;
    }

    return 0;
}

시뮬레이션 1의 마지막 문제인 중첩되는 사각형 문제를 풀어보겠습니다! 마지막 문제는 실력체크 문제이므로 정답 해설이 없습니다. 제 코드가 참고가 되면 좋겠습니다:)

☝️시뮬레이션 - 사각형 칠하기

격자에서 사각형을 칠해야하는 문제가 주어지면 이는 2차원 배열로 표현할 수 있다.

이렇게 (2, 5)와 (4, 8)을 양쪽 모서리로 하는 직사각형은 시계방향 90도로 회전한 2차원 배열에서 (2행, 5열)부터 (3행, 7열)로 나타낼 수 있다.
여기서 포인트는 기존 좌표계에서 (x1, y1), (x2, y2)로 이루어진 직사각형이 2차원 배열에서는 (x1 행, y1 열) 부터 (x2 - 1 행, y2 - 1 열) 로 표현된다는 점!!

여기서도 만약 좌표가 음수 값이 나온다면 해당 좌표의 최솟값을 양수로 만들어줄 수 있는 OFFSET을 설정해주어야 한다. 왜냐햐면 배열의 인덱스는 음수가 없기 때문이다.

구간 칠하기 문제가 1차원 배열을 필요로 했다면 사각형 칠하기는 2차원 배열이 필요하다고 생각하면 된다. 구간칠하기 문제에서는 x1, x2 배열을 쓰면서 좌표값을 가져왔다면 이제는 x1, y1, x2, y2 배열을 두고 좌표를 가져와 쓸 수있다.

✌️ 계속 중첩되는 사각형 문제

코드트리 문제 링크

문제

좌표평면 위에 총 n개의 직사각형이 주어집니다. 처음에 주어지는 직사각형은 빨간색이고, 그 다음에 주어지는 직사각형은 파란색입니다. 이와 같이 빨간색, 파란색 순으로 번갈아 가며 주어지고, 겹치는 위치가 있다면 가장 마지막에 덮힌 색으로 취급한다고 했을 때, n개의 직사각형이 주어지고 난 뒤의 파란색 영역의 총 넓이를 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에는 정수 n이 주어집니다. 두 번째 줄부터 각 줄마다 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.

1 ≤ n ≤ 10 -100 ≤ x1 < x2 ≤ 100 -100 ≤ y1 < y2 ≤ 100

출력 형식

첫 번째 줄에 파란색 영역의 넓이를 구하여 출력합니다.

입출력 예제 예제1 입력: 2 2 1 7 4 5 -1 10 3

출력: 20

🤟 문제 풀어보기!

빨간색, 파란색 번갈아 가면서 사각형이 주어지므로 빨간색 사각형은 1로, 파란색 사각형은 2로 두었다. 나는 구현하기 쉽게 짝수, 홀수로 구분하여 번갈아가며 1, 2로 표시하였다.

#include <iostream>
#define OFFSET 100 //x, y좌표의 최솟값이 -100
#define MAX_N 10
#define MAX_R 200

using namespace std;

int x1[MAX_N], x2[MAX_N], y1[MAX_N], y2[MAX_N];
int checked[MAX_R+1][MAX_R+1];
int n, cnt;

int main() {
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];

        x1[i] += OFFSET;
        x2[i] += OFFSET;
        y1[i] += OFFSET;
        y2[i] += OFFSET;
    }

    for(int i=0; i<n; i++){
        for(int x=x1[i]; x<x2[i]; x++){
            for(int y=y1[i]; y<y2[i]; y++){
                if(i%2==0){
                    checked[x][y] = 1; //빨강
                }else{
                    checked[x][y] = 2; //파랑
                }
            }
        }
    }

    for(int i=0; i<=MAX_R; i++){
        for(int j=0; j<=MAX_R; j++){
            if(checked[i][j] == 2){ //파랑의 개수
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

지난 주 487점 보다는 올랐다!! 이번 연휴에 열심히 공부해서 얼른얼른 진도를 나가야 겠다는 생각을 했다.. 🤣 공부하시는 모든 분들 화이팅입니다!!! 좋은 결과 있을 거예요!!!

☝️ 신기한 타일 뒤집기 문제

코드 트리 문제 링크

문제

일직선으로 무한히 나열된 회색 타일이 있습니다. 이 타일은 신기한 타일이기 때문에, 현재 타일의 색이 어떤 색인지와는 상관없이 왼쪽으로 뒤집으면 흰색으로 바뀌고, 오른쪽으로 뒤집으면 검은색으로 바뀌게 됩니다. 아무 타일에서 시작하여 n번의 명령에 걸쳐 움직입니다. 명령은 "x L", "x R" 형태로만 주어지며, "x L"의 경우 왼쪽으로 이동하며 순서대로 현재 위치 타일포함 총 x칸의 타일을 왼쪽으로 뒤집습니다. "x R"의 경우 오른쪽으로 이동하며 순서대로 현재 위치 타일포함 총 x칸의 타일을 오른쪽으로 뒤집습니다. 각 명령 이후에는 마지막으로 뒤집은 타일 위치에 서있는다고 가정합니다.

모든 명령을 실행한 뒤의 흰색, 검은색 타일 수를 각각 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에는 n이 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 명령이 주어집니다. 형태는 “x L” 혹은 “x R” 입니다.

1 ≤ n ≤ 1000 1 ≤ x ≤ 100

출력 형식

첫 번째 줄에 모든 명령을 실행하고 난 뒤의 흰색, 검은색 타일 수를 각각 공백을 사이에 두고 출력합니다.

입출력 예제

예제1 입력: 4 4 R 5 L 7 R 4 L

출력: 4 3

예제2 입력: 2 10 R 11 L

출력: 11 0

✌️ 구간 칠하기!

코드 트리에서 구간 칠하기 문제를 쭉 풀어봤다면 결국 구간 칠하기는 1차원 배열로 구간을 표현한다는 것이 관건이다!

예를 들어 구간 [2, 5], [4, 5], [1, 2]이 주어지고 각 구간을 칠한다고 해보자. 그러면 각 구간을 [x1, x2]로 생각하고 x1 배열과 x2 배열을 만든다.

[2, 5]를 입력받으면 배열에 다음과 같이 저장한다.다음으로 [4, 5]가 주어지면 다음과 같이 된다. 마지막으로 [1, 2]가 주어지면 다음과 같다.

이제 구간을 칠 할 checked라는 1차원 배열을 만든다. 그 다음 x1[0], x2[0] ~ x1[2], x2[2]까지의 값에 해당하는 checked의 인덱스를 찾아 해당 인덱스의 값을 1씩 증가시킨다. 코드로 표현하면 다음과 같다!!

 for(int i = 0; i < 3; i++)
     for(int j = x1[i]; j <= x2[i]; j++)
            checked[j]++;

만약 문제에서 주어지는 좌표의 범위가 음수가 있다면 적당한 OFFSET을 찾아서 모두 양수화를 해줘야 한다. 예를 들어 [-2, 5] 구간을 칠한다면 checked 배열에는 음수 인덱스가 없으니 좌표를 모두 양수화를 시켜준다. x 값이 -100에서 100 사이의 값으로 주어진다면 OFFSET을 최소 100으로 잡아준 뒤 좌표를 OFFSET만큼 증가시켜준다. 그러면 [-2, 5]는 OFFSET만큼 증가시키면 [98, 105]이 될테고 checked에서 해당 좌표 구간을 칠해주면 된다.

또한 구간을 칠하는 것이 왼쪽, 오른쪽으로 이동하는 문제라면 현재 위치에서 왼쪽, 오른쪽 이동하는 부분도 고려해야한다! 현재 위치를 담을 변수를 선언하고 적절한 위치에서 시작해서 왼쪽으로 이동하면 현재위치를 감소시키고 오른쪽으로 이동하면 현재위치를 증가시키면서 이동해야 한다.

🤟 문제 풀어보기!

이 문제에서 중요한 점은 배열의 크기를 설정하는 것이다. 문제에서 무한히 이어진 타일이 주어지고 왼쪽, 오른쪽으로 어떻게 얼만큼 이동할지 모르기 때문에 배열의 크기를 잘 지정해야 한다. 이 때, 이동하면서 음수 인덱스가 나오지 않도록 하기 위해서 최대 범위의 배열을 선언하고 그 중간 지점을 시작 위치로 잡아야 한다. 주어진 x의 범위는 1100이고 n의 범위는 11000이다. 즉 x 좌표는 1~100사이의 값이 주어지고, 명령의 횟수는 최대 1000번이다. 그러면 어느 한쪽으로 최대로 움직인 x좌표는 100 x 1000 이니 100000이 된다. 그래서 MAX_X는 100000으로 설정했다. 또한 x가 왼쪽으로 최대한 갈 수도 있고 오른쪽으로 최대한 갈 수도 있으니 배열의 크기는 2 x 100000 + 1로 잡았다. +1은 해당 인덱스까지도 배열의 크기로 쓰기 위해서 +1 해주었다.

#include <iostream>

#define MAX_X 100000 //x의 최댓값 설정

int arr_x[2*MAX_X+1]; //배열의 최댓값 설정
int w, b;

using namespace std;

int main() {
    int n;
    cin >> n;

    int cur = MAX_X; //타일의 현재 위치는 배열의 중간으로 잡는다.

    for(int i=0; i<n; i++){
        int x;
        char c;
        cin >> x >> c;

        if(c == 'L'){ //왼쪽으로 가면서 흰색으로 뒤집기 (흰색은 1로 표현)
            while(x--) {
                arr_x[cur] = 1;
                if(x) cur--;
            }
        }else{ //오른쪽으로 가면서 검은색으로 뒤집기 (검은색은 2로 표현)
            while(x--) {
                arr_x[cur] = 2;
                if(x) cur++;
            }
        }
    }

    for(int i=0; i<=2*MAX_X+1; i++){ //흰색(1), 검은색(2) 타일의 개수 세기
        if(arr_x[i] == 1) w++; 
        else if(arr_x[i] == 2) b++;
    }

    cout << w << " " << b;
    return 0;
}

나는 일주일 전 487점이였는데 이번에 몇 점일까?! 점수 떨어짐...ㅋㅋㅋㅋㅋㅠㅠ 2차원 배열 문제가 나왔는데 시간 안에 못 풀었다..(그 문제 다시 풀고싶다..) 풀 수 있는 문제였더라도 내가 시간 안에 못 풀었으니 점수가 떨어질 수 밖에 없었을 듯..! 떨어지니까 맘 아프다... 더 열심히 해야지...!!! 😹

이번 주차는 완전 탐색 알고리즘을 공부하는 중이다! 완전 탐색은 가능한 모든 경우의 수를 탐색해서 정답을 찾는 방법이다. Brute Force(브루트 포스)라고도 하는데 이는 무식하게 힘써서 한다는 뜻.. 모든 경우의 수를 탐색하기 때문에 정확도 100%의 암호 해독법으로 매우 강력한 방법이다!!

오늘은 그 중에서도 완전탐색 1에 있는 마지막 문제를 가져왔다! 완전 탐색 공부를 했다면 그리 어렵지 않을 문제인듯..!

☝️ 특정 수와 근접한 합 문제

코드 트리 문제 링크

문제

정수 S와 N개의 수가 주어지면, N개의 수들 중 정확히 2개를 제외하여 남은 N-2개의 숫자들의 합이 S와 최대한 가까워지도록 하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 N과 S가 공백을 사이에 두고 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

3 ≤ N ≤ 100 1 ≤ S ≤ 10,000 1 ≤ 주어지는 수 ≤ 100

출력 형식

2개를 제외하여 나올 수 있는 합 중 S와 가장 가까운 경우에 대해 두 값이 차이를 출력합니다.

✌️ 문제 생각해보기

크게 두 가지를 생각하면 되겠다! 1. 가능한 두 개의 원소를 빼고 모두 더하기 2. 1에서 더한 값과 S의 차이가 가장 작은 차이값 찾기

입력 예시가 5 7 9 1 13 8 일 때, 빼 낼 두 개의 원소를 쌍으로 표현하면 (5, 7), (5, 9), (5, 1), (5, 13), (5, 8) (7, 9), (7, 1), (7, 13), (7, 8) (9, 1), (9, 13), (9, 8) (1, 13), (1, 8) (13, 8) 이다.

이를 제외하고 모든 원소를 더했을 때 값을 sum에다 저장하고 이 sum 값과 S의 차이를 구한 뒤 이게 더 작을 때 min_val을 갱신한다.

🤟 코드 구현하기

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

    int arr[100];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    int min_val = INT_MAX;
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            int sum = 0;
            for(int k=0; k<n; k++){ //두 개 원소 빼고 모든 원소 더하기
                if(k == i || k == j){
                    continue;
                }
                sum += arr[k];
            }
            min_val = min(min_val, abs(sum-s)); //더한 값과 S의 차이를 구하고 더 작을 경우에 갱신한다.
        }
    }
    cout << min_val;

    return 0;
}

(내 레벨은 아직 알에서 나온 병아리 정도니까!!🐣 .. 나중에는 맛있는 치킨이 되야지..!)

현재 나는 level2 Novice Mid2에서 함수, 재귀함수, 정렬까지 어느정도 풀었다! (-> 남은 문제는 주중에 할 예정!!) 현재 상태에서 실력 진단을 해본 결과!!?!!?!!!

사실... 나는 완전탐색을 미리 학습하였다. 그 상태에서 진단을 하니 완선탐색 문제는 풀 수 있지만 dy,dy 문제가 부족하다는 진단이 나왔다! (완전 정확..)

진단 결과! 지금 나는 시뮬레이션 학습이 필요한 상태!! 바로 다음 단계인 시뮬레이션 1과 2를 학습했다!~

날짜와 시간 계산, 진법 계산을 차례로 풀고 나면 구간 칠하기, 사각형 칠하기를 풀면서 시뮬레이션하는 방법에 대해서 배운다!

시뮬레이션 1에서 했던 문제 중 사각형 칠하기 문제를 복습해보자 !!

☝️ 겹치지 않는 사각형의 넓이 문제

[코드트리 문제 링크] https://www.codetree.ai/missions/5/problems/area-of-non-overlapping-rectangle?&utm_source=clipboard&utm_medium=text

문제

좌표평면위에 직사각형 A, B를 먼저 붙이고 그 위에 직사각형 M을 붙였습니다. 아직 남아있는 (M으로 덮이지 못한) 직사각형 A, B의 넓이의 합을 구하는 프로그램을 작성해보세요. 단, 직사각형 A, B는 겹치지 않게 주어진다고 가정해도 좋습니다.

입력형식

첫 번째 줄에는 직사각형 A의 좌측 최하단의 좌표(x1, y1)와 우측 최상단의 좌표(x2, y2)가 공백을 사이에 두고 주어집니다.

두 번째 줄에는 직사각형 B의 좌측 최하단의 좌표(x1, y1)와 우측 최상단의 좌표(x2, y2)가 공백을 사이에 두고 주어집니다.

세 번째 줄에는 직사각형 M의 좌측 최하단의 좌표(x1, y1)와 우측 최상단의 좌표(x2, y2)가 공백을 사이에 두고 주어집니다.

-1,000 ≤ x1 < x2 ≤ 1,000 -1,000 ≤ y1 < y2 ≤ 1,000

출력형식

첫 번째 줄에 M으로 덮이지 못한 직사각형 A, B의 넓이의 합을 출력합니다.

✌️ 문제 분석

내가 생각한 접근법은 a, b, m 직사각형에 해당하는 격자는 +1 해주면 m과 겹치는 부분이 2가 될테니 전체 중 1의 개수만 구하는 것이였다! 그런데 이 부분은 구현이 안되었다.. 아마 내 생각에는 a, b 직사각형마저 겹쳐져 있다면 내 알고리즘은 구현이 안되기 때문이라고 생각한다. 정확한 답변은 토론 게시글에 올려서 답변을 받아 볼 생각...

아무튼 코드트리 해설에 나오는 정답 코드대로 한다면 a 직사각형의 격자는 1로, b 직사각형 격자는 2로, m 직사각형 격자는 3으로 만들어서 3인 격자만 빼고 넓이를 구하는 것!!

(1) offset, max 설정 offset은 x,y 최솟값을 양수로 만들 수 있는 값으로 설정하면 된다! x, y 값은 -1000 ~ 1000의 값을 가지기 때문에 전체적으로 직사각형들을 1사분면으로 옮겨주기 위해서 offset을 1000으로 주었다. offset이 2000이 됨에 따라 x, y 값이 -10001000에서 02000이 되었으므로 x, y의 max는 2000이 된다.

(2) 구간 칠하기 a, b, m 직사각형에 대하여 (x1, y1)부터 (x2, y2)까지 구간까지 각각 1, 2, 3으로 세팅해준다.

(3) 1이거나 2인 구간에 대해서만 cnt 증가하기

🤟 코드

#include <iostream>
#define OFFSET 1000
#define MAX 2000

using namespace std;

int x1[3], y1[3];
int x2[3], y2[3];
int checked[MAX+1][MAX+1];

int main() {
    // 여기에 코드를 작성해주세요.
    for(int i=0; i<3; i++){
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];

        x1[i] += OFFSET;
        y1[i] += OFFSET;
        x2[i] += OFFSET;
        y2[i] += OFFSET;
    }   

    for(int i=0; i<3; i++){
        for(int x=x1[i]; x<x2[i]; x++){
            for(int y=y1[i]; y<y2[i]; y++){
                checked[x][y] = i + 1;
            }
        }
    }

    int cnt = 0;
    for(int i=0; i<=MAX; i++){
        for(int j=0; j<=MAX; j++){
            if(checked[i][j] == 1 || checked[i][j] == 2){
                cnt++;
            }
        }
    }

    cout << cnt;

    return 0;
}

여전히 포함 관계 여부가 헷갈릴 때가 많다. 그럴 때마다 메모장에 그림 그려가면서 생각하는 중!!

알고리즘 배우니까 너무 재밌고 좋다..!!! 더 열심히 해야지!!! 🐣

(썸넬은 나 자신에게 하는 말입니다.. to me... from me...)

오늘 드디어 1단계 Novice low 프로그래밍 기초 문제 다 풀었습니다!~

푼 문제가 380문제밖에 안되는 건.. 객관식 몇 문제들이 제출을 해도 정답 처리가 안되더라구요..

아무튼 1단계 다 풀고 실력진단 해봤습니다! 전체 문제 중에서 3문제 풀었습니다! 4번째 문제는 이진수 문제였는데 시간이 모자랐어요.. 그 다음 문제도 dx, dy문제였는데 마찬가지로 시간이 모자랐습니다..

45일 뒤면 코테 1번 풀 수 있다고 하네요?! 전 매일 4-5시간을 공부할 계획이라 더 빨리 앞당겨지리라 믿습니다!

오늘부터 8주 뒤에 얼마나 성장할 수 있을까 나 자신이 궁금궁금

그럼 오늘부터 2단계 Novice mid 프로그래밍 연습 시작합니다 🥳

링크 : https://www.acmicpc.net/problem/10810

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.

도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.

공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에 걸쳐서 공을 넣는 방법이 주어진다. 각 방법은 세 정수 i j k로 이루어져 있으며, i번 바구니부터 j번 바구니까지에 k번 번호가 적혀져 있는 공을 넣는다는 뜻이다. 예를 들어, 2 5 6은 2번 바구니부터 5번 바구니까지에 6번 공을 넣는다는 뜻이다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ N)

도현이는 입력으로 주어진 순서대로 공을 넣는다.

출력

1번 바구니부터 N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력한다. 공이 들어있지 않은 바구니는 0을 출력한다.

예제 입력 1

5 4 1 2 3 3 4 4 1 4 1 2 2 2

예제 출력 1

1 2 1 1 0

☝️생각해보기

브론즈3 구현 문제! 내가 구현 문제 이해를 잘 못하는 것 같아서.. 문제 이해하는 데 시간이 좀 걸렸는데 나같은 분들이 계실까봐 써봅니다 !

문제에서는 총 n개의 바구니가 있다. 예제에는 n=5로 주어진다. 바구니에 공을 차례로 넣어야 하니 n개의 배열을 만들고 바구니처럼 쓰면 되겠다!

총 m번 공을 집어 넣는다. 이 때 공은 i번부터 j번 바구니에 각각 k번 공을 하나씩 넣으면 된다. 문제에서 m번 i, j, k값이 주어지기 때문에 for문을 m번 돌리면 되겠다!

예제에서 m=4이니 for문은 총 4번 돌아야 한다. 첫 번째 for문에 들어가는 값이 i = 1, j = 2, k = 3이다. 그렇다면 1~2번 바구니에 3번 공을 각각 넣어주면 된다.

두 번째 for문에서는 i = 3, j = 4, k = 4이다. 3~4번 바구니에 4번 공을 각각 넣어주면 된다.

세 번째 for문에서는 i = 1, j = 4, k = 1이다. 1~4번 바구니에 1번 공을 각각 넣어준다. 이미 공이 들어가있으면 새 공을 넣어준다 하였으니 모두 1번 공이 들어간다.

마지막 네 번째 for문에서 i = 2, j = 2, k = 2이다. 2~2번 바구니(2번 바구니 하나에)에 2번 공을 넣어준다. 이미 들어간 공은 빼고 새 공을 넣는다.

최종적으로 바구니에 남아있는 공들을 출력한다. 이 때 비어있는 바구니는 0으로 출력한다.

✌️ 구현하기

배열을 n개를 쓰는데 모두 0으로 초기화해야 한다는 점과 (마지막에 출력 할때 공이 안들어간 배열도 0으로 출력해야 하니까!) 바구니는 1번부터 시작한다는 점 두 가지만 신경쓰면 되겠다!

#include <iostream>
using namespace std;

int main(){
    int arr_n[100] = {0, };
    int n, m;
    cin >> n >> m;

    for(int z=0; z<m; z++){
        int i, j, k;
        cin >> i >> j >> k;
        for(int w = i; w<=j; w++){
            arr_n[w] = k;
        }
    }

    for(int i=1; i<n+1; i++){
        cout << arr_n[i] << " ";
    }

    return 0;
}

링크 : https://www.acmicpc.net/problem/11053

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6 10 20 10 30 20 50

예제 출력 1

4

🌈 DP로 문제를 풀어보자~!

☝️점화식 생각해보기!

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열(Longest Increasing Subsequence)"이라고 한다. (나무위키)

예를 들어 {10, 20, 30, 10} 수열이 있을 때 최장 증가 부분 수열을 만들어보자. 만들어질 부분 수열이 오름차순이어야 한다. DP 배열에는 현재 index까지 만들어진 최장 증가 부분 수열의 크기를 갱신한다.

index = 0일 때, {10}인 자기 자신 하나만 있기 때문에 부분 수열 값은 1이 된다. 따라서 DP = 1 이 된다.

index = 1일 때, {10, 20} 부분 수열이 되기 때문에 DP = 2가 된다.

index = 2일 때, {10, 20, 30} 부분 수열이 되기 때문에 DP = 3이 된다.

index = 3일 때, {10}보다 더 작은 값이 없기 이전에 때문에 부분 수열이 더 만들어지지 않는다. 자기 자신만 있으므로 DP = 1이다. 이렇게 이 수열의 최장 증가 부분 수열의 크기는 DP에서 제일 큰 값인 3이다.

i번 째 수열은 0번부터 i-1번의 수열까지 모두 검사하여 그 중에서 만들어지는 최장 증가 수열의 값을 DP에 갱신하여야 한다. 결국 2중 for문으로 구현하여 모두 검사해야 한다.

✌️ 코드로 구현하기!

이 문제의 가장 핵심 코드는 이렇게 나타낼 수 있다.

for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        //j번째 원소 값이 i번째 원소보다 작아야해
        if(arr[i] > arr[j]){ 
            //i번째 원소까지 추가한 부분 수열이 DP[i]보다 더 크다면 DP[i] 갱신
            dp[i] = max(dp[i] > dp[j]+1);
        }
    }
}

(1) if(arr[i] > arr[j]) i번째 원소 이전에 있는 j번째 원소들이 i보다 작은지 확인하는 단계이다. 만들어질 부분 수열은 항상 오름차순이어야 한다. 따라서 i번째 원소 값이 j번째 원소보다 클 때만 DP값이 갱신되는 것이다.

예를 들어 [10, 20, 30, 10]이 있다면 i = 3일 때 {10}이 추가되어 만들어질 부분 수열이 더이상 항상 증가하는 오름차순이 아니다. 더이상 DP를 갱신할 필요도 없으므로 if문으로 걸러주는 것이다.

(2) dp[i] = max(dp[i] > dp[j]+1)

i번째 원소를 마지막에 추가한 경우가 현재 DP[i]보다 크다면 i번째 원소를 포함하여 DP[i]를 갱신해야 하니 DP[i] = DP[j]+1 이다.

정리하면... (1), (2) 두 조건을 모두 충족한다는 뜻은 (1) j번째 원소가 i번째 원소보다 작으면서 (2) i번째 원소를 마지막에 추가했을 때 부분 수열이 현재 DP[i] 보다 크다면 DP[j]+1하여 DP[i] 값을 갱신한다.

전체 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a, dp;
    int n;
    cin >> n;

    //n개의 원소로 이루어진 a수열을 vector로 만들기.
    for(int i=0; i<n; i++){
        int num;
        cin >> num;
        a.push_back(num);
    }

    //dp는 1로 초기화
    dp.assign(n, 1);

    //최장 증가 부분 수열 크기를 담을 정답 변수
    int ans = 0;

    //모든 데이터에 대해 검사하며 dp 갱신
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            //j번째 원소는 항상 i번째 원소보다 작아야 된다. (LIS는 오름차순이니까)
            if(a[i] > a[j]){
                //i번째 원소를 포함한 부분 증가 수열이 더 크다면 dp를 갱신한다.
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        //갱신된 dp가 현재 값보다 더 크다면 정답 변수 갱신
        ans = max(dp[i], ans);
    }
    cout << ans;

    return 0;
}

링크 : https://www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

⭐️ 문제 풀어보기

연산 방법은 총 3가지가 있다. (1) N-1 (2) N/2 (나누어 떨어질 때) (3) N/3 (나누어 떨어질 때) 이 3가지 방법으로 주어진 N을 1로 만들면 된다. 총 연산의 횟수가 가장 작아야 한다.

☝️ 점화식 생각해보기

N을 1부터 예를 들어 보면.. N = 1 라면 원하는 목표 1이니 연산이 0번 이루어진다. N = 2 라면 N-1 연산이나 N/2 연산으로 목표 1을 만들 수 있어 _최소 연산이 1번_이다. N = 3 라면 N-1 연산 후 N/2 연산을 하여 목표 1을 만들 수 있지만 연산 횟수가 2번이다. 반면, N/3 연산으로 목표 1을 만들 수 있어 _최소 연산이 1번_이다.

N이 1, 2, 3일 때의 최소 연산은 구해졌다. 그렇다면 N = 4 라면? N = 4 라면 N/2 연산을 하면 N = 2가 된다. N = 2일 때는 앞서 N = 2일 때 구해둔 최소 연산이 1번을 알 수 있다. 총 최소 연산은 (N/2연산 1번) + (N=2 일 때 최소 연산 1번) = 2번이다. 이렇게 앞에 구해둔 최소 연산이 DP 배열에 있으면 그 값을 찾아서 더하면 된다.

✌️ DP 만들기

앞서 구한 내용을 바탕으로 DP 배열을 만들어보자. DP 배열에는 우리가 원하는 결과값을 저장한다. N = 1일 때 최소 연산이 0번이니 DP[1] = 0 N = 2일 때 최소 연산이 1번이니 DP[2] = 1 N = 3일 때 최소 연산이 1번이니 DP[3] = 1 N = 4일 때 N/2 연산 이후 N=2일 때 구해둔 연산과 더한다. DP[2] + 1 = 1 + 1 = 2

🤟 코드로 나타내기

결국 N을 1로 만들기 위해서는 N-1은 연산 횟수 1번 N/2은 연산 횟수 1번 N/3은 연산 횟수 1번이므로 한번의 연산을 거치면 +1을 해주면 된다. 이를 코드로 나타내면.. DP[N] = DP[N-1] + 1 (연산 횟수 +1) DP[N] = DP[N/2] + 1 (연산 횟수 +1) DP[N] = DP[N/3] + 1 (연산 횟수 +1) 이렇게 된다. 이 세 개 중 가장 작은 값을 DP에 저장해야 한다.

예를 들어, DP[4]가 있다면 DP[4-1] + 1, DP[4/2]+1, DP[4/3] + 1 중 가장 작은 것을 찾는다. DP[3] + 1 = 1 + 1 = 2 DP[4/2] + 1 = DP[2] + 1 = 1 +1 = 2 DP[4/3] + 1 -> 나누어 지지 않음 따라서 2가 가장 작음을 알 수 있다. DP[4] = 2로 갱신한다.

이 부분을 코드로 나타내면 다음과 같다.

dp[1] = 0; 
for(int i=2; i<=N; i++){
    // N-1 연산 
    dp[i] = dp[i-1] + 1; 

    // N-1 연산과 N/2 연산 중 더 작은 것 선택
    if(i%2 == 0) dp[i] = min(dp[i]. dp[i/2] + 1);

    // N-1 연산과 N/3 연산 중 더 작은 것 선택
    if(i%3 == 0) dp[i] = min(dp[i], dp[i/3] + 1);
    // 둘 중에 아무것도 나누어 지지 않았다면 N-1 연산 선택
}

전체 코드를 보면 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> dp;
    dp.assign(n+1, -1);
    dp[1] = 0;

    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1] + 1;
        if(i%2 == 0) dp[i] = min(dp[i], dp[i/2] + 1);
        if(i%3 == 0) dp[i] = min(dp[i], dp[i/3] + 1);
    }

    cout << dp[n] << endl;

    return 0;
}

난 큰 인물이 되고 싶긴 때문에 일단 사진 하나 박는다.. 바킹독님 강의 오늘부터 하나씩 파헤칩니다... 그럼 시작!

🖐️시간 복잡도

-문제 1번- (문제 설명) N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 10만 이하의 자연수이다.

int func1(int N){
    int sum = 0;
    for(int i=N; i>=3; i--){
        if(i%3 == 0 || i%5 == 0){
            sum += i;
        }
    }
    return sum;
}

내가 만든 func1 함수는 O(n)의 시간복잡도를 가진다.

-문제 2번- (문제 설명) 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.

int fun2(int arr[], int N){
    for(int i=0; i<=N; i++){
        for(int j=i+1; j<=N; j++){
            if(arr[i]+arr[j] == 100 && i != j){
                return 1;
            }
        }
    }
    return 0;
}

내가 짠 코드이다. O(n2)의 시간복잡도. (생각해보니 if문에 i != j 조건 필요없네..) 3강에서 O(n)으로 푸는 방법을 소개한다고 함.

O(n²)인 이유는 이중for문이니까...라고 간단히 생각하겠지만 그래도 자세히 들여다보면.. i=0일 때 n-1개의 수에 대해 합을 100과 비교하고, i=1일 때 n-2개의 수에 대해 합을 100과 비교하고 이렇게 반복하니... (n-1) + (n-2) + ... + 3 + 2+ 1 = (n²-n)/2이므로 O(n²)이다.

-문제 3번- (문제 설명) N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. n은 10억 이하의 자연수이다.

int func3(int N){
    for(int i=2; i<N; i++){
        if(i*i == N){
            return 1;
        }
    }
}

내가 짠 코드는 이렇다. O(n)...

int func3(int n){
    for(int i=1; i*i <= n; i++){
        if(i*i == N) return 1;
    }
}

바킹독님 코드.. O(√n)이므로 내가 짠 코드보다 훨씬 더 빨리 돌아간다. 바로 i*i <= n인지 확인하는 부분이 있기 때문에!! (->작은 부분이지만 큰 차이를 만든다!! 꼼꼼하게 코딩하기!!!)

-문제 4번- (문제 설명) N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.

int func4(int N){
    int i = 2;
    while(i*2 <= N){
        i *= 2;
    }
    return i;
}

내가 짠 코드... 시간 복잡도는... 음....

아래는 바킹독님 코드.. 똑같이 짰다....!

int func4(int N){
    int val = 1;
    while(2*val <= n) val *= 2;
    return val;
}

이렇게하면 N이 2k 이상 2k+1 미만이라고 할 때 while문 안에서 val은 최대 k번만 2배로 커진다.(2의 거듭제곱이니까) 그러고나면 val은 2k가 되고, 이후 while문 안의 2*val <= N이 거짓이 되어 탈출한다. 따라서 N이 2k 이상 2k+1 미만이라고 할 때 시간복잡도가 O(k)인데 k는 결국 log이니 O(logN)이 된다.

🖐️공간복잡도

코테에서 신경 써야하는 복잡도는 대체로 시간 복잡도를 의미한다. 공간복잡도와 관련하여서는 메모리 제한이 있을 경우가 있다.

> 512MB = 1.2억개의 int

메모리 제한이 512MB일 때 int 변수를 약 1.2억개 선언할 수 있다. 이 부분은 기억하면 좋다.

🖐️정수 자료형

정수 자료형과 각각 표현할 수 있는 수의 최댓값은 다음과 같다.

short(2byte) ---------> 2¹⁵-1(=32767) int(4byte) ------------> 2³¹-1(=2.1*10⁹) (대략 21억) long long(8byte) ----> 2⁶³-1(=9.2*10¹⁸)

이 범위를 넘어서는 수를 저장하게 되면 integer overflow가 발생한다. integer overflow는 int의 자료형 범위를 까먹어 자주 발생할 수 있다. 이를 해결하고자 전부 다 long long 형으로 선언하는 방법도 있다. (좋은 습관은 아니지만..?)

unsigned long long 범위를 넘어서는 수를 저장하길 요구하는 문제를 만나면 string으로 선언해야한다. 그런 문제가 굳이굳이 나온다면 c++로 구현하는 건 너무 어려우니 파이썬으로 하는 게 낫다고 함..

🖐️실수 자료형

(1) 실수 자료형은 double을 써야 한다! 실수 자료형은 float(4byte), double(8byte) 이렇게 2가지가 있는데 실수의 특성상 실수의 저장/연산 과정에서 오차가 생길 수 밖에 없다. 그러니 실수 자료형이 필요할 때는 double을 써야한다.

float은 유효숫자가 6자리인데 반해 double은 유효숫자가 15자리이다. 이것은 double이 상대오차 10^-15까지 안전하다는 것을 의미한다. float이 메모리를 적게 쓰긴 하지만 어찌됐든 실수가 필요할 때는 무조건 double을 쓸 것!

예를 들어 문제에서 '절대/상대 오차는 10^-6까지 허용한다.'고 제시되면 이것은 실수 자료형 문제이므로 double을 쓰면 된다. 이것은 실수 자료형은 필연적으로 오차가 있으니까 제시되는 단서이다. 따로 이렇게 제시되지 않으면 열에 아홉은 정수형으로 해결가능한 문제이다.

(2) double에 long long 범위의 정수를 담으면 안된다! double은 유효숫자가 15자리인데 long long은 최대 19자리니까 안된다. int는 최대 21억이므로 double에 담아도 오차가 생기지 않는다..

(3) 실수를 비교할 때 등호를 사용하면 안된다! 오차 때문에 실수가 같은지를 확인하고 싶을 땐 둘의 차이가 아주 작은 값대략 10^-12(=1e-12) 이하면 동일하다고 처리하는 게 안전..