이진 탐색 트리(BST)의 전위 순회(preorder traversal) 결과가 주어졌을 때, 루트보다 작은 요소의 개수를 찾는 문제를 다뤄보겠습니다.전위 순회에서는 트리의 루트를 가장 먼저 방문하기 때문에, 순회 결과의 첫 번째 요소가 곧 BST의 루트입니다. 이 특성만 활용하면 간단하게 해결할 수 있습니다. 예제를 통해 살펴보겠습니다.입력preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]출력3루트는 첫 번째 요소인 5이며, 5보다 작은 요소는 4, 2, 1로 총 3개입니다.알고리즘전위 순회 결과를 배열에

숫자로만 이루어진 문자열이 주어졌을 때, 그 안에서 만들 수 있는 짝수 부분 문자열의 개수를 구하는 문제입니다. 예제를 통해 살펴보겠습니다.입력num = 1234출력6주어진 문자열에서 만들 수 있는 짝수 부분 문자열은 다음과 같습니다.2124342341234핵심 아이디어어떤 수가 짝수인지 아닌지는 오직 마지막 자릿수에 의해서만 결정됩니다. 따라서 특정 위치의 숫자가 짝수라면, 그 위치를 끝으로 하는 모든 부분 문자열은 반드시 짝수가 됩니다. 인덱스 i(0부터 시작)에 있는 숫자가 짝수일 때, 그 위치를 끝으로 하는 부분 문자열은 정

예를 들어 이진 문자열 10011이 주어졌다고 가정해 보겠습니다. 이 문자열을 교대(alternate) 패턴의 이진 문자열로 만들려면 최소 2개의 문자를 뒤집어 10101로 바꿔야 합니다. 문제 접근 방법 교대 이진 문자열에는 두 가지 가능한 형태가 있습니다. 0으로 시작하는 경우(01010...)와 1로 시작하는 경우(10101...)입니다. 따라서 두 경우 각각에 대해 필요한 뒤집기 횟수를 계산한 뒤, 그중 더 작은 값을 반환하면 됩니다. 구체적인 예를 통해 살펴보겠습니다. 입력 binary = 10011 출력 2 문자열을 0으

문제 개요자석을 표현하는 숫자에서 1은 양극(N극)을, 0은 음극(S극)을 의미합니다.각 자석은 두 개의 극을 가지며, 10 또는 01의 형태로 표현됩니다. 서로 이끌어당기는(인력이 작용하는) 자석들은 하나의 그룹을 이룰 수 있으며, 서로 마주 보는 면의 극이 다른 자석들이 같은 그룹에 속하게 됩니다.여기서 N개의 자석이 주어졌을 때, 이 자석들로 형성할 수 있는 그룹의 개수를 구해야 합니다.핵심 규칙은 간단합니다. 서로 다른 자석이 나란히 배치될 때마다 새로운 그룹이 형성되며, 이 경우 그룹 개수를 하나씩 증가시키면 됩니다.예시입

문제 소개숫자로 이루어진 배열이 주어졌을 때, 원소의 합이 3으로 나누어 떨어지는 크기 2와 크기 3의 그룹이 각각 몇 개 존재하는지 구해야 합니다. 해결 방법은 간단합니다. 배열에서 두 개씩, 세 개씩 원소를 조합하여 각 그룹의 합을 계산하고, 그 합이 3으로 나누어 떨어지는지 확인하면 됩니다.먼저 예시를 살펴보겠습니다.입력arr = [1, 2, 3, 4]출력4합이 3으로 나누어 떨어지는 조합은 다음과 같이 총 4개입니다.[1, 2] → 합 = 3 [2, 4] → 합 = 6 [1, 2, 3] → 합 = 6 [2, 3, 4] → 합

배열과 인덱스 범위가 주어졌을 때, 해당 범위 안에서 서로 인접하면서 값이 같은 요소가 몇 개 있는지 세는 문제입니다. 이 문제는 단순 반복문 하나로 효율적으로 해결할 수 있습니다.먼저 예시를 통해 문제를 이해해 보겠습니다.예시입력arr = [1, 2, 2, 2, 3, 3, 4] lower = 1 upper = 5출력3인덱스 1부터 5 사이에서 인접한 요소들을 비교하면, (2, 2), (2, 2), (3, 3)으로 총 3쌍이 같은 값을 가지므로 결과는 3이 됩니다.알고리즘배열과 탐색할 인덱스 범위(lower, upper)를 초기화합

숫자 n이 주어졌을 때, 1부터 n까지의 정수 중 이진수 표현에서 세트 비트(set bit, 값이 1인 비트)의 개수가 홀수인 정수가 몇 개 있는지 구하는 문제입니다. 예시를 통해 살펴보겠습니다.입력n = 10출력51부터 10 사이에는 이진수 표현에서 세트 비트 개수가 홀수인 정수가 총 5개 존재합니다. 실제로 확인해 보면 1(1), 2(10), 4(100), 7(111), 8(1000)이 해당됩니다.알고리즘숫자 N을 초기화합니다.이진수 형태에서 세트 비트의 개수를 세는 함수를 작성합니다.결과를 저장할 카운트 변수를 0으로 초기화합

이 튜토리얼에서는 C++를 사용하여 주어진 두 점 사이에 존재하는 정수 좌표점(격자점)의 개수를 구하는 프로그램을 작성해 보겠습니다. 핵심 아이디어 두 점 사이의 정수점 개수는 다음 공식으로 간단하게 계산할 수 있습니다. gcd(abs(x1 - x2), abs(y1 - y2)) - 1 여기서 gcd는 최대공약수(greatest common divisor)를 의미합니다. 다만, 두 점을 잇는 선분이 좌표축에 평행한 특수한 경우에는 아래와 같이 따로 처리해야 합니다. x축에 평행한 경우: 두 점의 y좌표가 같으므로 정수점 개수는 a

방정식 x1 + x2 + … + xn = k의 정수 해의 개수를 구하는 문제는 조합론의 별과 막대(stars and bars) 기법으로 간단하게 해결할 수 있습니다.핵심 공식음이 아닌 정수 해(변숫값이 0 이상인 경우)의 개수는 C(n+k−1, k) 입니다.양의 정수 해(변숫값이 1 이상인 경우)의 개수는 C(k−1, n−1) 입니다.문제에서 제한 조건 없이 모든 정수 해를 요구한다면, 위 두 가지 경우의 수를 더하면 됩니다.예제입력n = 4k = 7출력140n = 4, k = 7일 때 음이 아닌 정수 해의 개수는 C(10, 7)

문자열이 주어졌을 때, 각 문자의 오른쪽에 있는 더 큰 문자의 개수를 세는 것은 코딩 테스트에서 자주 등장하는 기본적인 문제입니다. 예시를 통해 자세히 살펴보겠습니다.입력string = abc출력2 1 0a의 오른쪽에는 a보다 큰 문자가 2개(b, c) 있으므로 결과는 2입니다.b의 오른쪽에는 b보다 큰 문자가 1개(c) 있으므로 결과는 1입니다.c의 오른쪽에는 c보다 큰 문자가 없으므로 결과는 0입니다.알고리즘문자열을 초기화합니다.각 문자의 개수를 저장할 배열을 초기화합니다.두 개의 중첩 반복문을 사용해 문자열을 순회합니다.한 번

문제 개요주어진 숫자의 이진(binary) 표현에서 선행 0(leading zeroes)의 개수를 구하는 문제입니다. 이때 전체 비트 수는 32비트라고 가정합니다.예를 들어 살펴보겠습니다.입력5출력29숫자 5의 이진 표현은 00000...00101입니다. 실제로 값이 채워진 비트는 맨 뒤의 3개뿐이므로, 나머지 앞부분에 해당하는 선행 0은 총 29개입니다.알고리즘숫자 n을 초기화합니다.n의 이진 표현을 구합니다.전체 비트 수(32)에서 n의 이진 표현 길이를 뺍니다.계산된 결과를 반환합니다.구현다음은 위 알고리즘을 C++로 구현한

개요이 튜토리얼에서는 N-진 트리(n-ary tree)에서 모든 노드의 하위 트리에 속한 리프 노드(leaf node)의 개수를 구하는 프로그램을 작성해 보겠습니다.N-진 트리가 주어졌을 때, 각 노드를 루트로 하는 하위 트리에 포함된 리프 노드의 수를 계산해야 합니다. 먼저 예시를 통해 문제를 살펴보겠습니다.입력N = 8 tree = [[2, 3], [], [4, 5, 6], [7, 8], [], [], [], []]출력1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->

자연수 N이 주어졌을 때, 최악의 경우 순열(permutation)을 완전히 추측하는 데 필요한 이동 횟수를 구하는 것이 이 글의 목표입니다. 순열의 각 위치를 차례대로 확인하며 가능한 모든 경우를 고려하면, 필요한 총 이동 횟수는 아래와 같은 규칙으로 계산할 수 있습니다.핵심 아이디어는 간단합니다. 1부터 n까지의 각 i에 대해 i × (n − i)를 모두 더한 뒤, 마지막에 n을 한 번 더해 주면 됩니다.예시입력:9출력:129n이 9일 때 각 항을 계산하면 8 + 14 + 18 + 20 + 20 + 18 + 14 + 8 + 0

스테핑 넘버(Stepping Number)란 인접한 두 자릿수의 차이가 정확히 1인 숫자를 말합니다. 예를 들어 123, 321, 121 같은 숫자가 여기에 해당합니다. 자릿수 n이 주어졌을 때, n자리 스테핑 넘버가 총 몇 개 있는지 구하는 문제를 C++로 해결해 보겠습니다.문제 예시입력2출력172자리 숫자 중 가장 작은 수는 10, 가장 큰 수는 99입니다. 이 범위 안에는 12, 23, 34, 45, 56, 67, 78, 89, 98 등 총 17개의 스테핑 넘버가 존재합니다.알고리즘자릿수 n을 초기화합니다.개수를 저장할 변수

배열과 특정 요소의 인덱스가 주어졌을 때, 그 요소의 오른쪽에 위치하면서 값이 더 큰 요소가 몇 개인지 세는 문제를 풀어보겠습니다. 이러한 요소는 흔히 NGE(Next Greater Element)라고 불립니다.문제 예시입력arr = [2, 3, 5, 1, 4, 2, 6] index = 3출력3인덱스 3에 해당하는 대상 요소는 1입니다. 이 요소의 오른쪽에는 4, 2, 6 총 세 개의 요소가 있으며, 모두 1보다 큰 값입니다. 따라서 정답은 3이 됩니다.알고리즘 접근 방법이 문제는 단순한 선형 탐색으로 해결할 수 있습니다. 절차는

n-ary 트리와 하나의 숫자가 주어졌을 때, 해당 숫자보다 큰 값을 가진 노드의 개수를 세는 문제입니다. 트리를 순회하면서 조건에 맞는 노드만 카운트하면 되므로, 재귀 호출을 활용하면 간단하게 해결할 수 있습니다.먼저 예제를 통해 문제를 이해해 보겠습니다.입력tree = [[4], [1, 2], [3, 5]] n = 2출력3위 트리에서 값이 2(n)보다 큰 노드는 3개입니다.알고리즘n-ary 트리를 초기화합니다.카운트 변수를 0으로 초기화합니다.현재 노드의 값이 n보다 크면 카운트를 1 증가시킵니다.현재 노드의 모든 자식 노드를

이번 튜토리얼에서는 합 방정식(sum equation)의 음이 아닌 정수(non-negative integer) 해가 총 몇 개인지 구하는 프로그램을 C++로 작성해 보겠습니다.문제에서 다루는 방정식은 다음과 같습니다.x + y + z = n자연수 n이 주어졌을 때, 이 방정식을 만족하는 음이 아닌 정수(x, y, z ≥ 0) 조합이 몇 가지 존재하는지 찾아야 합니다. 예제를 통해 살펴보겠습니다.입력 및 출력 예시입력2출력6n = 2일 때 가능한 해는 다음 6가지입니다.0 0 20 1 10 2 01 0 11 1 02 0 0알고리즘가

직선의 방정식 y = mx + c가 주어졌을 때, 배열에 있는 값들로 만들 수 있는 순서쌍(ordered pair) 중 이 방정식을 만족하는 쌍의 개수를 구하는 문제입니다. 배열과 기울기 m, 절편 c가 입력으로 주어지며, 조건을 만족하는 순서쌍의 개수를 출력해야 합니다.먼저 예시를 통해 문제를 살펴보겠습니다.입력 예시arr = [1, 2, 3] m = 1 c = 1출력 예시2위 예시에서 방정식 y = x + 1을 만족하는 순서쌍은 다음과 같습니다.(2, 1) (3, 2)배열의 각 원소를 x값으로 대입했을 때, 결과인 y값도 같은

두 개의 숫자 N과 K가 주어졌을 때, 1부터 N까지의 자연수 중에서 서로 다른 두 수의 합이 K로 나누어지는 쌍(pair)의 개수를 세는 문제입니다. 예시를 통해 살펴보겠습니다.입력N = 3K = 2출력1합이 K로 나누어지는 쌍은 (1, 3) 하나뿐입니다. 두 수의 합이 4이며, 이는 2로 나누어떨어지기 때문입니다. 반면 (1, 2)의 합은 3, (2, 3)의 합은 5로 2로 나누어지지 않습니다.알고리즘N과 K를 초기화합니다.1부터 N까지의 자연수를 생성하여 배열에 저장합니다.카운트 변수를 0으로 초기화합니다.두 개의 반복문을 사

배열이 주어졌을 때, 두 원소의 합이 2의 거듭제곱(1, 2, 4, 8, ...)이 되는 쌍(pair)의 개수를 구하는 문제입니다. 먼저 간단한 예시를 통해 문제를 이해해 보겠습니다.예시입력arr = [1, 2, 3]출력1합이 2의 거듭제곱이 되는 쌍은 (1, 3) 단 하나뿐입니다. 1 + 3 = 4이고, 4는 2²이므로 조건을 만족합니다.알고리즘이 문제는 브루트 포스(Brute Force) 방식으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.배열을 임의의 숫자들로 초기화합니다.카운트 변수를 0으로 초기화합니다.두 개