승코딩당당당

문제[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..

문제[C++] 백준 9471: 피사노 주기 SILVER 4https://www.acmicpc.net/problem/9471 접근 방법백준 9471번은 피사노 주기(Pisano Period) 를 구하는 문제다.피보나치 수열을 어떤 정수 m으로 나눈 나머지를 계속 계산하면 수열이 일정한 주기를 가지고 반복된다.이 반복되는 길이를 피사노 주기라고 한다. 예를 들어, 피보나치 수열을 3으로 나눈 나머지를 보면1 1 2 0 2 2 1 0 1 1 ...이렇게 특정 구간 이후부터 동일한 패턴이 반복된다.이 반복되는 길이가 바로 피사노 주기 k(m) 이다. 상세 아이디피사노 주기는 다음 성질을 가진다.k(m) ≤ m² − 1 즉, 최대 m^2번 정도만 확인하면 반드시 주기가 발견된다.그래서 반복문을 m * m 범위까..

문제[C++] 백준 11725: 트리의 부모 찾기 SILVER 2https://www.acmicpc.net/problem/11725 접근 방법이 문제는 루트가 1번인 트리가 주어졌을 때, 각 노드의 부모를 출력하는 문제다. 트리는 사이클이 없는 연결 그래프이기 때문에,1번 노드를 기준으로 DFS를 한 번만 돌면서 부모를 기록해주면 해결된다. 구현 아이디어는 간단하다:graph : 인접 리스트 (양방향 그래프)ret[i] : i번 노드의 부모 노드 번호visited[i] : 방문 체크DFS에서void dfs(int before, int now){ visited[now] = true; ret[now] = before; // now의 부모는 before for (int i = 0; i 이렇게..

문제[C++] 백준 1850: 최소공약수 SILVER 1 https://www.acmicpc.net/problem/1850 접근 방법백준 1850번은 두 정수 A와 B가 주어졌을 때, 각각이 1로만 이루어진 수(1111… 형태) 라고 생각하고그 둘의 최대공약수에 해당하는 1의 개수를 출력하는 문제다. 핵심 아이디어는 다음과 같다.111…(A개) 와 111…(B개)의 최대공약수는1이 GCD(A, B)개 있는 수가 된다. 즉,두 수의 최대공약수를 먼저 구하고그 개수만큼 1을 출력하면 된다.따라서 문제의 본질은 두 수의 최대공약수(GCD)를 구하는 것이다.유클리드 호제법을 이용하면 효율적으로 계산할 수 있다.int GCD(ll a, ll b){ if (a % b == 0) return b;..

문제[C++] 백준 1934: 최소공배수 BRONZE 1https://www.acmicpc.net/problem/1934 접근 방법백준 1934번은 두 수의 최소공배수(LCM) 를 구하는 문제다.최소공배수를 직접 구하기보다는, 다음 공식을 이용하면 훨씬 쉽게 해결할 수 있다.LCM(a, b) = a × b ÷ GCD(a, b) 따라서 문제의 핵심은 최대공약수(GCD) 를 구하는 것이다.최대공약수는 유클리드 호제법을 이용하면 효율적으로 구할 수 있다.https://xeungcoding.tistory.com/106 유클리드 호제법 (euclidean-algorithm)코딩 테스트에서 수학 알고리즘 문제를 풀다 보면 자주 등장하는 개념이 바로 최대공약수(GCD)이다. 최대공약수를 구하는 가장 기본적인 방법은..

문제[C++] 백준 1620: 나는야 포켓몬 마스터 이다솜 SILVER 4https://www.acmicpc.net/problem/1620 접근 방법이 문제는 포켓몬 이름과 번호를 양방향으로 조회해야 하는 문제다. 즉,이름이 주어지면 → 번호 출력번호가 주어지면 → 이름 출력이 두 가지를 모두 빠르게 처리해야 한다.그래서 자료구조를 두 개로 나누어 사용했다.map→ 이름 → 번호를 저장vector→ 번호 → 이름을 저장입력받을 때 포켓몬을 1번부터 차례대로 저장하면서 아래와 같이 두 자료구조에 동시에 기록한다.dic[str] = i; // 이름 → 번호dic2.push_back(str); // 번호 → 이름 질의를 처리할 때는 입력이 문자열로 들어오므로,첫 글자가 숫자라면 → stoi로 정수 ..

문제[C++] 백준 1991: 트리 순회 SILVER 1https://www.acmicpc.net/problem/1991 접근 방법백준 1991번은 이진 트리의 전위, 중위, 후위 순회 결과를 출력하는 문제다. 각 노드는 대문자 알파벳으로 표현되고, 입력으로 (부모, 왼쪽 자식, 오른쪽 자식) 형태가 주어진다.자식이 없는 경우는 '.'로 표시된다. 이 문제의 핵심은:트리를 직접 구성하고재귀를 이용해 3가지 순회 방식을 구현하는 것트리의 노드는 최대 26개(알파벳 A~Z)이므로 배열을 이용해 간단히 표현할 수 있다. 처음에 DFS로 푸는 문제라고 생각하여 DFS로 전위순회를 구현했지만 중위순회부터 막혔다..ㅠㅠ다른 사람들이 푼 걸 보니 너무 간단하게 푸는 문제여서 현타MAX.... 아래 블로그를 참고하였..

문제[C++] 백준 16953: A → B SILVER 2https://www.acmicpc.net/problem/16953 접근 방법백준 16953번은 정수 A를 B로 바꾸는 최소 연산 횟수를 구하는 문제다.사용할 수 있는 연산은 두 가지뿐이다.현재 값 × 2현재 값 뒤에 1을 붙이기 (예: 23 → 231)이 문제는 연산이 두 갈래로 계속 뻗어나가는 구조이기 때문에 그래프 탐색 문제로 볼 수 있다. 각 숫자를 하나의 노드라고 생각하면,val → val * 2val → val * 10 + 1이렇게 두 개의 간선이 존재하는 셈이다.최소 연산 횟수를 구해야 하므로 BFS(너비 우선 탐색) 을 사용했다. 상세 아이디어1. BFS로 최소 횟수 탐색queue> Q;Q.push(make_pair(a, 1)); ..