Sevity Blog

인풋파싱

아래는 4개 숫자를 stdin에서 읽어오는 코드

import sys
input = sys.stdin.readline

# 입력 받기: H, W, N, M
H, W, N, M = map(int, input().split())

숫자하나 + 문자열리스트

3
MBC
KBS1
KBS2

인풋이 위와 같을때

import sys
input = sys.stdin.readline

# 채널의 수 N을 입력받음
N = int(input().strip())

# N개의 채널 이름을 리스트로 입력받음
channels = [input().strip() for _ in range(N)]

기본문법

기본 for루프

for y in range(H):

N+1개씩 건너뛰기

for y in range(0, H, N+1):  # 행을 N+1씩 건너뛰며 반복

주의사항들

재귀관련해서 메모아이제이션과 호출깊이가 깊을때 조정코드(N=1000이라도 아래코드 필요)

import sys
sys.setrecursionlimit(10**6)  #여기1

from functools import lru_cache
input = sys.stdin.readline

N = int(input().strip())

@lru_cache(maxsize=None) #여기2
def go(remain):
    if remain == 0:
        return False
    if not go(remain-1):
        return True
    if remain >=3 and not go(remain-3):
        return True
    return False
    
print("SK" if go(N) else "CY")

단순구현부터 해봤는데 역시 TLE난다.

#include <string>
#include <vector>

using namespace std;
typedef long long ll;

// 뭐지 단순 구현문제인가.. long long이라 아닐거 같기도 하고 흠..
long long solution(int _k, int _d) {
    ll k=_k,d=_d;
    ll answer = 0;
    //일단 단순 구현해보자.
    for(ll a=0;a<1000000;a++)for(ll b=0;b<1000000;b++){
        if(k*k*a*a+k*k*b*b<=d*d) {
            //printf("(%d,%d),", a*k,b*k);
            answer++;
        }
        else break;
    }
    return answer;
}

#include <string>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

// 뭐지 단순 구현문제인가.. long long이라 아닐거 같기도 하고 흠..
long long solution(int _k, int _d) {
    ll k=_k,d=_d;
    ll answer = 0;
    //일단 단순 구현해보자.
    for(ll a=0;a<1000000;a++) {
        ll s = d*d-a*a*k*k;
        if(s<0) continue;
        double bb = sqrt((double)s)/(double)k;
        //if(bb<0) continue;
        //printf("%lld\n", bb);
        answer+=bb+1;
    }
    return answer;
}

이건 일부 케이스WA나네..

#include <string>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

long long solution(int _k, int _d) {
    ll k=_k,d=_d;
    ll answer = 0;
    for(ll a=0;a<=1000000;a++) {
        ll s = d*d-a*a*k*k;
        if(s<0) break;
        ll bb = sqrt(s)/k;
        answer+=bb+1;
    }
    return answer;
}

뭐지? 1000000포함안시킨거랑 double연산 때문에 WA났던거네?

double연산시 오류나는건 좀 그렇네.. 흠..

아이디어 자체는 chatGPT랑 동일하다.

#include <string>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

long long solution(int _k, int _d) {
    ll k=_k,d=_d;
    ll answer = 0;
    for(ll a=0;a<=1000000;a++) {
        ll s = d*d-a*a*k*k;
        if(s<0) break;
        double bb = (double)sqrt(s)/k;
        answer+=(ll)(bb+1e-9)+1;
    }
    return answer;
}

double은 위처럼 하면 되는거 보니, 형변환시 문제인거 같다. 2.0이 1.999로 되는등..

으허.. 머리에 쥐나긴했는데.. chatGPT한테 힌트 받고 스스로 풀긴했다 ㄷ

재귀를 통해서 하는건데.. 알아두면 두고두고 써먹을거 같긴하다.

#include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;

ll length[21];
ll val[21];//val[3]이면 F(3)일때 1의 개수

ll solution_sub(int n, ll l, ll r) {
    if (n <= 0) return 1;
    ll answer = 0;
    if (n == 1) {
        for (int i = l; i <= r; i++) {
            if (i != 3) answer += 1;
        }
        return answer;
    }

    //n에 대해서 5등분 해서 재귀로 들어가면 되지 않을까?
    ll lx = (l - 1) / length[n - 1] + 1;
    ll rx = (r - 1) / length[n - 1] + 1;

    ll nl = l - length[n - 1] * ((l - 1) / length[n - 1]);
    ll nr = r - length[n - 1] * ((r - 1) / length[n - 1]);


    if (lx == rx) {
        if(lx!=3) answer += solution_sub(n - 1, nl, nr);
    } else {
        //왼쪽

        //answer += solution_sub(n - 1, l - length[n-1]*((l-1)/length[n-1]), r - length[n - 1] * ((r - 1) / length[n - 1]));
        ll nl = l - length[n - 1] * ((l - 1) / length[n - 1]);
        ll nr = r - length[n - 1] * ((r - 1) / length[n - 1]);
        ll a = ((l - 1) / length[n - 1] + 1) * length[n - 1];
        ll rv = nr; if (r > a) rv = length[n - 1];
        if(lx!=3) answer += solution_sub(n - 1, nl, rv);

        //오른쪽
        a = ((r - 1) / length[n - 1]) * length[n - 1];
        ll lv = nl; if (l < a) lv = 1;
        if(rx!=3) answer += solution_sub(n - 1, lv, nr);

        //중간
        for (int i = lx + 1; i < rx; i++) {
            if (i != 3) answer += val[n - 1];
        }

    }
    return answer;
}


ll solution(int n, ll l, ll r) {
    length[1] = 5; for (int i = 2; i <= 21; i++) length[i] = length[i - 1] * 5;
    val[1] = 4; for (int i = 2; i <= 21; i++) val[i] = val[i - 1] * 4;

    return solution_sub(n, l, r);
}

int main() {
    cout << solution(3, 35, 102) << endl;
    // 예시 입력: n = 2, l = 4, r = 17 → 결과는 8이어야 함
    cout << solution(2, 4, 17) << endl;

    return 0;
}

초기구현.. 거의 한번에 AC받긴함

Competitive Progrmming Helper의 약자로 백준같은 사이트에서 testcase같은걸 긁어다가 vscode에서 할 수 있게 해준다.

chrome에서도 확장프로그램을 설치해야하고(Competitive Companion)

vscode에서도 확장을 설치해야한다(Competitive Programming Helper)

원격ssh로 실행하는 경우는 포트전달이 필요할수도 있다.

문제에서 double을 다뤄야 하면, 주의해야할 점들이 있어서 나열해 본다.

이 문제를 보자.

먼저, double을 int로 변환해야하는 경우 단순한 형변환으로는 부족할 수 있다.

예를 들어 다음코드를 돌려보면 1004가 아닌 1003이 찍힌다.

이경우 다음처럼 뒤에 0.5를 곱해주고 변환해야 제대로 변환된다.

아래처럼 rint를 쓰면 가까운 int로 변환해서 해당문제가 없어진다고 한다.

double a = 10.04 * 100;
int b = (int) rint(a);
printf("%d\n", b);

풀이과정

출발점은 하나로 정해져 있고, 도착점은 여러개.

현금인출은 사이클 도는게 유리하므로 SCC단위로 생각하면 됨.

도착점도 SCC단위로 묶어서 생각하면 됨.

SCC단위로 묶고나서 보면, 간선 가중치는 없는 방향그래프 이므로, 위상정렬 개념 도입해서 longest 구하면 답

(여기서 위상정렬이 아닌 단순 BFS로는 안풀린다. 그래프 최장거리 참조)

헷갈렸던 점

아래 그래프가 SCC이후에 만들어진 DAG이라고 해보자. 

1번정점이 시작, 5번 정점이 끝이라고 해보자.

위의 그래프를 아래와 같은 코드로 위상정렬하면서 돌리게 되면

1번노드를 처리한다음에 2번 노드처리하기전에 while()이 끝나게 된다. (2번 노드의 in_edge가 3이라서 1빼도 아직 2라서 3과 4를 처리하기 전까진 못들어가는데 3,4를 처리하지 않는 코드이다.)

하지만 정답은 1 -> 2 -> 3을 모두 계산한 최대비용이 답이었던것.. 

따라서, 아래처럼 처음에 indegree가 0인 모든 정점을 queue에 넣어주고, cal[v] 맵을 사용해서 유효한 경우에만 max_dist가 갱신되도록 해주면 OK

코드

scc_dag_kosaraju()를 라이브러리화 하고, 기존 longest()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

문제는 여기

특정간선을 포함하는경우, 실제 MST보다 큰 값이 나올 수 있다. (프루스칼로 MST를 구할때는 간선을 정렬한다음에 최소간선부터 시작함을 상기하자)

MST 한 번 하는데 $O(E \times log E)$ 니까, 간선개수만큼 하면 $O(E^2 \times log E)$ 일거고.. E가 10^5보다 크므로 나이브하게 해서는 TLE확정이다.

풀이방법

MST를 구한다음에.. 해당 간선이 이미 포함돼 있으면 MST값을 그냥 찍으면 되고, 만약 포함되어 있지 않으면 포함시키고, 다른 간선중 하나를 빼는식으로 하면 된다.

잘 이해가 가지 않는다면 다음 그래프를 보자. (간선 가중치는 생략돼 있지만 MST를 그린 화면으로 생각하자)

위 그림에서 알 수 있듯이 MST에 (1,4)간선을 추가한 순간 사이클이 생기기 때문에, (1,6) (6,2) (2,5) (5,3) (3,4) 중 하나를 대신 끊어줘야 한다.

이때 나이브하게 경로를 쭉 따라가면서 가중치 가장 큰 걸 빼주는 식으로 하면, 그래프 구조가 직선적인 경우 O(E)가 걸리게 되어 E개의 쿼리를 처리하는데 O(E^2)이 걸려서 TLE가 나게된다.

따라서 위에 LCA로 표시했지만 공통조상까지 올라가고, 내려오는 경로상에서 스파스 테이블을 사용해서 효율적으로 최대가중치를 가진간선을 골라줘야 한다. 참고로 LCA에서 최대가중치 간선을 고르는 문제는 여기에 있다.

코드

Binary Search Tree 구현을 해보았다. 

트리 만드는 부분 까지만 되어 있다.

지금은 root부터 insert로 트리를 생성하게 되어 있는데, 첨에는 다르게 해보다가 엄청 고생함.

최적화 된 형태는 아니기 때문에 향후에 업데이트 될 가능성은 크다.

인접리스트로만 구현하려고도 해봤는데, left, right가 [0], [1]로 되어야 해서 좀 어색하고,

특히 parent처리하려면 별도 배열을 쓰거나 node안에 w옆에 넣어야 하는데 좀 어색함

이걸로 post_order로 순회하는 것까지 구현한게 아래 코드이고, 이 문제에 대한 답안이기도 하다.

그래프 문제를 풀때 인접행렬, 인접리스트를 다룰일이 워낙 많아서 별도 글로 하나 정리해 둔다.

인접행렬보다는 인접리스트로 구현하는게 일반적으로 더 나은데, 간선수가 최대일 경우 정점의 개수 제곱정도 되는데 인접행렬로 구현하게 되면 항상 이정도 복잡도를 가지는 반면 인접리스트로 구현하면 간선이 드물수록 속도 업이 된다. (예를 들어 그래프가 트리인 경우 최대 간선수는 정점의 제곱이 아닌 정점의 개수-1개 정도로 줄어든다.)

그래서 인접리스트 구현을 먼저 실어두고 나중에 PS할때 이용하려고 한다.

인접리스트 간선가중치 없는 경우

인접리스트 간선가중치 있는 경우

w=1로 놓으면 간선가중치 없는 경우에도 범용적으로 쓸수 있기는 한데.. 무거울듯?

인접행렬 간선가중치 있는 경우

간선가중치 없는 경우는 단순하게 w대신 1을 넣어주면 되기 때문에 트리비얼하다.

just store Lunlun numbers in an array.좋은 문제를 발견하면, 그 문제의 뽕을 뽑아먹는(충분히 검토하는) 코뽕시간입니다 ㅎ

오늘의 코뽕문제는 AtCoder Beginner Contest 161 - D Lunlun Number가 되겠습니다.

이 문제는 설명이 단순하고 쉽기 때문에 나중에 다시 문제를 recall하기도 좋고 풀이도 다양해서 코뽕에 아주 적합한 문제가 되겠습니다.

참고로 이 Lunlun number는 OEIS에 등록되어 있습니다.

이문제는 대략 살펴보아도 

브루트포스, 백트래킹, 이진탐색, Queue 등을 이용해서 풀 수 있는걸로 보입니다.

브루트 포스를 이용한 방법

먼저 브루트포스를 이용한 방법은, 단순히 1씩 증가시키면서 lunlun 넘버인지 보는코드에다가 일정부분을 스킵할 수 있는 코드를 삽입하는 간단한 방법입니다. 샘플코드는 다음과 같습니다.

예들들어 현재 숫자가 243일때 2가 violation이므로 둘째자리 숫자인 4가 9가 될때까지 50을 더해서 293까지 skip한다는 idea. 

이정도 아이디어만 가지고도 AC를 받기에는 충분(대략 700ms정도 걸림)

다른 아이디어도 적용하면 좀 더 스킵할수도 있을것임

아래는 다른사람들 방법

just store Lunlun numbers in an array.

근데 이건 원리상 아래 BFS랑 동일한거 같다.

백트래킹을 이용한 방법

678이라는 임의의 Lunlun넘버를 생각해 봤을때, 다음처럼 3가지 경우로 갈 수 있다고 생각하고, DFS를 돌리는 아이디어.

이건 실전에서 구현하기도 좋아보인다. 

특별히 백트래킹이랄것도 없고.. 그냥 최대숫자보다 커지면 return하는게 다인데.. 저 최대숫자를 모르면 좀 애매하다는게 문제라면 문제.. DFS특성상 11111111111111 이런숫자를 먼저 최대자리수까지 파는 경향이 있기 때문에 더욱그렇다.

BFS를 이용한 방법

에디토리얼에서도 이걸 정해로 주장하고 있다.

뭐 기본적으로 DFS와 동일한 아이디어 인데, 최대숫자를 guessing할 필요가 없고 그냥, 값이 채워진게 10만번째이면 바로 break하면 되기 때문에 좀 더 안전성이 있다. 부채모양으로 퍼져나가니 찾자마자 최단거리가 되는 원리랑 조금 비슷한게 담긴거 같다.

실전에서는 이코드처럼 정확히 10만에서 break하면 좀 위험할수도 있으니, 좀더 버퍼를 주는게 좋겠지만, 어쨌든 DFS보다는 나은 어프로치인듯하다.

덕북에 실행속도와 메모리 사용량에 있어서도 3배정도는 이득이 있는듯?

아래는 다른사람들 BFS구현

https://atcoder.jp/contests/abc161/submissions/11513177

https://atcoder.jp/contests/abc161/submissions/11518213

이진탐색을 이용한 방법

이진탐색+DigitDP 솔루션 : https://atcoder.jp/contests/abc161/submissions/11532810

이건 오버 엔지니어링 같아서 보기가 좀 싫어지네 ㅎ 나중에 보자.