승코딩당당당

문제[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)이다. 최대공약수를 구하는 가장 기본적인 방법은..

코딩 테스트에서 수학 알고리즘 문제를 풀다 보면 자주 등장하는 개념이 바로 최대공약수(GCD)이다. 최대공약수를 구하는 가장 기본적인 방법은 두 수를 소인수 분해한 뒤, 공통된 소수들의 곱을 구하는 것이다.하지만 이 방법은 구현이 번거롭고, 큰 수에 대해서는 비효율적이다. 이를 훨씬 간단하고 빠르게 구할 수 있는 방법이 바로 유클리드 호제법(Euclidean Algorithm) 이다.이번 글에서는 유클리드 호제법의 원리와 동작 과정, 그리고 왜 이 방법이 효율적인지 정리해보려고 한다. ✍️ 유클리드 호제법이란?유클리드 호제법은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.이 알고리즘의 핵심 아이디어는 다음과 같다.두 수 A와 B에 대해 A를 B로 나..

문제[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) 안에 해결할 수 있다. 상세 아..

수학 기반 알고리즘 문제 중에서는 정수론(Number Theory) 개념을 묻는 문제가 종종 등장한다.그중 대표적인 개념이 바로 오일러 피 함수(Euler’s Totient Function) 이다.처음 보면 다소 생소할 수 있지만, 원리를 이해하면 에라토스테네스의 체와 매우 유사한 구조를 가진다.https://xeungcoding.tistory.com/58 소수(prime number) 구하기 - 에라토스테네스의 체그래프나 탐색 알고리즘뿐만 아니라, 코딩 테스트에서는 수학적 개념을 코드로 구현하는 문제도 자주 출제된다.그중 대표적인 주제가 바로 소수 구하기이다.소수는 정의 자체는 단순하지만, 입xeungcoding.tistory.com 이번 글에서는 오일러 피 함수의 정의와 원리,그리고 배열을 이용한 계..

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

출판사 서평 “그애는 나의…… 질문입니다.나에게 주어진 지극한, 가장 어려운 질문입니다.”부모의 생사를 알지 못한 채 보육원에서 자란 한 소녀. 그녀는 어느 날 자신에게 특별한 능력이 있다는 것을 알게 된다. 타인의 상처에 손을 대면 그의 생각을 말 그대로 ‘읽을’ 수 있다는 것. 그녀는 어린 시절 사고로 다친 친구의 출혈을 멈추기 위해 상처를 손바닥으로 눌렀을 때 자신의 머릿속으로 쏟아져들어오는 언어의 홍수를 통해 그러한 능력을 어렴풋이 자각하지만 그것을 이용할 수 있으리라는 생각은 하지 못한 채 성장한다. 한편 우연히 그녀의 능력을 알게 된 사업가 문오언은 그 능력을 어디에 활용할 수 있을지 누구보다 잘 알고 있는 인물이다. 오언은 보육원을 나온 뒤 고단한 삶을 이어가다 도움을 구하기 위해 자신을 찾..

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

문제[C++] 백준 1764: 듣보잡 SILVER 4https://www.acmicpc.net/problem/1764 접근 방법이 문제는 듣도 못한 사람 N명 + 보도 못한 사람 M명이 주어졌을 때, 두 목록에 모두 속하는 사람(= 듣보잡) 을 찾는 문제다. 즉, 간단히 말하면문자열 집합 A와 집합 B의 교집합을 구한 뒤, 그 결과를 사전 순으로 정렬해서 출력하는 문제. 풀이 아이디어는 이렇게 잡았다.먼저 듣도 못한 사람 N명을 입력받으면서 map who에 이름을 저장한다.이름을 key, 값을 1로 저장 → 존재 여부 체크용다음으로 보도 못한 사람 M명을 입력받으면서who[str] == 1이면 듣도 보도 못한 사람이므로 ret 벡터에 push.ret에 모아둔 이름들을 sort로 사전 순 정렬한 뒤,개수..