Sevity Blog

알고리즘 문제 풀이에서 Python 입력 파싱은 sys.stdin.readline, split, map, 리스트 컴프리헨션을 조합해 빠르게 처리합니다.

숫자 여러 개를 한 줄에서 읽는 경우, 문자열 여러 줄을 리스트로 받는 경우, 재귀 풀이에서 호출 깊이를 늘리는 경우를 구분해 기본 템플릿을 준비해 두면 편합니다.

핵심 정리

Python으로 PS 문제를 풀 때는 input을 sys.stdin.readline으로 바꿔 입력 속도를 안정적으로 확보하는 경우가 많습니다. 한 줄의 숫자 여러 개는 split 뒤 map으로 정수 변환하고, 여러 줄 문자열은 반복문이나 리스트 컴프리헨션으로 모읍니다. 재귀와 메모이제이션을 쓰는 문제에서는 recursionlimit과 lru_cache 설정도 함께 확인해야 합니다.

• sys.stdin.readline은 많은 입력을 받을 때 기본 input보다 안정적인 선택이 될 수 있습니다.
• 한 줄 숫자 여러 개는 map과 split으로 정수 변수에 나눠 담습니다.
• 여러 줄 문자열은 strip을 사용해 줄 끝 개행을 제거한 뒤 리스트에 저장합니다.
• range의 세 번째 인자를 쓰면 일정 간격으로 반복할 수 있습니다.
• 재귀 깊이가 커질 수 있으면 sys.setrecursionlimit을 먼저 조정합니다.
• 중복 부분 문제가 있으면 functools.lru_cache로 메모이제이션을 붙일 수 있습니다.

입력 파싱 템플릿은 문제마다 조금씩 바뀝니다. 한 줄인지 여러 줄인지, 숫자인지 문자열인지, 공백을 보존해야 하는지부터 확인하면 불필요한 디버깅을 줄일 수 있습니다.

이어서 볼 글

• python array (indexing and slicing) - 입력값을 리스트로 만든 뒤 인덱싱과 슬라이싱으로 다루는 흐름이 이어진다.
• python numpy - 파싱한 숫자 데이터를 NumPy 배열로 넘겨 처리하는 다음 단계 글이다.

인풋파싱

아래는 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")

프로그래머스 점 찍기는 k 간격의 격자점 중 원 안에 들어가는 점의 개수를 세는 문제입니다.

모든 x, y 조합을 이중 반복으로 확인하면 느리므로, x를 하나 정한 뒤 가능한 최대 y를 제곱근으로 구해 한 줄씩 개수를 더하는 방식이 핵심입니다.

핵심 정리

점의 좌표가 k의 배수이므로 x를 k 단위로 늘려가며 원 안에 남아 있는 y의 최대값을 계산하면 됩니다. x가 커질수록 남은 반지름 제곱이 작아지고, 음수가 되는 순간 더 볼 필요가 없습니다. 가능한 y 개수는 0부터 최대 y까지 포함하므로 하나를 더해 더합니다. 부동소수점 계산은 경계값에서 오차가 생길 수 있어, 정수 계산을 우선하고 double을 쓰더라도 작은 보정값을 두어 WA를 피해야 합니다.

• 단순 이중 반복은 좌표 범위가 커질 때 시간 초과가 나기 쉽습니다.
• x를 고정하면 가능한 y의 최대값을 원의 식에서 구할 수 있습니다.
• 남은 값이 음수가 되면 더 큰 x는 볼 필요가 없습니다.
• y가 0인 점도 포함되므로 개수를 더할 때 하나를 더합니다.
• 제곱 계산은 long long 범위로 처리해야 overflow 위험을 줄일 수 있습니다.
• sqrt 결과를 정수로 바꿀 때 경계 오차가 WA 원인이 될 수 있습니다.

원문은 TLE, WA를 겪은 코드 흐름이 잘 남아 있지만 왜 개선되는지 설명이 부족했습니다. 이번 보강은 이중 반복에서 한 축 반복으로 줄어드는 이유와 sqrt 경계 오차를 먼저 드러냈습니다.

이어서 볼 글

• C++ double 반올림과 int 변환: 오차 처리 방법 - sqrt 결과를 정수로 바꿀 때 생기는 부동소수점 경계 오차를 설명한다.

단순구현부터 해봤는데 역시 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로 되는등..

유사 칸토어 비트열 문제는 전체 문자열을 실제로 만들지 않고, 5등분 구조를 따라 필요한 구간만 재귀로 내려가며 1의 개수를 세는 방식으로 풀 수 있습니다.

가운데 세 번째 구간은 항상 0이 되는 구조라서, l부터 r까지의 범위가 어느 5등분 구간에 걸치는지만 계산하면 불필요한 문자열 생성과 순회를 피할 수 있습니다.

핵심 정리

핵심은 n단계 비트열의 길이와 1의 개수를 미리 알아두는 것입니다. 길이는 단계마다 5배가 되고, 1의 개수는 가운데 구간을 제외하므로 4배가 됩니다. 현재 범위가 한 구간 안에 있으면 그 하위 단계로 그대로 내려가고, 여러 구간에 걸치면 왼쪽 끝, 오른쪽 끝, 중간의 완전한 구간을 나누어 더합니다. 중간 구간 중 세 번째는 0 구간이므로 합산하지 않습니다.

• 전체 비트열을 문자열로 만들면 길이가 급격히 커져 비효율적입니다.
• 각 단계는 이전 단계 5개 구간으로 나뉩니다.
• 세 번째 구간은 0으로 취급해 재귀 탐색에서 제외합니다.
• length 배열은 단계별 전체 길이를 저장합니다.
• val 배열은 단계별 1의 개수를 저장합니다.
• 범위가 여러 구간에 걸치면 왼쪽, 중간, 오른쪽을 나눠 계산합니다.

원문은 코드가 바로 시작되어 구간 분할 의도가 늦게 보였습니다. 이번 보강은 5등분 구조와 세 번째 구간 제외 규칙을 먼저 설명해, 아래 재귀 코드의 변수들이 어떤 역할인지 따라가기 쉽게 했습니다.

으허.. 머리에 쥐나긴했는데.. 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 Programming Helper, CPH는 VS Code 안에서 알고리즘 문제의 샘플 입력과 출력을 실행하고 판정하는 확장입니다.

브라우저의 Competitive Companion이 온라인 저지 문제를 읽어 로컬 도구로 보내고, VS Code의 CPH가 그 데이터를 받아 테스트케이스 실행 환경을 만드는 흐름으로 이해하면 됩니다.

핵심 정리

CPH 설정은 VS Code 확장 하나만 설치하는 작업처럼 보이지만, 실제로는 브라우저 확장과 VS Code 확장이 함께 동작하는 구조입니다. 문제 페이지에서는 Competitive Companion이 샘플 입력, 출력, 문제 정보를 파싱해 로컬 포트로 전송하고, VS Code에서는 CPH가 이 데이터를 받아 문제 파일과 테스트케이스를 관리합니다. 원격 SSH 개발 환경에서 실행한다면 브라우저는 로컬에 있고 VS Code 서버는 원격에 있을 수 있으므로 포트 전달 여부를 따로 확인해야 합니다.

• CPH는 Competitive Programming Helper의 약자로, VS Code에서 컴파일, 실행, 샘플 테스트 판정을 돕습니다.
• Competitive Companion은 Codeforces, AtCoder 같은 문제 페이지에서 샘플 테스트를 추출해 외부 도구로 전달하는 브라우저 확장입니다.
• 두 확장을 함께 써야 문제 페이지에서 누른 동작이 VS Code의 문제 파일 생성으로 이어집니다.
• 원격 SSH 환경에서는 Companion이 보내는 로컬 포트가 원격 VS Code 쪽으로 연결되는지 확인해야 합니다.
• 포트 전달이 막혀 있으면 확장은 설치되어 있어도 테스트케이스가 VS Code로 들어오지 않습니다.
• 문제가 들어오지 않을 때는 브라우저 확장 권한, CPH 실행 상태, 포트 포워딩을 순서대로 보는 것이 빠릅니다.

원문은 CPH, Competitive Companion, VS Code 확장, 원격 SSH 포트 전달 메모가 한 줄로 이어진 글이었습니다. 보강 블록은 설치 목록보다 데이터가 이동하는 흐름과 문제 발생 지점을 먼저 보이게 정리했습니다.

이어서 볼 글

• VS Code C++ 설정: tasks.json과 launch.json 빌드 디버깅 - CPH가 테스트케이스를 받아도 C++ 컴파일과 실행 설정이 맞아야 실제 풀이에 쓸 수 있다.
• Codeforces C++ 헬퍼 VsCaide: Visual Studio 설치와 용도 - 같은 온라인 저지 테스트 실행 자동화를 Visual Studio 환경에서 다룬 글이다.

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

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

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

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

C++에서 double 값을 int로 바꿀 때는 부동소수점 오차 때문에 기대한 값보다 1 작게 잘리는 경우가 있습니다.

예를 들어 10.04에 100을 곱한 값이 내부적으로 정확히 1004가 아니라 1003.999처럼 표현되면, 단순 형변환은 소수점을 버려 1003이 될 수 있습니다.

핵심 정리

double을 int로 변환할 때 단순 캐스팅은 반올림이 아니라 버림에 가깝게 동작합니다. 그래서 소수 계산 결과를 정수로 바꿔야 한다면 0.5를 더한 뒤 변환하거나, 가까운 정수로 반올림하는 함수를 사용하는 편이 안전합니다. 알고리즘 문제에서는 돈, 좌표, 백분율처럼 소수 계산 뒤 정수 출력이 필요한 경우 이 문제가 자주 드러납니다.

• double은 많은 십진 소수를 정확히 표현하지 못합니다.
• 계산 결과가 화면에는 1004처럼 보여도 내부 값은 조금 작을 수 있습니다.
• int로 단순 변환하면 소수점 아래가 버려져 예상보다 작은 값이 나올 수 있습니다.
• 양수 반올림이 목적이라면 0.5를 더한 뒤 정수로 바꾸는 방식이 쓰입니다.
• 가까운 정수 변환에는 rint 같은 반올림 함수를 사용할 수 있습니다.
• 문제 조건에 따라 반올림, 올림, 내림 중 무엇이 필요한지 먼저 확인해야 합니다.

double 문제는 코드가 틀린 것처럼 보이지 않아 더 찾기 어렵습니다. 소수 계산 뒤 정수로 바꾸는 부분이 있다면 출력 직전 값과 변환 방식을 함께 확인하는 습관이 좋습니다.

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

이 문제를 보자.

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

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

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

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

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

백준 ATM 문제는 사이클 안의 금액을 모두 모을 수 있다는 점 때문에 SCC 압축 후 DAG 최장 경로로 바꿔 풀 수 있습니다.

출발점에서 도달 가능한 SCC만 유효하게 보고, 레스토랑이 포함된 SCC까지의 최대 누적 금액을 계산해야 하므로 단순 BFS가 아니라 위상정렬 기반 DP가 필요합니다.

핵심 정리

ATM 문제의 첫 단계는 방향 그래프의 사이클을 SCC로 묶는 것입니다. SCC 내부에서는 서로 이동 가능하므로 해당 컴포넌트 안의 ATM 금액을 모두 합쳐 하나의 노드 값으로 볼 수 있습니다. 그 다음 SCC 사이의 간선으로 압축 그래프를 만들면 DAG가 되고, 출발 SCC에서 도달 가능한 컴포넌트만 대상으로 누적 금액의 최댓값을 갱신합니다. 최종 답은 레스토랑이 포함된 SCC들 중 도달 가능하면서 누적 금액이 가장 큰 값입니다.

• 사이클 안에서는 정점들을 반복해서 오갈 수 있으므로 SCC 단위로 묶습니다.
• 각 SCC의 ATM 금액은 컴포넌트 내부 정점 금액의 합입니다.
• SCC 사이의 간선을 모으면 압축 DAG를 만들 수 있습니다.
• 출발 정점이 속한 SCC에서 도달 가능한 컴포넌트만 계산 대상입니다.
• DAG 위에서는 위상정렬 순서로 DP 값을 전파할 수 있습니다.
• 레스토랑 정점도 SCC 단위로 표시해야 합니다.
• 답은 도달 가능한 레스토랑 SCC 중 최대 누적 금액입니다.
• 도달 불가능한 SCC를 섞으면 잘못된 경로가 답에 포함될 수 있습니다.

원문은 SCC 압축 이후 DAG 최장 경로 코드로 이어지므로, 문제를 SCC, 압축 그래프, 도달 가능성, DP 전파, 레스토랑 후보 선택 순서로 다시 정리했습니다. 이 순서를 놓치면 그래프는 맞게 압축해도 출발점과 무관한 컴포넌트가 계산에 섞일 수 있습니다.

이어서 볼 글

• SCC 강한 연결 요소: Kosaraju와 Tarjan 알고리즘 - 문제 풀이에서 먼저 수행하는 SCC 압축의 기본 개념이다.
• 그래프 최장거리 풀이: 트리 지름과 DAG 최장 경로 - SCC 압축 후 DAG 위에서 최장 경로 DP를 계산하는 배경이다.

풀이과정

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

현금인출은 사이클 도는게 유리하므로 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()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

백준 15481 그래프와 MST는 각 간선을 반드시 포함한다고 가정했을 때의 최소 신장 트리 비용을 빠르게 구하는 문제입니다.

모든 간선마다 Kruskal을 다시 돌리면 느리므로, MST를 한 번 만든 뒤 비트리 간선을 추가했을 때 생기는 사이클에서 최대 간선을 빼는 방식으로 계산해야 합니다.

핵심 정리

이 문제의 핵심은 기본 MST 비용과 대체 간선 비용을 분리해서 보는 것입니다. 먼저 Kruskal로 MST를 만들고 전체 비용을 구합니다. 이미 MST에 포함된 간선은 답이 기본 MST 비용입니다. MST에 없는 간선을 하나 추가하면 두 정점 사이의 MST 경로와 새 간선이 사이클을 만들고, 그 사이클에서 가장 무거운 간선을 제거해야 비용이 최소가 됩니다. 따라서 두 정점 사이 경로의 최대 간선 가중치를 빠르게 찾기 위해 LCA와 sparse table을 사용합니다.

• 먼저 Kruskal로 기본 MST와 총 비용을 구합니다.
• MST에 포함된 간선의 답은 기본 MST 비용입니다.
• MST에 없는 간선을 추가하면 트리에 사이클이 하나 생깁니다.
• 사이클 안에서 가장 무거운 간선을 빼야 새 MST 후보 비용이 최소가 됩니다.
• 필요한 값은 MST 위에서 두 정점 사이 경로의 최대 간선 가중치입니다.
• LCA sparse table에 조상 정보와 경로 최대 간선 정보를 함께 저장합니다.
• 각 비트리 간선마다 기본 비용에 새 간선 비용을 더하고 경로 최대값을 빼서 답을 구합니다.
• 간선이 MST에 들어갔는지 표시해 두어야 각 간선의 답을 올바르게 나눌 수 있습니다.

원문은 MST와 LCA를 결합하는 풀이로 이어지므로, 왜 LCA가 필요한지 먼저 설명했습니다. 이 문제는 MST를 여러 번 만드는 문제가 아니라 한 번 만든 MST 위에서 경로 최대 간선을 빠르게 묻는 문제로 바꾸는 것이 핵심입니다.

이어서 볼 글

• 최소신장트리 MST: Kruskal, Prim, Union-Find - 문제 풀이의 출발점인 MST와 Kruskal 배경이다.
• LCA 공통조상 알고리즘: depth, parent, binary lifting - MST 위 두 정점 경로를 처리할 때 필요한 LCA 기본 개념이다.
• Sparse Table과 Binary Lifting: LCA와 경로 쿼리 - 경로 최대 간선을 빠르게 묻기 위한 sparse table 응용이다.

문제는 여기

특정간선을 포함하는경우, 실제 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에서 최대가중치 간선을 고르는 문제는 여기에 있다.

코드

BST는 왼쪽 서브트리에는 작은 값, 오른쪽 서브트리에는 큰 값을 두는 이진 탐색 트리 구조다.

insert 과정은 루트부터 값을 비교하며 내려가는 반복이고, postorder 순회는 왼쪽, 오른쪽, 현재 노드 순서로 방문한다.

핵심 정리

BST 구현을 볼 때는 배열에서 하는 이진탐색과 달리 비교 결과에 따라 트리의 왼쪽 또는 오른쪽 자식으로 내려간다는 점을 잡아야 한다. 삽입 순서에 따라 트리 모양이 달라질 수 있고, 한쪽으로 치우치면 탐색 성능도 나빠질 수 있다.

• BST에서는 현재 노드보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 보낸다.
• insert는 루트부터 값을 비교하며 빈 자리를 찾을 때까지 내려간다.
• postorder 순회는 왼쪽 서브트리, 오른쪽 서브트리, 현재 노드 순서로 방문한다.
• 입력 순서가 정렬되어 있으면 트리가 한쪽으로 치우칠 수 있다.
• 균형이 무너지면 평균적으로 기대하는 탐색 성능이 나오지 않을 수 있다.

BST는 이진탐색의 비교 아이디어를 트리 구조로 옮긴 자료구조로 보면 이해하기 쉽다. 다만 배열 이진탐색처럼 항상 균등하게 반씩 줄어드는 것은 아니다.

이어서 볼 글

• 이진탐색 Binary Search: lower_bound와 경계 찾기 - 값 비교로 탐색 범위를 좁히는 기본 아이디어를 설명한다.
• DFS 깊이 우선 탐색 개념과 시간복잡도 - 트리의 전위, 중위, 후위 순회는 DFS 계열 순회로 이해할 수 있다.
• 인접행렬과 인접리스트 차이: 그래프 저장 방식 - 트리와 그래프를 저장하고 순회하는 구조적 배경을 함께 볼 수 있다.

Binary Search Tree 구현을 해보았다. 

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

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

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

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

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

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

그래프를 저장할 때 인접행렬은 정점 간 연결 여부를 표처럼 저장하고, 인접리스트는 각 정점의 이웃 목록을 저장한다.

두 방식은 같은 그래프를 표현하지만 메모리 사용량, 간선 존재 확인 속도, 전체 이웃 순회 비용이 다르므로 문제 조건에 맞춰 골라야 한다.

핵심 정리

인접행렬은 두 정점 사이의 간선 존재 여부를 빠르게 확인하기 좋지만 정점 수가 커지면 메모리를 많이 쓴다. 인접리스트는 실제 연결된 간선만 저장하므로 희소 그래프에서 효율적이고, BFS나 DFS처럼 이웃을 순회하는 문제에서 자주 쓰인다.

• 인접행렬은 정점 수의 제곱 크기 표를 사용해 연결 여부를 저장한다.
• 인접리스트는 각 정점마다 연결된 이웃 정점 목록을 저장한다.
• 간선 존재 여부를 자주 묻는 문제는 인접행렬이 단순할 수 있다.
• 정점은 많고 간선은 적은 그래프는 인접리스트가 메모리 면에서 유리하다.
• BFS와 DFS 구현에서는 보통 현재 정점의 이웃을 순회하므로 인접리스트가 자연스럽다.

그래프 문제를 풀 때는 탐색 알고리즘보다 먼저 정점 수, 간선 수, 간선 존재 질의 여부를 보고 저장 방식을 정하는 편이 좋다.

이어서 볼 글

• BFS 알고리즘: 큐, 방문 처리, 최단거리 구현 - 인접리스트나 인접행렬 위에서 이웃 정점을 순회하는 대표 알고리즘이다.
• DFS 깊이 우선 탐색 개념과 시간복잡도 - 그래프 저장 방식에 따라 DFS의 이웃 순회 비용이 달라진다.
• 그래프 최장거리 풀이: 트리 지름과 DAG 최장 경로 - 그래프 경로 문제를 풀 때 저장 방식이 구현의 출발점이 된다.

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

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

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

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

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

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

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

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

AtCoder ABC161 D Lunlun Number 문제는 인접한 두 자리의 차이가 1 이하인 수를 작은 순서대로 만들고 K번째 값을 찾는 구현 문제입니다.

이 메모는 단순 증가 검사, DFS 백트래킹, BFS 큐 생성 방식이 이 문제에서 어떻게 연결되는지 정리합니다.

핵심 정리

Lunlun Number는 각 자리의 이웃한 숫자 차이가 1 이하인 수입니다. 작은 수부터 차례로 검사하면서 조건을 만족하는 수만 세는 방법도 가능하지만, K가 커질수록 불필요한 수를 많이 보게 됩니다. 더 자연스러운 풀이는 한 자리 수 1부터 9를 시작점으로 두고, 마지막 자리 숫자에서 하나 작거나 같거나 하나 큰 숫자만 뒤에 붙여 후보를 만드는 방식입니다. 이렇게 만들면 조건을 깨는 수를 애초에 만들지 않기 때문에 풀이가 단순해집니다.

• 브루트포스는 숫자를 하나씩 늘리며 Lunlun 조건을 검사하는 가장 직접적인 방법입니다.
• 검사 중 조건을 깨는 자리수를 발견하면 다음 후보로 건너뛰는 최적화를 넣을 수 있습니다.
• DFS 백트래킹은 가능한 다음 자리만 붙여 Lunlun 후보를 재귀적으로 만듭니다.
• BFS는 큐에 1부터 9를 넣고 앞에서 꺼낸 수의 마지막 자리 기준으로 다음 후보를 붙입니다.
• BFS 방식은 작은 수부터 후보가 나오기 쉬워 K번째 값을 찾는 문제와 잘 맞습니다.
• 이 문제의 핵심은 모든 수를 훑는 것이 아니라 조건을 만족하는 수만 생성하는 쪽으로 생각을 바꾸는 것입니다.

원문에 있던 브루트포스, 백트래킹, 이진 탐색, 큐 아이디어 중에서 실제로 가장 설명 가치가 큰 부분은 후보 생성 방식입니다. 그래서 이 보강은 풀이 선택지를 나열하는 대신 Lunlun Number를 어떻게 직접 만들어낼지에 초점을 맞췄습니다.

이어서 볼 글

• BFS 알고리즘: 큐, 방문 처리, 최단거리 구현 - 큐로 작은 후보를 순차 생성하는 풀이의 기본 탐색 구조를 설명한다.
• DFS 깊이 우선 탐색 개념과 시간복잡도 - 재귀로 다음 자릿수를 생성하는 대안 풀이의 기본 구조를 설명한다.

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

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

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

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

이문제는 대략 살펴보아도 

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

브루트 포스를 이용한 방법

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

예들들어 현재 숫자가 2

43일때 2가 violation이므로 둘째자리 숫자인 4가 9가 될때까지 50을 더해서 2

9

3까지 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

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