승코딩당당당

문제[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++] 백준 11689: GCD(n, k) = 1 GOLD 1https://www.acmicpc.net/problem/11689 접근 방법이 문제는 어떤 수 n에 대해, 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 구하는 문제다.이는 곧 오일러 피 함수 φ(n)를 구하는 문제이고, 공식을 이용하면 다음처럼 쓸 수 있다.여기서p∣n 은 “p가 n의 약수(소인수)”라는 뜻곱은 “n의 서로 다른 소인수들”에 대해서만 한 번씩 해주면 된다.즉,n을 소인수분해해서 서로 다른 소인수 p 들을 찾고ret에 ret = ret * (1 - 1 / p)를 순서대로 적용해 주면 최종적으로 ret이 φ(n)이 된다.이 공식을 그대로 구현하면, n이 최대 범위일 때도 O(√n) 안에 해결할 수 있다. 상세 아..

문제[C++] 백준 1016: 제곱 ㄴㄴ 수 GOLD 1https://www.acmicpc.net/problem/1016 접근 방법구간 [Min,Max][Min, Max][Min,Max] 안에 있는 수들 중에서 어떤 소수 p에 대해 p^2로 나누어떨어지지 않는 수(= 제곱 ㄴㄴ 수)의 개수를 세는 문제이다. 즉, 구간 안에서 2^2, 3^2, 5^2, ... 이런 제곱수들로 나누어 떨어지는 수는 다 제외하고 남는 숫자의 개수를 세면 된다. 하지만 여기서 중요한 제약은 이와 같기 때문에,단순히 1 ~ Max까지 배열 만들어서 에라토스테네스 같은 걸 돌리거나매 수마다 제곱수 나눠보는 방식으로는 시간/메모리 초과가 난다.그래서 이 문제는 “전체를 다 보는 게 아니라, [Min, Max] 구간만 슬라이딩해서 ..

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