이 글에서는 주어진 문자열을 몇 번 회전했을 때 회문(palindrome)이 되는지 확인하는 방법을 살펴봅니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미합니다.예를 들어 AAAAD라는 문자열은 그 자체로는 회문이 아닙니다. 하지만 이를 한 칸 회전하면 AADAA가 되는데, 이는 회문입니다. 이처럼 적절히 회전하면 회문이 되는 문자열을 회전 회문(rotated palindrome)이라고 합니다.접근 방법문자열이 회전 회문인지 확인하는 기본적인 절차는 다음과 같습니다.1. 먼저 원본 문자열이 회문인지 검사합니다.2.

어떤 수가 주어졌을 때, 이 수를 두 개의 과잉수(Abundant Number)의 합으로 표현할 수 있는지 확인하는 문제입니다. 표현이 가능하다면 해당하는 두 수를 출력하고, 불가능하다면 -1을 출력해야 합니다.과잉수란?과잉수란 자기 자신을 제외한 약수(진약수)의 합, 즉 sum(n)이 그 수 자체의 값보다 큰 수를 말합니다. 예를 들어 12의 진약수는 1, 2, 3, 4, 6이며, 이들의 합은 16으로 12보다 크기 때문에 12는 과잉수에 해당합니다.문제 해결 접근 방식이 문제를 해결하기 위해 다음과 같은 전략을 사용합니다.먼저

정수 n이 주어졌을 때, 이 수의 이진수 표현이 교대 패턴(alternate pattern)을 가지는지 확인하는 문제를 살펴보겠습니다. 교대 패턴이란 101010...처럼 0과 1이 번갈아 나타나는 비트 배열을 의미합니다. 예를 들어 10진수 42의 이진 표현은 101010이므로 교대 패턴을 가진다고 볼 수 있습니다.접근 방법풀이 아이디어는 매우 직관적입니다. 이진수의 각 비트를 하나씩 검사하면서 인접한 두 비트를 비교하고, 두 비트가 같으면 즉시 false를 반환합니다. 끝까지 검사하는 동안 인접한 비트가 한 번도 같지 않았다면

문제 개요정수 n이 주어졌을 때, 이 수의 이진수 표현이 교대 패턴(alternating pattern), 즉 101010…과 같은 형태를 가지고 있는지 확인하는 문제입니다.O(1) 접근 방식의 핵심 아이디어가장 먼저 num = n XOR (n >> 1)을 계산합니다. 만약 n의 비트가 101010…처럼 번갈아 나타난다면, n을 오른쪽으로 한 비트 시프트한 값과 XOR 연산을 수행한 결과인 num의 모든 비트가 1이 됩니다.따라서 문제는 num의 모든 비트가 1인가?를 확인하는 것으로 단순화됩니다. 모든 비트가 1로 설정

이번 글에서는 특정 숫자가 크리슈나무르티 수(Krishnamurthy Number)인지 판별하는 방법을 알아보겠습니다. 어떤 수의 각 자릿수에 대한 팩토리얼 값을 모두 더한 합이 원래의 수와 같다면, 그 수를 크리슈나무르티 수라고 부릅니다.예를 들어 숫자 145를 살펴보겠습니다.1! + 4! + 5! = 1 + 24 + 120 = 145각 자릿수의 팩토리얼 합이 145로 원래 숫자와 일치하므로, 145는 크리슈나무르티 수입니다. 이 외에도 1과 2(1! = 1, 1! + ... = 2), 그리고 40585(4! + 0! + 5! +

이 글에서는 어떤 숫자가 23으로 나누어 떨어지는지 판별하는 프로그램을 살펴보겠습니다. 예를 들어 1191216이라는 숫자가 주어졌을 때, 이 숫자는 23으로 나누어 떨어집니다.23의 배수 판별 규칙23으로 나누어 떨어지는지 확인하려면 다음 규칙을 따라야 합니다.매번 숫자(또는 잘린 숫자)의 마지막 자릿수를 추출합니다.잘린 숫자에 마지막 자릿수에 7을 곱한 값을 더합니다.필요한 만큼 이 과정을 반복합니다.예시17043 → 1704 + 7 × 3 = 1725 1725 → 172 + 7 × 5 = 207 207은 9 × 23이므로, 1

이번 글에서는 주어진 숫자가 41로 나누어 떨어지는지 확인하는 프로그램을 C++로 작성해 보겠습니다. 예를 들어 104413920565933이라는 숫자가 있다고 가정해 봅시다. 이 숫자는 41로 나누어 떨어집니다.큰 숫자를 직접 나눗셈으로 검증하기보다는, 수학적으로 증명된 41의 배수 판별법을 활용하면 훨씬 간단하게 확인할 수 있습니다.41의 배수 판별법어떤 숫자가 41로 나누어 떨어지는지 확인하려면 다음 규칙을 반복적으로 적용합니다.숫자(또는 자릿수가 잘린 숫자)의 마지막 자릿수를 추출합니다.나머지 부분(마지막 자릿수를 제거한 숫

이번 글에서는 주어진 숫자나 문자열이 오직 1, 14, 144만을 이어 붙여 만든 형태인지 판별하는 문제를 다뤄보겠습니다. 예를 들어 111411441은 1 · 1 · 14 · 1 · 144 · 1의 연결이므로 유효한 숫자지만, 144414는 어떤 조합으로도 표현할 수 없기 때문에 유효하지 않습니다. 문제 해결 접근 방식 핵심 아이디어는 매우 간단합니다. 숫자의 마지막 자리부터 세 자리, 두 자리, 한 자리 단위로 잘라 내어 각각 144, 14, 1과 일치하는지 확인합니다. 일치하는 부분을 찾으면 해당 자릿수만큼 숫자를 줄인 뒤

배열 A와 정수 K가 주어졌을 때, K의 배수와 배수 사이에 위치한 요소들만 정렬하는 문제를 살펴보겠습니다. 예를 들어 배열이 [2, 13, 3, 1, 21, 7, 8, 13, 12]이고 K = 2라고 가정해 봅시다. 이 경우 출력 결과는 [2, 1, 3, 7, 13, 21, 8, 13, 12]가 됩니다.여기서 2의 배수는 2, 8, 12입니다. 2와 8 사이에 있는 요소들은 13, 3, 1, 21, 7이며, 이들은 오름차순으로 1, 3, 7, 13, 21로 정렬됩니다. 반면 8과 12 사이에는 13 하나만 존재하므로 이미 정렬된

문자열 배열과 하나의 참조 문자열이 주어졌다고 가정해 봅시다. 이때 참조 문자열에 나타난 문자들의 순서를 기준으로 문자열 배열을 정렬해야 합니다. 여기서는 배열 안의 문자열들과 참조 문자열이 모두 소문자 알파벳으로만 이루어져 있다고 가정합니다.문제 예시예를 들어 문자열 배열이 [hello, programming, science, computer, india]이고, 참조 문자열이 pigvxbskyhqzelutoacfjrndmw라고 합시다. 정렬 후의 결과는 다음과 같습니다.[programming, india, science, hell

두 개의 서로 다른 배열이 있을 때, C++ STL의 pair 클래스를 이용하면 한 배열을 다른 배열의 값에 맞춰 함께 정렬할 수 있습니다. 예를 들어 첫 번째 배열 A1 = [2, 1, 5, 4, 9, 3, 6, 7, 10, 8]과 두 번째 배열 A2 = [A, B, C, D, E, F, G, H, I, J]가 있다고 가정해 보겠습니다. 정렬 후 결과는 다음과 같습니다.A1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]A2 = [B, A, F, D, C, G, H, J, E, I]핵심 아이디어이 문제의 핵심은 pai

문제 개요완전 그래프(Complete Graph)가 주어졌을 때, 이 그래프에서 만들 수 있는 간선 분리 스패닝 트리(Edge Disjoint Spanning Tree)의 개수를 구하는 문제입니다. 간선 분리 스패닝 트리란, 집합에 속한 어떤 두 스패닝 트리도 서로 공유하는 간선이 단 하나도 없는 경우를 의미합니다.예를 들어 정점의 개수 N이 4라면, 출력 결과는 2가 됩니다. 4개의 정점으로 구성된 완전 그래프는 다음과 같습니다.위 그래프에서 추출할 수 있는 두 개의 간선 분리 스패닝 트리는 다음과 같습니다.핵심 아이디어N개의 정

양수와 음수가 섞여 있는 하나의 배열이 주어졌을 때, 연속된 부분 배열(subarray) 중에서 합이 가장 큰 값을 찾는 문제가 있습니다. 예를 들어 배열이 {-2, -5, 6, -2, -3, 1, 5, -6}이라면, 최대 부분 배열의 합은 7이며, 이는 {6, -2, -3, 1, 5}의 합입니다.이 문제는 분할 정복(Divide and Conquer) 기법을 사용하여 효율적으로 해결할 수 있습니다. 이 방식의 시간 복잡도는 O(n log n)으로, 단순한 브루트 포스 방식(O(n²))보다 훨씬 빠릅니다.알고리즘 동작 원리분할 정복

크기가 n인 배열이 주어졌을 때, 카운팅 정렬(counting sort) 기법을 활용하면 중앙값(median)과 최빈값(mode)을 효율적으로 구할 수 있습니다. 이 방법은 배열 원소의 값 범위가 제한적일 때 특히 유용합니다. 예를 들어 배열이 {1, 1, 1, 2, 7, 1}이라면 가장 자주 등장하는 값인 1이 최빈값이 됩니다. 중앙값과 최빈값이란? 중앙값(Median): 숫자들을 오름차순으로 정렬했을 때 정확히 가운데에 위치하는 값입니다. 최빈값(Mode): 데이터 목록에서 등장 횟수가 가장 많은 값입니다. 알고리즘 접근 방

문제 개요문자열이 하나 주어져 있고, 특정 문자의 모든 등장(occurrence)을 제거한 후 문자열에 남은 각 문자의 ASCII 값 합계를 최소화하는 것이 목표입니다. 예를 들어 hello라는 문자열이 주어지면 전체 ASCII 값의 합은 (104 + 101 + 108 + 108 + 111) = 532가 됩니다. 이제 각 문자별로 등장 횟수와 비용을 확인해 보겠습니다.h는 1번 등장하므로 비용은 1 × 104 = 104e는 1번 등장하므로 비용은 1 × 101 = 101l은 2번 등장하므로 비용은 2 × 108 = 216o는 1번

두 개의 숫자 문자열 A와 B가 주어졌을 때, 두 문자열을 완전히 동일하게 만들기 위해 필요한 최소 비용을 구하는 문제입니다. 이때 사용할 수 있는 연산은 단 하나뿐이며, 바로 문자열에서 숫자(자릿수)를 삭제하는 것입니다. 숫자를 삭제할 때 드는 비용은 해당 숫자의 값과 같습니다.예를 들어 A = 6789, B = 7859라고 가정해 보겠습니다. 두 문자열을 같게 만들려면 A에서 6을, B에서 5를 삭제해야 하므로 총 비용은 6 + 5 = 11이 됩니다.문제 접근 방식이 문제는 최장 공통 부분 수열(Longest Common Sub

두 개의 문자열 A와 B와 함께 두 개의 비용 값 CostA, CostB가 주어졌다고 가정해 봅시다. 목표는 A와 B를 동일하게 만드는 데 드는 최소 비용을 찾는 것입니다. 문자열에서 문자를 삭제할 수 있으며, 문자열 A에서 삭제하는 비용은 CostA, 문자열 B에서 삭제하는 비용은 CostB입니다.예를 들어 문자열 A = wxyz, B = wyzx이고 CostA는 10, CostB는 20이라고 합시다. 이때 출력 결과는 30이 됩니다. 두 문자열에서 문자 x를 각각 삭제하면 A와 B가 동일해지므로 총 비용은 10 + 20 = 30

문제 상황 두 사람이 함께 여행할 도시를 정하려고 합니다. 각자 선호하는 도시를 목록으로 작성했고, 우리는 두 사람 모두가 선택한 공통 도시를 찾아야 합니다. 이 연산은 집합의 교집합 성질과 매우 유사합니다. 두 목록을 각각 하나의 집합으로 간주한 뒤 교집합 연산을 수행하면 공통 요소를 쉽게 얻을 수 있습니다. C++ STL의 set_intersection 활용하기 C++ 표준 템플릿 라이브러리(STL)에는 정렬된 두 범위의 교집합을 구하는 set_intersection 함수가 제공됩니다. 이 함수는 입력 범위가 반드시 오름차순으

사각형 ABCD가 있을 때, 각 변의 중점 P와 Q의 좌표 그리고 사각형의 한 변 길이 L만 알고 있다고 가정해 보겠습니다.우리의 목표는 P와 Q의 좌표와 변의 길이 L만을 이용하여 네 꼭짓점 A, B, C, D의 좌표를 구하는 것입니다. 예를 들어, P가 (1, 0), Q가 (1, 2), L이 2라면 A, B, C, D는 각각 (0, 0), (0, 2), (2, 2), (2, 0)이 됩니다.발생 가능한 세 가지 경우사각형이 수평 방향인 경우: AD와 BC가 X축에 평행합니다.사각형이 수직 방향인 경우: AD와 BC가 Y축에 평행합

이진 트리가 하나 주어졌다고 가정해 보겠습니다. 우리의 과제는 이 트리 안에 포함된 단일 값 하위 트리(single valued subtree)의 개수를 세는 것입니다. 단일 값 하위 트리란 해당 하위 트리를 구성하는 모든 노드가 동일한 값을 가지는 경우를 의미합니다.예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.이 트리에는 총 네 개의 단일 값 하위 트리가 존재하며, 그 구성은 아래와 같습니다.해결 접근 방식이 문제는 상향식(bottom-up) 방식으로 효율적으로 해결할 수 있습니다. 재귀적으로 각 하위 트리를 방문할 때