승코딩당당당

문제[C++] 백준 1976: 여행 가자 GOLD 4https://www.acmicpc.net/problem/1976 접근 방법백준 1976번은 여행 계획이 가능한지 판단하는 문제다.여러 도시가 있고, 도시 간 연결 정보가 주어질 때 주어진 여행 계획대로 모든 도시를 이동할 수 있는지 확인해야 한다. 핵심 아이디어는 다음과 같다.여행 계획에 포함된 모든 도시가하나의 연결된 그룹(같은 집합) 에 속해 있는지 확인하면 된다. 이 문제는 도시 간 연결 여부를 계속 확인해야 하므로Union-Find(Disjoint Set) 자료구조를 사용하는 것이 가장 효율적이다. 상세 아이디어부모 배열 초기화 parent.resize(N + 1, 0);for (int i = 1; i 각 도시는 처음에 자기 자신을 부모로 가..

문제[C++] 백준 1717: 집합의 표현 GOLD 5https://www.acmicpc.net/problem/1707 접근 방법백준 1717번은 집합의 합집합과 포함 여부를 처리하는 문제로,대표적인 Union-Find(Disjoint Set) 자료구조를 사용하는 문제다. 문제에서 수행하는 연산은 두 가지다.0 a b → a와 b를 같은 집합으로 합치기 (Union)1 a b → a와 b가 같은 집합인지 확인 (Find)따라서 핵심은 각 원소가 어떤 집합에 속해 있는지를 효율적으로 관리하는 것이다. 이를 위해 parent 배열을 사용한다.vector parent; parent[i] : i의 부모 노드초기에는 모든 원소가 자기 자신을 부모로 가진다.for (int i = 1; i Find (대표 노드 ..

문제[C++] 백준 1707: 이분 그래프 GOLD 4https://www.acmicpc.net/problem/1707 접근 방법이 문제는 주어진 그래프가 이분 그래프인지 판별하는 문제이다.이분 그래프란, 정점을 두 개의 집합으로 나누었을 때 같은 집합 내에서는 간선이 존재하지 않는 그래프를 의미한다.이를 해결하기 위해 그래프를 탐색하면서 각 정점을 두 가지 색(0, 1)으로 칠하는 방식을 사용한다.인접한 두 정점은 반드시 서로 다른 색이어야 함만약 같은 색이 되면 → 이분 그래프 아님그래프는 여러 개의 연결 요소로 나뉠 수 있으므로, 모든 정점을 시작점으로 탐색을 수행해야 한다.탐색 방법은 DFS를 사용하였다. 상세 아이디어1. 그래프 구성 vector> graph; 인접 리스트 형태로 그래프를 구성..

문제[C++] 백준 2251: 물통 GOLD 4https://www.acmicpc.net/problem/2251 접근 방법이 문제의 핵심은 상태를 그래프로 보고 BFS로 탐색하는 문제이다.각 물통의 상태를 하나의 노드로 보고, 물을 옮기는 행위를 간선으로 생각하면 된다. 처음에는 세 물통 A, B, C의 상태 (A, B, C)를 모두 고려해야 할 것 같지만,전체 물의 양이 항상 일정하기 때문에 다음과 같이 단순화할 수 있다.전체 물의 양 = 항상 C의 초기값따라서 C = 전체 - A - B로 계산 가능즉, (A, B)만 알면 상태를 완전히 표현할 수 있기 때문에 visited[A][B] 형태로 방문 체크를 진행한다.탐색은 BFS를 사용하여 가능한 모든 상태를 순회하며, 그 중에서 A가 0인 상태일 때의..

문제[C++] 백준 1325: 효율적인 해킹 SILVER 1https://www.acmicpc.net/problem/1325 접근 방법백준 1325번은 효율적인 해킹 문제로,어떤 컴퓨터를 해킹했을 때 가장 많은 컴퓨터를 해킹할 수 있는 시작 노드를 찾는 문제다. 핵심 포인트는 다음이다.A → B 라는 관계는A를 해킹하면 B도 해킹할 수 있다는 의미가 아니라B를 해킹하면 A를 해킹할 수 있다는 의미다. 그래서 그래프를 그대로 저장하면 안 되고, 간선 방향을 반대로 저장해야 한다.이렇게 하면 “어떤 노드에서 시작했을 때 도달 가능한 모든 노드”를 DFS로 쉽게 탐색할 수 있다.graph[b].push_back(a); 상세 아이디어1. 그래프 구성graph[b].push_back(a)→ b를 해킹하면 a를 ..

문제[C++] 백준 18352: 특정 거리의 도시 찾기 SILVER 2https://www.acmicpc.net/problem/18352 접근 방법백준 18352번은 특정 거리의 도시 찾기 문제로,시작 도시 X에서 출발했을 때 최단 거리가 정확히 K인 도시들을 모두 출력하는 문제다. 모든 도로의 거리가 1로 동일하기 때문에, 이 문제는 가중치가 없는 그래프에서의 최단 거리 탐색 문제로 볼 수 있다.이런 경우에는 BFS(너비 우선 탐색) 를 사용하면 된다. 그래프는 인접 리스트로 저장했다.vector> graph; 그리고 각 도시까지의 거리를 저장하기 위해 dist 배열을 사용했다.vector dist; 초기에는 모든 도시의 거리를 -1로 설정해두고,BFS를 하면서 처음 방문한 도시의 거리를 갱신해 나간..

문제[C++] 백준 1033: 칵테일 GOLD 2https://www.acmicpc.net/problem/1033 접근 방법백준 1033번은 재료들 사이의 비율 정보가 주어졌을 때,모든 재료의 양을 가장 작은 정수 비율로 구하는 문제다. 예를 들어 A와 B의 비율이 2:3 이라면,A의 양이 2일 때 B의 양은 3이 되고, A의 양이 4일 때 B의 양은 6이 되는 식으로 비율만 만족하면 여러 경우가 가능하다. 하지만 이 문제에서는 모든 재료의 양을 정수로 표현하면서, 동시에 더 이상 줄일 수 없는 최소 형태로 출력해야 한다.이 문제는 재료들을 정점, 비율 관계를 간선으로 생각해서 그래프 형태로 접근할 수 있다. 상세 아이디입력으로 주어지는 a, b, p, q는 다음 의미를 가진다.a : b = p : q..

문제[C++] 백준 2606: 바이러스 SILVER 3https://www.acmicpc.net/problem/2606 접근 방법백준 2606번은 컴퓨터 바이러스 문제로,1번 컴퓨터가 바이러스에 감염되었을 때 연결된 다른 컴퓨터가 몇 대 감염되는지 구하는 문제다. 컴퓨터들이 네트워크로 연결되어 있기 때문에, 이를 그래프 탐색 문제로 볼 수 있다.문제의 핵심은 다음과 같다.컴퓨터 = 노드네트워크 연결 = 간선따라서 그래프 탐색(DFS 또는 BFS) 을 이용해서 1번 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 방문하면 된다. 이번 풀이에서는 DFS(Depth First Search) 를 사용했다.먼저 그래프를 인접 리스트 형태로 저장한다.vector> graph;그리고 방문 여부를 확인하기 위해 배열을 사용..

문제[C++] 백준 10826: 피보나치 수 4 SILVER 5https://www.acmicpc.net/problem/10826 접근 방법백준 10826번은 N번째 피보나치 수를 출력하는 문제다.하지만 일반적인 피보나치 문제와 달리 값의 크기가 매우 커진다. 예를 들어 N이 커지면 피보나치 값은 수백 자리 이상의 정수가 되기 때문에long long 같은 기본 정수 타입으로는 저장할 수 없다.그래서 이 문제는 큰 정수(Big Integer) 를 직접 구현해야 한다.이를 위해 문자열(string) 을 이용해서 덧셈을 구현했다. 피보나치 점화식은 다음과 같다.F(n) = F(n-1) + F(n-2)하지만 문자열끼리 바로 덧셈이 되지 않기 때문에 문자열 덧셈 함수 add()를 만들어 계산했다. 문자열 덧셈의..

문제[C++] 백준 2749: 피보나치 수 3 GOLD 2https://www.acmicpc.net/problem/2749 접근 방법백준 2749번은 N번째 피보나치 수를 1,000,000으로 나눈 나머지를 구하는 문제다. 문제의 핵심은 N의 범위가 매우 크다는 것이다.N은 최대 10^18까지 주어질 수 있기 때문에, 단순히 피보나치 수열을 N까지 계산하는 방법으로는 해결할 수 없다. 이 문제를 해결하기 위해 피사노 주기(Pisano Period) 개념을 이용한다.피보나치 수열을 어떤 수 m으로 나눈 나머지는 반복되는 주기를 가진다.이 반복되는 길이를 피사노 주기라고 한다. 이 문제를 풀기 전에 백준 9471번 문제를 먼저 풀고 오는 것을 추천한다.관련 포스팅:https://xeungcoding.tis..