✅ 1. 머신러닝 기본 개념

(1) 지도학습(Supervised Learning)

정답이 있는 데이터를 이용해 학습하는 방식
→ Kaggle 대회의 대부분이 이 방식이다.

예시:

• 대출 승인 여부 예측 (0/1, Classification)
• 집값 예측 (숫자 예측, Regression)

(2) 특징(Feature)와 라벨(Label)

머신러닝 모델은 아래 2개로 구성된 데이터를 사용한다.

Kaggle의 예:
loan_status → label
나머지 모든 컬럼 → features

(3) 모델(Model)

입력 데이터를 보고 정답을 예측하는 알고리즘.
Kaggle에서는 아래 모델들을 가장 많이 사용한다.

• LightGBM
• XGBoost
• CatBoost
• Logistic Regression
• Random Forest
• Neural Network(딥러닝)

특히 Tabular(표 형식) 문제는 LightGBM/XGBoost/CatBoost가 최강이다.

✅ 2. 데이터 전처리(Preprocessing)

Kaggle에서 가장 중요한 단계 중 하나.

(1) 결측치 처리(Missing Values)

데이터에 비어 있는 값이 있으면:

• 평균/중앙값으로 채우기
• 최빈값으로 채우기
• 모델 기반 채우기
• 또는 CatBoost처럼 자동 처리 기능 사용

(2) 범주형 변수 처리(Categorical Encoding)

문자/카테고리 데이터는 모델이 직접 사용할 수 없으므로 숫자로 변환해야 한다.

방법:

• One-Hot Encoding
• Label Encoding
• CatBoost Encoding

(3) 스케일링(Scaling)

데이터 단위를 고르게 만드는 작업 >> 딥러닝/로지스틱 회귀에서 특히 중요

• StandardScaler (평균=0, 표준편차=1로 변환)
• MinMaxScaler (0~1로 정규화)

단, Tree 모델(LGB/XGB/CatBoost)은 스케일링 필요 없음

3. 학습/검증/테스트 개념

(1) Train / Validation / Test 분리

모델이 과적합(overfitting)되지 않도록
훈련용, 검증용, 테스트용을 나눠야 한다.

Kaggle에서 가장 중요한 평가 방식은:

(2) K-Fold Cross Validation(CV)

데이터를 k개로 나눠 번갈아가며 검증하는 방식
불안정한 점수를 안정적으로 만들어 준다.

예: StratifiedKFold(n_splits=5)

Kaggle에서 성능을 올리려면CV 전략이 거의 절반이다.

✅ 4. 모델 평가 지표(Metrics)

대회마다 평가 기준이 다르다.

가장 많이 쓰는 지표:

특히 Kaggle에서는
Accuracy보다 AUC가 훨씬 중요하다.

✅ 5. 하이퍼파라미터(Hyperparameters)

모델이 학습하는 과정에서
"조정하는 여러 가지 설정"을 말한다.

예)

• learning_rate
• max_depth
• num_leaves
• n_estimators

튜닝할수록 성능이 올라간다.

튜닝 방법:

• Grid Search
• Random Search
• Optuna (가장 강력)
• Bayesian Optimization

✅ 6. 앙상블(Ensemble)

여러 모델을 함께 사용하는 방식.
Kaggle 상위권의 핵심 전략.

종류:

• Bagging
• Boosting
• Blending
• Stacking ← 가장 성능 좋음
• Voting Ensemble

Ensemble = 성능 증가 + 안정성 증가

✅ 7. Kaggle 실전 Workflow (가장 중요)

Kaggle에서 머신러닝 할 때 가장 흔한 완전한 작업 흐름:

이 순서를 반복하면 자연스럽게 실력이 성장한다.

⭐ 기초 개념만 알면 Kaggle은 바로 시작 가능하다

Kaggle은 초보자에게도 매우 친절한 플랫폼이라
기본 개념만 제대로 잡으면 누구나 시작할 수 있다.

필수 기초 개념 7개는 다음과 같다.

✔ 지도학습/분류/회귀
✔ Feature & Label
✔ 전처리(결측치/범주형 처리)
✔ One-hot / Label Encoding
✔ Cross-Validation (특히 K-Fold)
✔ 평가 지표(AUC, RMSE 등)
✔ 하이퍼파라미터 튜닝

이 정도만 알고 있어도
Playground 시리즈 정도는 충분히 도전 가능하다.

🧠 Kaggle이란?

데이터 분석가 · 머신러닝 엔지니어 · AI 개발자들이 모여 실력을 겨루고 성장하는 세계 최대의 데이터 과학 플랫폼

Kaggle(캐글)은 Google이 운영하는 글로벌 데이터 사이언스 플랫폼으로,
머신러닝 모델 개발·데이터 분석·경진대회·코드 공유까지
AI 개발에 필요한 모든 생태계가 갖춰져 있는 곳이다.

전 세계 개발자들이 실력을 겨루고 교류하는 중심지이기도 하다.

🚀 1. Kaggle의 핵심 기능

1) 머신러닝 대회 (Competitions)

Kaggle을 대표하는 기능이다.
기업·연구기관·정부 등이 제공한 데이터로 문제를 해결하는 방식이며
참가자들은 모델을 만들어 리더보드(Leaderboard) 점수를 겨룬다.

다룰 수 있는 분야는 매우 다양하다.

• 대출 승인 예측 (Tabular Data)
• 이미지 분류 / 객체 탐지 (Vision)
• 자연어 처리 (NLP)
• 시계열 예측 (Time-Series)
• 추천 시스템
• 음성 인식, 이상 탐지 등

특히, 현실 데이터 기반 과제가 많아 실무 감각을 익히기에 최고의 환경이다.

2) 방대한 공개 데이터셋 (Datasets)

Kaggle은 수백만 개가 넘는 데이터셋을 무료로 제공한다.

예를 들면:

• Netflix 시청 기록
• 도로 교통 데이터
• 브랜드 소비자 리뷰
• 의료 영상 데이터
• 주택 가격 정보
• 자연재해 기록

데이터 분석 연습 시 가장 어려운 부분은 “쓸만한 데이터 찾기”인데 Kaggle은 그 문제를 완벽히 해결해준다.
필요한 데이터를 즉시 불러와 바로 분석할 수 있다.

3) Kaggle Notebook (코드 실행 환경)

별도의 IDE나 서버 없이
웹 브라우저에서 바로 Python 코드를 실행할 수 있다.

• GPU / TPU 무료 제공
• 16GB 메모리
• 다양한 머신러닝 라이브러리 사전 설치
• 데이터셋 자동 연동

덕분에 로컬 환경을 설정하지 않아도 딥러닝 모델을 바로 돌릴 수 있다.

4) 코드 공유 (Code / Notebooks)

다른 유저가 올린 Notebook을 복사해 실행하거나
자신의 코드를 공개해 포트폴리오로 활용할 수 있다.

이 기능 덕분에 초보자도 빠르게 성장할 수 있다.

• “고수는 어떻게 모델링하는가?”
• “특정 문제에서는 어떤 전처리가 효과적이었는가?”
• “하이퍼파라미터 튜닝은 어떻게 하는가?”

이런 질문에 대한 답을 실제로 공개된 코드에서 직접 확인할 수 있다.

5) Discussion & Q/A

Kaggle에는 굉장히 활발한 토론 커뮤니티가 있다.

• 모델링 팁 공유
• 베이스라인 코드 공유
• 상위권 솔루션 분석
• 에러 해결

특히 대회 종료 후 올라오는 **상위권 참가자의 솔루션 글(solution write-up)**은 교재보다 훨씬 실전적이고 도움이 된다.

🎯 2. Kaggle을 하면 얻을 수 있는 것

1) 실무형 머신러닝 능력

Kaggle의 데이터는 단순한 연습용이 아니라 기업이나 연구자가 실제로 해결하고 싶은 문제다.

따라서 Kaggle 경험은 곧 실무 경험과 맞닿아 있다.

2) 포트폴리오

Notebook과 코드, Competition 순위는 그 자체로 훌륭한 포트폴리오가 된다.

실제로 많은 기업이 “Kaggle 경험”을 플러스 요소로 본다.

3) 데이터 분석 실력 향상

Kaggle을 하게 되면 자연스럽게 다음 능력이 성장한다:

• 피처 엔지니어링
• 모델 선택 및 비교
• 하이퍼파라미터 튜닝
• 앙상블 기법
• CV 전략
• 데이터 리딩 & EDA

이 기술들은 실무에서 바로 사용하는 스킬들이다.

4) 글로벌 커뮤니티 경험

전세계의 데이터 과학자들과 함께 같은 문제를 해결하고, 결과를 비교할 수 있다.

이 과정 자체가 큰 성장 동력이 된다.

🎖 3. Kaggle 등급 시스템

Kaggle은 실력에 따라 메달과 랭크가 매겨진다.

특히 Grandmaster는 AI 업계에서도 최고 수준의 실력자로 평가된다.

🛠 4. 초보자가 Kaggle을 시작하는 방법

1. Kaggle 가입
2. Notebook에서 Python 연습
3. 쉬운 Playground 대회 참여
4. 다른 참가자 Notebooks 참고
5. 리더보드 점수 올려보기
6. 점차 더 어려운 대회로 이동

이 과정을 반복하면 자연스럽게 머신러닝 실력이 올라간다.

✨ 5. Kaggle을 왜 해야 할까?

Kaggle은 단순히 ‘대회 사이트’가 아니다. 데이터 분석과 머신러닝을 배우는 “성장 플랫폼”이다.

✔ 데이터 분석력 향상
✔ 실무형 포트폴리오 구축
✔ 모델링 감각 개발
✔ 글로벌 커뮤니티 경험
✔ 직무 역량 강화

데이터분석 · AI 분야로 진로를 생각한다면 Kaggle은 거의 필수 경험이라고 할 수 있다.

📌 마무리

Kaggle은 배우고 성장하고, 실력을 증명하는 곳이다.
데이터를 좋아한다면,
머신러닝을 배우고 싶다면,
AI 개발자가 되고 싶다면,

Kaggle은 최고의 출발점이 될 것이다.

백준 파이썬 공부 2025.11.08
1987번 알파벳 (골드 4)

1. 문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 
새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 
즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 
말이 지나는 칸은 좌측 상단의 칸도 포함된다.

2. 입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 
둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

3. 출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

4. 문제 풀이
처음에는 set 자료형을 이용해서 알파벳 경로를 확인하려 했으나, 시간초과가 나왔다.
따라서 다른 방식을 찾아봤다.

<비트 마스크>
- 정수 하나를 선택하여, 각각의 알파벳에 해당하는 위치의 비트를 할당하고,
이동했다면, 1, 이동한적 없다면 0으로 처리하여 하나의 정수를 나타내는 비트에 저장하는 방법
- 이동했는지 여부를 확인하려면, 각각의 비트의 교집합이 0인지 확인하면 된다.
(visited & val == 0 # visited : 현재까지 방문한 알파벳이 저장된 정수, val : 현재 방문한 알파벳의 위치의 비트)
- 새롭게 이동한 위치에 대한 갱신은 각각의 비트의 합집합으로 나타내면 된다.
(visited | val # visited : 현재까지 방문한 알파벳이 저장된 정수, val : 현재 방문한 알파벳의 위치의 비트)

필요한 함수
- ord(문자) : 해당 문자에 해당하는 유니코드 정수 반환 ('A' = 65)
- << : 왼쪽 비트 이동
- & : 논리곱 비트 연산자 (둘다 1인 경우에만 1)
- | : 논리합 비트 연산자 (둘다 0인 경우에만 0)

>>코드

"""
1987번 알파벳
입력 : r (행), c (열)
board (보드 상태) 
출력 : count (말이 지날 수 있는 최대 칸 수)
"""
r, c = map(int, input().split())
board = [input() for _ in range(r)]

count = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def DFS(x, y, visited, depth):
    global count
    count = max(count, depth)
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < r and 0 <= ny < c:
            # 해당 알파벳을 유니코드로 반환 후 0 ~ 25 사이의 수로 변환
            # 수에 해당하는 인덱스의 비트를 1로 변환한 수 생성
            val = 1 << (ord(board[nx][ny]) - 65)
            if visited & val == 0:
                DFS(nx, ny, visited | val, depth + 1)

start = 1 << (ord(board[0][0]) - 65)
DFS(0, 0, start, 1)
print(count)

5. 문제 링크
https://www.acmicpc.net/problem/1987

백준 파이썬 공부 2025.11.07
17070번 파이프 옮기기 1 (골드 5)

1. 문제
유현이가 새 집으로 이사했다. 
새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 
각각의 칸은 (r, c)로 나타낼 수 있다. 
여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 
각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 
파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 
벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 
즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 
파이프는 밀면서 회전시킬 수 있다. 
회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 
대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 
꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 
파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

2. 입력
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 
둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 
빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

3. 출력
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 
이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

4. 문제 풀이
경로의 경우의 수를 구하는 방식이다.

<고려할 점>
1) 파이프의 좌표에 대해
문제상에선 파이프가 2좌표에 걸쳐있지만, 사실상 파이프의 끝좌표만 중요하다.
걸쳐있는 시작 좌표는 이미 지나온 좌표이기 때문

2) 이동 방식에 대해
현재 파이프가 놓인 방향에 따라 이동 가능한 방식이 달라진다는 것을 인지하자.
- 현재 상태가 가로 방향이면, 가로, 대각선 이동 가능
- 현재 상태가 세로 방향이면, 세로, 대각선 이동 가능
- 현재 상태가 대각선 방향이면, 가로, 세로, 대각선 이동 가능

3) 구현 방식에 대해
경로를 구하는 방식은 BFS, DFS 모두 가능하나,
최단경로가 아닌 모든 경로의 수를 구하므로, BFS를 사용할 경우 house의 크기가 커지면,
queue에 저장된 값이 너무 많아져서 메모리 초과가 나타날 수 있다.
따라서 DFS 또는 DP 이용

>>코드

"""
17070번 파이프 옮기기 1
입력 : n (집 한변 길이)
house (집 상태  0 : 빈 공간, 1 : 벽) 
출력 : count ((0, 0) 에서 (n, n)으로 이동시키는 경우의 수)
"""
n = int(input())
house = [list(map(int, input().split())) for _ in range(n)]
count = 0

# x(행번호), y(열번호), d(방향)
# d(현재 상태) = 0(가로), 1(세로), 2(대각)
def DFS(x, y, d):
    global count
    
    if x == n-1 and y == n-1:
        count += 1
        return
    
    # 가로 이동
    if d == 0 or d == 2:
        nx, ny = x, y + 1
        if 0 <= nx < n and 0 <= ny < n:
            if house[nx][ny] == 0:
                DFS(nx, ny, 0)
    
    # 세로 이동
    if d == 1 or d == 2:
        nx, ny = x + 1, y
        if 0 <= nx < n and 0 <= ny < n:
            if house[nx][ny] == 0:
                DFS(nx, ny, 1)
   
    # 대각선 이동
    nx, ny = x + 1, y + 1
    if 0 <= nx < n and 0 <= ny < n:
        if house[nx][ny] == 0 and house[x][ny] == 0 and house[nx][y] == 0:
            DFS(nx, ny, 2)

DFS(0, 1, 0)
print(count)

5. 문제 링크
https://www.acmicpc.net/problem/17070

백준 파이썬 공부 2025.11.06
1918번 후위 표기식 (골드 2)

1. 문제
수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 
연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 
연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 
연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 

예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 
후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 
이 방법의 장점은 다음과 같다. 

- 우리가 흔히 쓰는 중위 표기식 같은 경우에는 
덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 
후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 

- 또한 같은 방법으로 괄호 등도 필요 없게 된다. 
예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 
우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 
그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 
그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 
마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 
연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

2. 입력
첫째 줄에 중위 표기식이 주어진다. 
단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 
그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 
표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

3. 출력
첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

4. 문제 풀이
스택문제이다

<기호처리 방식>
- 피연산자 (A~Z) : 바로 출력
- '(' : 스택에 push
- ')' : '('이 나올 때까지 스택 pop → 출력
- 연산자 ('+', '-', '*', '/') : 우선순위가 같거나 높은 연산자가 스택 top에 있으면 pop 후 출력, 그 다음 push

처음에는 따로 괄호를 일일히 씌운 후 처리해야 하나 했지만,

연산자에 우선순위를 매겨 순서대로 pop하면 된다는 것을 깨달았다.

>>코드

"""
1918번 후위 표기식
입력 : middle (중위 표기식)
출력 : back (후위 표기식)
"""
def transform(formula):
    stack = []
    result = []

    for c in formula:
        if c.isalpha():  # 피연산자 (A~Z)
            result.append(c)

        elif c == '(':
            stack.append(c)

        elif c == ')':
            while stack and stack[-1] != '(':
                result.append(stack.pop())
            stack.pop()  # '(' 제거

        elif c in ['+', '-', '*', '/']:
            while stack and stack[-1] != '(' and priority(stack[-1]) >= priority(c):
                result.append(stack.pop())
            stack.append(c)

    while stack:
        result.append(stack.pop())

    return ''.join(result)

def priority(op):
    if op in ['*', '/']:
        return 2
    elif op in ['+', '-']:
        return 1
    else:
        return 0

initial = input().strip()
print(transform(initial))

5. 문제 링크
https://www.acmicpc.net/problem/1918

백준 파이썬 공부 2025.11.05
1865번 웜홀 (골드 3)

1. 문제
때는 2020년, 백준이는 월드나라의 한 국민이다. 
월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. 
(단 도로는 방향이 없으며 웜홀은 방향이 있다.) 
웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 
특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 
웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 
한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 
출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 
여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

2. 입력
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 
그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 
각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 
도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다. 

그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다. 
S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다. 
그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 
S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다. 
T는 10,000보다 작거나 같은 자연수 또는 0이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 
지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

3. 출력
TC개의 줄에 걸쳐서 
만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 
불가능하면 NO를 출력한다.

4. 문제 풀이
가중치가 있는 최단거리 문제이지만, 가중치가 음수인 수가 존재한다.
이러면 원래 알던 다익스트라 알고리즘으로 문제 풀이가 불가능하다.
음수 가중치가 있으면 우선순위 큐 - 힙에서 잘못된 선택을 하게 되어 오답이 발생한다.

따라서 이용되는 알고리즘이 벨만-포드 알고리즘이다.

<벨만 포드 알고리즘>
“u → v”로 가는 간선의 가중치 w를 이용해
v로 가는 더 짧은 경로가 있으면 갱신(relaxation) 하는 것입니다.

방식
1. 시작점의 거리 dist[start] = 0 으로 초기화.
2. 나머지는 모두 inf (무한대).
3. 모든 간선을 확인하면서, dist[end] > dist[start] + weight 이면 값을 갱신.
4. 이 과정을 정점 개수 V - 1번 반복.

이유: 최단 경로는 최대 (V-1)개의 간선만 거칠 수 있기 때문입니다.

다만 일반적인 벨만 포드 알고리즘이 아닌, 변형을 써야하는데,
출발지점과 도착지점이 정해져있지 않고, 아무곳에서나 도착 시 음수 시간이 되면 되기 때문이다.

이러한 경우 초반 시간 초기화를 float('inf') 가 아니라 0으로 해놓으면 된다.
왜냐하면, 모든 곳에서 출발하여 도착하는 경우 도착한 값이 음수가 되면,
왕복 시간 음수가 가능해지기 때문이다.

나도 처음에 잘 이해가 안됐는데 순서대로 알고리즘의 특성을 나열해보면 답이 나온다.

1) 벨만 포드 알고리즘의 경우, 가중치가 음수인 간선이 존재한다.
2) 가중치의 합이 음수인 사이클 == 왕복 시 시작시간 이전으로 돌아오는 경로
3) 가중치의 합이 음수인 사이클이 존재하는 경우, 
해당 사이클의 이루는 노드를 지나는 경로는 무한하게 음수 가중치가 늘어난다.
4) 해당 사이클이 존재하는지를 알기 위해서는 n-1 반복을 한 후, 
한번 더 경로의 최소값을 갱신했을 때, 값이 변화하면 된다.
5) 다만 사이클과 아예 떨어진 노드(단독노드)에서 출발하는 경우도 존재하므로,
모든 노드를 0으로 초기화 하여, 모든 정점이 출발점이 될 수 있도록 한다.

>>코드

"""
1865번 웜홀
입력 : t (테스트 케이스)
n (지점수), m (도로수), w (웜홀수)
s (시작지점), e (도착지점), t(이동하는데 걸리는 시간)
출력 : YES/NO (시간이 줄어들면서 출발위치로 돌아오는 것이 가능한지 여부)
>> 도로는 방향이 없고, 웜홀은 방향이 있다.
>> 웜홀에서는 시간이 반대로 간다.
"""

def wormhole():
    n, m, w = map(int, input().split())
    
    RoadNWorm = []
    # 도로
    for __ in range(m):
        s, e, t = map(int, input().split())
        RoadNWorm.append((s, e, t))
        RoadNWorm.append((e, s, t))
    # 웜홀
    for __ in range(w):
        s, e, t = map(int, input().split())
        RoadNWorm.append((s, e, -t))
    
    #모든 노드에서 출발 가능
    time = [0] * (n+1)
    for i in range(n):
        for s, e, t in RoadNWorm:
            if time[e] > time[s] + t:
                time[e] = time[s] + t         
                if i == n-1:
                    print("YES")
                    return
    print("NO")
    
for _ in range(int(input())):
    wormhole()

        
5. 문제 링크
https://www.acmicpc.net/problem/1865

백준 파이썬 공부 2025.11.04
11444번 피보나치 수 6 (골드 2)

1. 문제
피보나치 수는 0과 1로 시작한다. 
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 
그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

3. 출력
첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

4. 문제 풀이
문제 자체는 간단한 재귀문제로 보이나.. 수의 제한범위가 심상치 않아보인다
일단 원래 방식대로 풀어보자

>>코드1. 재귀 이용 : 런타임 에러

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())

def fibo(n):
    if n == 0 or n == 1:
        return n
    return fibo(n-1) + fibo(n-2)

print(fibo(n))

뭐 당연한 결말이였던거 같다...
그러면 다이나믹 프로그래밍을 이용해보자..

>>코드2. 동적프로그래밍 이용 : 메모리 초과

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())

def fibo(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

print(fibo[n])

그렇다.. 메모리 초과 엔딩이다.
그렇다면,,? 숫자를 2개만 저장하며 갱신하는 방식으로 해보자

>>코드 3. 반복문 + 공간 최적화 DP : 시간초과

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())

def fibo(n):
    f = [0, 1]
    if n < 2:
        return f[n]
    for i in range(n):
        f[0], f[1] = f[1], f[0] + f[1]
    return f[0]
    
print(fibo(n))

그렇다.. 수가 너무 크기 때문에 이것도 시간초과가 나온다.
따라서 새로운 방법을 찾아내야 한다.

빠른 거듭제곱 (분할정복) 을 이용한다.
행렬의 곱셈을 이용하여, 피보나치 수를 구한다.
1 1
1 0  행렬을 거듭제곱하면 피보나치 수가 나온다.

방식이 더하기에서 곱하기로 바뀌었으므로 분할 정복이 가능하다.

- 거듭제곱 수p가 짝수면 : p//2 거듭제곱 x p//2 거듭제곱
- 거듭제곱 수p가 홀수면 : M [[1, 1], [1, 0]] x p//2 거듭제곱 x p//2 거듭제곱

또한 행렬의 곱셈 시 매번 MOD (1,000,000,007) 로 나누어 수가 너무 커지는 것을 방지한다.

>>코드 4. 정답입니다.

"""
11444번 피보나치 수 6
입력 : n (피보나치수 번호)
출력 : fibo (n번째 피보나치 수)
"""

n = int(input())
fibo = [0, 1]
MOD = 1000000007

def fibo(n):
    def mat_mult(A, B):
        return [
            [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD,
             (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD],
            [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD,
             (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD]
        ]
    
    def mat_pow(M, p):
        if p == 1:
            return M
        if p % 2 == 0:
            half = mat_pow(M, p//2)
            return mat_mult(half, half)
        else:
            return mat_mult(M, mat_pow(M, p-1))
        
    if n == 0:
        return 0
    
    M = [[1, 1], [1, 0]]
    result = mat_pow(M, n)
    return result[0][1]
    
print(fibo(n))

5. 문제 링크
https://www.acmicpc.net/problem/11444

백준 파이썬 공부 2025.11.03
1238번 파티 (골드 3)

1. 문제
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 
이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 
하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. 
N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

2. 입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 

두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 
그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 

시작점과 끝점이 같은 도로는 없으며, 
시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

3. 출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

4. 문제 풀이
가중치가 있으면서, 사이클이 있는 최단거리 >> 다익스트라 알고리즘

유의할 점
- 각각의 경로는 최소시간여야 하며, 최소시간인 경로들 중 최장 소요시간을 구한다.
- 경로가 단방향이기 때문에 A에서 X로 가는 시간과 X에서 A로 오는 시간을 각각 구해서 더해야한다.

>>>코드

"""
1238번 파티
입력 : n (학생수), m (도로수), x (파티장소)  
start, end, time (시작점, 끝점, 소요시간)
출력 : max_time (가장 오래걸리는 소요시간)
>> 모든 학생들 중 x에 갔다가 다시 돌아오는데 걸리는 최소시간이 가장 큰 학생
>> 그 학생의 최종 소요시간
"""
import heapq

n, m, x = map(int, input().split())
road = [[] for _ in range(n+1)]
for _ in range(m):
    start, end, time = map(int, input().split())
    road[start].append((end, time))
    
def calculation(start, end):
    heap = []
    heapq.heappush(heap, (0, start))
    
    time = [float('inf')] * (n+1)
    time[start] = 0
    
    while heap:
        cur_time, cur = heapq.heappop(heap)
        
        if cur_time > time[cur]:
            continue
        
        for next_city, w in road[cur]:
            if time[next_city] > cur_time + w:
                time[next_city] = cur_time + w
                heapq.heappush(heap, (time[next_city], next_city))
    
    return time[end]

total_time = []
for i in range(1, n+1):
    total_time.append(calculation(i, x) + calculation(x, i))
print(max(total_time))

5. 문제 링크
https://www.acmicpc.net/problem/1238