ohsopp's coding

코드를 작성하다보면 컨테이너형 자료 구조가 필요할 때가 있다. 크게 두 가지로, 하나는 배열이고 다른 하나는 연결 리스트다.

이 둘은 프로그래머가 어떤 목적으로 사용하느냐에 따라 선택이 나뉜다.

배열(Array)

장점 : 위치에 관계없이 연산으로 항목에 접근하므로 참조 시간이 빠르다.

단점 : 크기가 고정되고 항목 간의 위치가 연속하므로 삽입/삭제 시 불리하다.

예를 들어, 4 byte int형 배열 int ary[6]가 있다고 하자. 배열의 전체 크기는 배열 선언 시 4 byte * 6 = 24 byte로 고정된다.

배열의 시작 주소를 ary라고 할 때, 각 인덱스의 주소는 다음과 같다.

ary[0]의 주소 : ary + (4 * 0)

ary[1]의 주소 : ary + (4 * 1)

ary[2]의 주소 : ary + (4 * 2)

. . .

ary[5]의 주소 : ary + (4 * 5)

메모리상에서 배열은 연속되는 주소값을 갖는다. 여기서 항목을 추가 또는 삭제한다면 실행 후에도 연속된 메모리 주소를 유지해야하므로 기존 항목을 밀어내는 등 불필요한 이동이 발생한다.

연결 리스트(Linked List)

장점 : 항목들 간에 참조 포인터로 연결되어 있으므로 삽입/삭제 시 유리하다.

단점 : 항목의 개수가 늘어나면 접근성이 떨어지고, 참조 포인터를 이용하기 때문에 배열보다 메모리 관리 측면에서 불리하다.

연결 리스트는 data 필드와 link 필드로 나뉜다. data 필드는 항목의 값을 저장하고, link 필드는 연결된 노드의 주소를 가리킨다.

따라서 n번째 항목에 접근하려면 단방향 링크드 리스트의 경우, 처음부터 n번 만큼 이동하여야 한다.

양방향 링크드 리스트(doubly linked list)의 경우 단방향보다 접근성이 향상되지만, 추가적인 link 필드를 필요로 한다.

종합해보면 빠른 접근이 필요할 때에는 배열을,

삽입/삭제 연산이 많은 경우엔 연결 리스트를 사용하면 효율적이다.

물론 이 개념은 C++뿐만 아닌 모든 프로그래밍 언어에서 동일하다고 보면 된다.

Problems :

2022.01.29 - [🏆 Codeforces/⏳ Solved problems] - [C++] Codeforces #768 Div.2 A : Min Max Swap

2022.01.29 - [🏆 Codeforces/⏳ Solved problems] - [C++] Codeforces #768 Div.2 B : Fun with Even Subarrays

2022.02.02 - [🏆 Codeforces/⌛ Unsolved problems] - [C++] Codeforces #768 Div.2 C : And Matching

한국 시간으로 21/01/27 오후 11:35분, Codeforces Round #768 (Div. 2)에 처음으로 참가를 했다.

Codeforces에서는 보통 달마다 5번 정도의 대회가 열린다고 한다.

대회의 진행 방식은 제한된 시간(약 2시간) 내에 문제들의 정답을 맞춘다.

보통 5~6 문제 정도 출제 되는데 A부터 알파벳 순으로 매겨지며 뒤로 갈수록 난이도가 높다.

점수가 매겨지는 방식은 문제가 공개되면, 난이도에 따라 초기 점수가 나타나며 시간이 지날수록 낮아진다.

또한 다시 submit을 할 경우 50점씩 차감된다. (이거 모르고 막 제출했다가 200점 정도 날린 듯 ㅎㅎ)

즉, 가능한 빠른 시간 내에 최대한 틀리지 않고 적은 시도에 맞힐수록 높은 점수를 획득할 수 있다.

Lock/Hack 개념도 있긴 한데, 아직은 잘 모르겠어서 여기서는 생략하겠다.

레이팅에 따라 Div. 1, Div. 2, Div. 3으로 대회 자체의 난이도 또한 나뉜다고 한다.

UnRanked(a.k.a 뉴비)인 나는 Div. 3에 참가하면 됐지만, Div. 3은 기회가 많이 없기에 처음임에도 Div. 2에 참가했다.

코드포스에는 레이팅에 따라 참가자들에게 색깔과 칭호를 부여하는 시스템이 있다.

백준과 계정 연동을 하면 대회 참가시 레이팅에 따라 백준 아이디에도 반영된다. (사실 좀 멋있다; 아니 많이)

본론에 들어가기 앞서 결과부터 말하자면 6문제 중 2문제(A, B번)만 맞혔다.

A 문제는 시작 후 Accepted까지 11분 걸렸지만, 이놈의 B가 말그대로 '문제'였다;

그래서 B번 건너뛰고 C번 풀려 했지만 앞 문제부터 풀어야 하는지, 일정 시간이 지나야 하는지 넘어가지진 않아서 울며 겨자먹기로 붙잡고 있었다.

2번 째 시도까지는 출력 오류, 3번 째 시도에서는 런타임 오류다. (여기서 점수 많이 깎인 것 같다.)

문제에서 요구하는 알고리즘 완벽하게 이해했고 예제 테스트 케이스도 다 맞았는데 나도 모르는 반례가 자꾸 발견된 듯 하다.

그래서 이 조건, 저 조건 추가하다보니 코드가 많이 더러워진 것을 발견했다.

문제를 맞춰도 이런 식이라면 맞춘 게 아니라는 생각에 지금껏 작성해둔 코드 다 지우고 #include...부터 다시 시작.

써내려가다보니 내가 지금껏 고민했던 수많은 조건들이 갑자기 떠오른 한 방법으로 퉁쳐질(?) 수 있을 것 같았다.

에빙하우스 망각 곡선 되기 전에 얼른 작성하고 예제 테스트 케이스까지 통과한 것을 확인 후 코드 제출했다.

Accepted

기쁨보다는 허무함이 좀 더 컸던 것 같다. B번 맞힌 후 C번 문제를 잠깐 봤는데 B번에서 엉뚱하게 헤매지 않았다면 C번도 가능했을 것 같다. (그렇지만 헤매는 것도 내 실력인 걸,,)

급하게 생각하려는 습관 좀 줄이고 시간 될 때마다 참가하면서 실력을 키워 나가야겠다.

Codeforces Round #768 (Div. 2) 나머지 문제들 풀면서 글 올릴 예정.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

문제 해결

BFS를 사용하는 구현 문제로,

처음에는 먹을 수 있는 가장 가까운 거리의 물고기가 있는 위치를 찾아서 현재 아기 상어의 위치와의 배열의 인덱스 차이를 더하는 식으로 계산했더니 오류가 났다.

​

이것 때문에 10분 정도를 헤맸는데, 아기 상어보다 몸집이 큰 물고기가 있는 경우 돌아가야 하는데 단순히 배열의 인덱스 차이를 더하는 식으로 계산하는 경우 돌아가지 않고 큰 물고기가 있는 경로를 통과해서 가게 된다.

​

그래서 (X, Y)에서의 최소 거리를 저장하는 큐 d를 하나 더 추가하고 (X, Y)에 갈 수 있는 경우에만 현재 거리에 1 더한 값을 push하는 것으로 해결했다.

​

변수 설명 :

- fx, fy : 현재 아기 상어가 있는 위치 좌표

- nx, ny : 먹으러 갈 다음 물고기가 있을 때 그 위치 좌표

- eats : 먹은 물고기의 수

- fsize : 아기 상어의 몸집 크기

코드

#include <iostream>
#include <queue>
using namespace std;

int n, t, fx, fy, nx, ny, eats, mindist, fsize = 2, map[22][22], visit[22][22];
int dx[] = { 0,-1,1,0 }, dy[] = { -1,0,0,1 };


int bfs(int x, int y) {
    visit[x][y] = 1;

    queue<pair<int, int>> q; q.push({ x,y });
    queue<int> d; d.push(0);

    nx = 22, ny = 22, mindist = 4000;  // 초기에 임의의 큰 값으로 설정

    int chk = 0;

    while(!q.empty()) {
        int xx = q.front().first, yy = q.front().second;
        int dd = d.front();
        q.pop(); d.pop();

        if (map[xx][yy] && map[xx][yy] < fsize) {  // 물고기를 먹을 수 있을 때
            chk = 1;

            if (dd < mindist) {  // 물고기와의 거리가 mindist보다 작다면 무조건 작은 쪽으로
                nx = xx;
                ny = yy;
                mindist = dd;
            }
            
            else if (dd == mindist) {  // 물고기와의 거리가 mindist와 같은 거리일 때
                if (xx < nx) {
                    nx = xx;
                    ny = yy;
                }
                else if (xx == nx && yy < ny) ny = yy;
            }
        }
        
        for (int i = 0; i < 4; i++) {
            int X = xx + dx[i], Y = yy + dy[i];
            
            // 작거나 같은 몸집의 물고기가 있는 경로는 지나갈 수 있음
            if (X && Y && X <= n && Y <= n && !visit[X][Y] && map[X][Y] <= fsize) {
                visit[X][Y] = 1;
                q.push({ X,Y });
                d.push(dd + 1);
            }
        }
    }

    return chk;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 9) { fx = i, fy = j; map[i][j] = 0; }
        }

    while (1) {
        //memset(visit, 0, sizeof(visit)); 이유는 모르겠지만 백준에서는 memset을 인식하지 못한다
        fill(visit[0], visit[21], 0);

        if (!bfs(fx, fy)) break;

        else {
            eats++;
            t += mindist;

            fx = nx, fy = ny;
            map[fx][fy] = 0;

            if (fsize == eats) {
                eats = 0;
                fsize++;
            }
        }
    }

    cout << t;
}

문제 해결

DP(Dynamic Programming) 방법으로 풀릴까 싶어 30분이 넘도록 고민하다가 도저히 갈피를 잡을 수 없다고 판단해서 문제 태그를 살펴봤다.

소수, 정수론, 에라토스테네스의 체, 등등은 당연하지만.. 그 중에 눈에 띄는 태그가 있었는데 바로 "너비 우선 탐색"이다.

바로 코드 작성해서 맞추긴 했지만, BFS로 해결해야 함을 알아채는 것이 관건이었다.

알고리즘은 다음과 같다.

네 자리 중 한 자리씩 0부터 9까지 바꿔가는 문제로, 구현은 대략 5분 쯤 걸린 것 같다..

네 자리 중 한 자리를 바꿨을 때 수를 k라고 한다면 k가

(1) 1000 이상

(2) 소수

(3) 아직 큐에 추가되지(방문하지) 않은 수

위의 세 조건을 모두 만족하면 큐에 추가한다.

구현 과정에서 약간의 실수가 있었는데,

수를 0에서 9까지 바꿔서 판별한 후 다음 자릿수로 넘어가기 전에 바뀐 수를 다시 원래대로 복구해둬야 한다.

그렇지 않으면 한 턴에 한 자리가 아니라 여러 자리가 바뀌어 버리므로 원하는 결과를 얻을 수 없다.

코드

#include <iostream>
#include <queue>
using namespace std;

int t, a, b, tmp[4];
bool prime[10001] = { 1,1 };    // 소수면 0, 소수가 아니면 1

int toInt(int* ary) {
    int res = 0;

    for (int i = 0, m = 1000; i < 4; i++, m /= 10) {
        res += ary[i] * m;
    }
    return res;
}

int bfs() {
    bool visit[10000] = {};

    queue<pair<int, int>> q;

    visit[a] = 1;
    q.push({ a,0 });

    while (!q.empty()) {
        int p = q.front().first, cnt = q.front().second;
        q.pop();

        if (p == b) return cnt;

        for (int i = 0, m = 1000; i < 4; i++, m /= 10) {
            tmp[i] = p / m;
            p %= m;
        }

        for (int i = 0; i < 4; i++) {
            int origin = tmp[i];		// 원래 값 기억

            for (int j = 0; j < 10; j++) {
                tmp[i] = j;
                int k = toInt(tmp);

                if (k >= 1000 && !prime[k] && !visit[k]) {
                    q.push({ k, cnt + 1 });
                    visit[k] = 1;
                }
            }

            tmp[i] = origin;	// 해당 자릿수 반복 끝나면 원상태로 복구
        }
    }

    return -1;
}

int main() {

    for (int i = 2; i * i < 10000; i++)
        for (int j = 2 * i; j <= 10000; j += i) {
            if (prime[i]) break;
            prime[j] = 1;
        }
    
    cin >> t;
    
    while (t--) {
        cin >> a >> b;

        int ans = bfs();

        if (ans < 0) cout << "Impossible" << '\n';
        else cout << ans << '\n';

    }  
}

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

 

문제 해결

매우 간단한 그리디 알고리즘이다.

현재 리터당 가격보다 저렴한 지역을 도착했을 때 해당 지역의 리터당 가격으로 주유한다.

위 과정을 종점까지 반복한다.

코드

#include <iostream>
using namespace std;

long long sum, n, mp = 1e9, price[100001], dist[100001];

int main() {
    cin >> n;

    for (int i = 1; i <= n - 1; i++) scanf("%lld", dist + i);
    for (int i = 1; i <= n; i++) scanf("%lld", price + i);

    for (int i = 1; i <= n - 1; i++) {
        if (price[i] < mp) mp = price[i];
        sum += dist[i] * mp;
    }
    cout << sum;
}