Hello, World & Me Hello, World & Me

📘 LeetCode 2540. Minimum Common Value📝 문제 설명두 개의 정렬된 정수 배열 nums1과 nums2가 주어진다.두 배열 모두에 공통으로 존재하는 가장 작은 정수를 반환하라.공통된 값이 없으면 -1을 반환한다.🔹 제약 사항두 배열 모두 오름차순 정렬되어 있음각 배열의 길이는 1 이상 10⁵ 이하🔸 예시✅ 예시 1Input:nums1 = \[1, 2, 3\], nums2 = \[2, 4\]Output:2✅ 예시 2Input:nums1 = \[1, 2, 3, 6\], nums2 = \[4, 5, 6\]Output:6💡 해설두 배열이 모두 오름차순 정렬되어 있다는 점을 활용하면,투 포인터 방식으로 매우 효율적으로 풀 수 있다.🚀 해결 전략포인터 i, j를 각각 nums1,..

📘 LeetCode 917. Reverse Only Letters📝 문제 설명주어진 문자열 s에서 영문자(letter)만 뒤집고,숫자, 기호 등의 비영문자는 원래 위치를 그대로 유지한 문자열을 반환하라.🔹 예시Input:s = "a-bC-dEf-ghIj"Output:"j-Ih-gfE-dCba"🔸 추가 예시Input:s = "Test1ng-Leet=code-Q!"Output:"Qedo1ct-eeLg=ntse-T!"💡 해설이 문제는 투 포인터 알고리즘의 전형적인 응용이다.양쪽 끝에서 시작하는 포인터(left, right)를 활용하여,양쪽에서 영문자만 만나면 교체하고,영문자가 아닌 문자는 그대로 두고 포인터만 이동한다.이 방식은 문자열을 한 번만 스캔하므로 시간 복잡도는 O(n) 이다.🚀 해결 전략..

# 📘 LeetCode 557. Reverse Words in a String III ## 📝 문제 설명 문자열 `s`가 주어졌을 때, 각 단어 안의 문자를 뒤집어서 새로운 문자열을 반환하라.   단어의 순서는 그대로 유지해야 한다. - 단어는 공백(`' '`) 하나로 구분되어 있음 - 공백 외의 다른 구분자는 없음 - 문자열 `s`에는 최소한 하나의 단어가 존재함 ### 🔹 예시 **Input:**

위상정렬 (Topological Sort) 완벽 정리✅ 위상정렬이란?방향 그래프(DAG)에서 선행 조건을 지키며 노드들을 정렬하는 알고리즘.대표적인 예:선수과목 → 후속 과목작업 A → 작업 B (A를 먼저 해야 B가 가능)🔑 조건DAG (Directed Acyclic Graph) 이어야 함사이클이 존재하면 위상정렬 불가능📘 용어 정리용어의미진입 차수해당 노드로 들어오는 간선의 개수진출 차수해당 노드에서 나가는 간선의 개수진입 차수 0선행 조건이 없는 노드, 바로 처리 가능🔁 위상정렬 알고리즘 흐름 (진입 차수 기반)모든 노드의 진입 차수 계산진입 차수가 0인 노드를 큐에 삽입큐에서 꺼내며 결과 리스트에 추가꺼낸 노드가 향하는 노드들의 진입 차수 -1새로 진입 차수 0이 된 노드를 큐에 삽입큐가 빌..

📌 백준 2565번 - 전깃줄 (LIS / DP / 이분 탐색)✨ 문제 요약두 전봇대(A, B)가 있고, 각각의 전깃줄이 A의 위치와 B의 위치를 쌍으로 갖는다.전깃줄이 서로 교차하지 않도록 하기 위해 최소 몇 개를 제거해야 하는지 구하는 문제다.🧠 문제 해석전깃줄이 교차하지 않으려면 A에서의 순서가 증가할 때, B에서도 증가해야 한다.즉, A를 기준으로 정렬하면남은 B 값들이 가장 긴 증가하는 부분 수열(LIS)이 되도록 전깃줄을 선택하면 됨.✅ 정답 로직전깃줄 목록을 A 기준으로 오름차순 정렬한다.정렬된 리스트에서 B 값들만 추출한다.B 값들에서 LIS를 구한 뒤,전체 전깃줄 수 - LIS 길이 = 제거할 전깃줄 수🧱 DP 풀이 (O(N²))N = int(input())arr = [tuple(m..

📌 백준 9655번 - 돌 게임 (게임 이론 / DP)✨ 문제 요약1 또는 3개의 돌을 가져갈 수 있는 게임이 있다.총 N개의 돌이 있으며, SK와 CY가 번갈아가며 돌을 가져간다.마지막 돌을 가져가는 사람이 이긴다.SK가 항상 먼저 시작이기는 사람의 이름을 출력 ("SK" 또는 "CY")🧠 문제 해석이 문제는 기초적인 게임 이론 또는 DP로 푸는 대표 문제다.핵심은 "현재 돌 개수에 따라 이기는 사람이 정해진다"는 점이다.✅ 수학적 풀이 (패턴 관찰)N (돌 개수)승자1SK2CY3SK4CY5SK→ 홀수면 SK가 이기고, 짝수면 CY가 이긴다!✨ 정답 코드 (수학 풀이)N = int(input())print("SK" if N % 2 == 1 else "CY")✅ DP 풀이🔧 상태 정의dp[i] = ..

📌 백준 2839번 - 설탕 배달 (DP)✨ 문제 요약당신은 설탕을 정확히 N킬로그램 배달해야 합니다.설탕 봉지는 3kg 또는 5kg 두 종류만 있습니다.가장 적은 봉지 수로 N킬로그램을 배달하려면 몇 개가 필요할까요?만약 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.🧠 문제 해석3kg, 5kg 봉지만 사용 가능조합해서 정확히 N을 만들어야 함최소 봉지 수를 구하는 문제 → 최소값 DP🔧 점화식 설계dp[i] = i킬로그램을 만들기 위한 최소 봉지 수기본 점화식:dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1)i-3에 3kg 하나 추가i-5에 5kg 하나 추가둘 중 최소값 선택초기값:dp[0] = 0 (0kg은 봉지 0개)나머지는 float('inf')로 설정 (..

📌 백준 11722번 - 가장 긴 감소하는 부분 수열 (LDS)✨ 문제 요약수열이 하나 주어졌을 때,그 수열에서 감소하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.🧠 문제 해석LIS(가장 긴 증가하는 부분 수열)와 반대 개념즉, 수열의 요소들이 점점 작아지는 방향으로 이어져야 함연속되지 않아도 되고, 순서만 지켜지면 됨🔧 점화식 설계dp[i] = i번째 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이for i in range(N): for j in range(i): if arr[i] 🧱 DP 테이블 예시입력: arr = [10, 30, 10, 20, 10]i arr[i] dp[i] 의미 (i까지 고려했을 때 감소하는 수열 길이)0101 (처음 원소)1301 (증..