geminanolja 님의 블로그

📌 외판원 문제 (TSP, Traveling Salesman Problem)? 🚀🔹 문제 개요:어떤 한 도시에서 출발하여 모든 도시를 한 번씩 방문한 뒤, 다시 출발 도시로 돌아오는 최단 경로를 찾는 문제✅ 1. 문제 설명🎯 문제 예제어떤 도시들이 있고, 도시 간 이동 비용(거리)이 주어진다고 하자.📌 예제 입력 (도시 4개, 거리 행렬) 0 1 2 30 [0, 10, 15, 20]1 [10, 0, 35, 25]2 [15, 35, 0, 30]3 [20, 25, 30, 0]각 값 dist[i][j]는 도시 i에서 j로 가는 비용을 의미한다.예를 들어:dist[0][1] = 10 → 0번 도시에서 1번 도시로 가는 비용 10dist[2][3] = 30 → 2번 도시에서 3번 도시로 가는..

cote/Intermediate 2025. 2. 22. 20:48

https://www.acmicpc.net/problem/2225  #include using namespace std;const int MOD = 1000000000; // int dp[202][202]; // 배열 크기 확장 (최대 201까지 접근 가능하도록)int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, K; cin >> N >> K; for (int i = 0; i 0 ? dp[k][n - 1] : 0)) % MOD; } } cout

cote/Intermediate 2025. 2. 20. 19:52

https://www.acmicpc.net/problem/9251  🚀 Dynamic Programming (DP) 이해하기!🧩 DP = 완전탐색(Brute Force) + 메모이제이션(Memoization)🏗 DP의 핵심 개념1️⃣ 완전탐색처럼 모든 경우의 수를 생각 🤯2️⃣ 그 구조를 만들면서 점화식(Recurrence Relation)을 유도 🔄3️⃣ 계산된 값을 저장하여 중복 계산을 방지 (메모이제이션) 💾📌 메모이제이션(Memoization) 이란?📂 이미 계산된 값을 저장하고 재사용하는 것!📦 어디에 저장할까?✅ array (배열)✅ map (해시맵)✅ set (중복 방지)🔄 DP 해결 방식🔼 Top-Down (재귀, 직관적) 🛠재귀를 사용해 큰 문제를 작은 문제로 쪼개서..

cote/Intermediate 2025. 2. 19. 16:16

https://www.acmicpc.net/problem/11053 문제:수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하기e.g. 수열 A = {10, 20, 10, 30, 20, 50} , 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4 입력첫째 줄 수열 A의 크기 N (1 ≤ N ≤ 1,000)둘째 줄 수열 A를 이루고 있는 Ai (1 ≤ Ai ≤ 1,000) 출력수열 A의 가장 긴 증가하는 부분 수열의 길이 LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘 :주어진 수열에서 일부 원소를 선택하여 순서를 유지하면서 가장 긴 증가하는 부분 수열동적 계획법(DP, Dynamic Programmi..

cote/Intermediate 2025. 2. 18. 18:29

https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  #include #include #include #include#includeusing namespace std;// ✅ 1️ `banned_id` 패턴과 `user_id`가 매칭되는지 확인하는 함수bool isMatch(string user, string banned) { if (user.size() != banned.size()) return false; // 길이가 다르면 불가능 for (int i = 0; i > getMat..

cote/Challenge 2025. 2. 11. 16:53

https://www.acmicpc.net/problem/11399#include #include#includeusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector WaitingLine(n); for (int i = 0; i > WaitingLine[i]; } //for (auto a : WaitingLine) cout ❌ 순열로 풀면 비효율적! (Brute-force 접근 문제점)순열(모든 경우의 줄 서는 순서)을 사용하여 해결하는 방법도 가능하지만, 너무 비효율적순열을 이용한 풀이 방식N명의 사람이 줄을 서는 모든 경우(순열)를 구한다. →..

cote/Intermediate 2025. 2. 11. 15:05

https://www.acmicpc.net/problem/27961마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N마리를 집에서 키우기로 결심했다!마법소녀 마도카는 N마리의 고양이를 최소한의 행동 횟수로 생성하려 한다.초기에는 고양이가 없으며, 다음 두 가지 마법을 사용할 수 있다생성 마법: 고양이 1 마리를 마도카의 집에 생성한다.복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 k마리 존재한다면, 0마리 이상 k마리 이하의 고양이를 마도카의 집에 추가할 수 있다.마도카는 위의 2가지 마법을 적절히 사용하여, 마도카가 정확히 N마리의 고양이를 만들기 위해 필요한 최소 행동 횟수를 구하라. 🚀 #inc..

cote/Intermediate 2025. 2. 11. 10:55

https://www.acmicpc.net/problem/15686  1) nexxt_permutation 사용 :0초 나옴#include #include #include // next_permutationusing namespace std;int n, m; // 도시 크기, 유지할 치킨집 개수vector> PericanaChickenLocations;vector> HouseLocations;vector combination; // 조합 선택을 위한 배열// 특정 치킨집 조합으로 도시의 치킨 거리 계산int ChickenDistance(const vector>& selectedChicken){ int totalChickenDistance = 0; for (auto house : Hou..

cote/Intermediate 2025. 2. 7. 16:08