선순회 결과로 BST 구성하기 선순회(preorder traversal) 결과가 하나 주어졌다고 가정해 보겠습니다. 이 순회 결과만으로 원래의 이진 탐색 트리(Binary Search Tree, BST)를 복원해야 합니다. 예를 들어 순회 결과가 [10, 5, 1, 7, 40, 50]과 같다면, 구성되는 트리는 다음과 같은 형태가 됩니다. 접근 방법: 스택 활용 선순회의 첫 번째 값은 항상 트리의 루트라는 성질을 이용하면, 스택(stack)을 사용해 O(n) 시간 복잡도로 트리를 구성할 수 있습니다. 알고리즘은 다음과 같습니다.

레벨 순서 순회(Level Order Traversal) 결과가 하나 주어졌다고 가정해 보겠습니다. 이 순회 결과만으로 원래의 트리를 복원해야 하는 것이 목표입니다. 예를 들어 순회 결과가 [7, 4, 12, 3, 6, 8, 1, 5, 10]이라면, 최종적으로 만들어지는 트리는 다음과 같은 형태가 됩니다.접근 방법이 문제는 재귀적(recursive) 접근 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.배열의 첫 번째 요소는 항상 루트(root)가 됩니다.두 번째 요소부터는 기존 BST의 삽입 규칙을 따릅니다. 즉,

이번 글에서는 주어진 이진 트리를 논리 AND(Logical AND) 속성을 만족하는 트리로 변환하는 방법을 C++ 코드와 함께 살펴보겠습니다.여기서 논리 AND 속성이란, 트리의 모든 내부 노드가 자신의 값으로 두 자식 노드 값의 AND 연산 결과를 갖는다는 의미입니다. 예를 들어 왼쪽 자식이 1이고 오른쪽 자식이 0이라면, 부모 노드의 값은 1 AND 0 = 0이 됩니다. 단, 모든 노드의 값은 0 또는 1로 제한됩니다.문제 해결 접근 방식이 문제는 후위 순회(Post-order Traversal)를 사용하면 깔끔하게 해결할 수

개요 이 튜토리얼에서는 이진 트리(Binary Tree)를 이중 연결 리스트(Doubly Linked List)로 변환하는 C++ 프로그램을 다룹니다. 변환 시 지켜야 할 조건은 다음과 같습니다. 트리의 left 포인터는 리스트의 prev(이전) 포인터 역할을 합니다. 트리의 right 포인터는 리스트의 next(다음) 포인터 역할을 합니다. 완성된 이중 연결 리스트의 노드 순서는 반드시 이진 트리의 중위 순회(Inorder Traversal) 결과와 동일해야 합니다. 접근 방법 이 문제는 매우 직관적인 방법으로 해결할 수 있

이 튜토리얼에서는 C++을 사용하여 이진 트리(Binary Tree)를 이중 연결 리스트(Doubly Linked List)로 변환하는 프로그램을 다룹니다.이진 트리가 주어졌을 때, 트리의 왼쪽(left)과 오른쪽(right) 포인터를 각각 이중 연결 리스트의 이전(prev) 포인터와 다음(next) 포인터로 변환해야 합니다. 또한 변환된 이중 연결 리스트의 순서는 반드시 원본 이진 트리의 중위 순회(Inorder Traversal) 결과와 동일해야 합니다.접근 방식이 문제는 여러 가지 방법으로 해결할 수 있지만, 여기서는 역방향

이 튜토리얼에서는 일반 이진 탐색 트리(Binary Search Tree, BST)를 균형 잡힌 이진 탐색 트리(Balanced BST)로 변환하는 프로그램을 C++로 구현하는 방법을 알아봅니다.변환 대상은 왼쪽 또는 오른쪽으로 한쪽으로 치우친(skewed) 형태의 이진 탐색 트리입니다. 치우친 BST는 트리의 높이가 노드 수만큼 깊어져 탐색, 삽입, 삭제 연산이 최악의 경우 O(n)까지 느려질 수 있습니다. 따라서 우리의 목표는 정해진 규칙에 따라 이러한 트리를 높이가 최소화된 균형 잡힌 BST로 재구성하는 것입니다.변환 접근 방

이 튜토리얼에서는 주어진 숫자를 음수 진법(negative base) 표현으로 변환하는 프로그램을 C++로 구현하는 방법을 알아봅니다. 음수 진법이란 밑(base)이 음수인 수 체계를 말합니다. 예를 들어 밑이 -3이라면, 숫자는 (-3)의 거듭제곱들의 합으로 표현됩니다. 흥미롭게도 음수 진법에서는 별도의 부호 없이 모든 정수(양수와 음수)를 표현할 수 있다는 장점이 있습니다. 우리에게는 하나의 숫자와 해당하는 음수 진법이 주어지며, 목표는 그 숫자를 음수 진법의 동등한 표현으로 변환하는 것입니다. 단, 이 글에서는 음수 진법 값

개요이 글에서는 두 가지 연산만을 허용하여 숫자 m을 n으로 변환할 때 필요한 최소 연산 횟수를 구하는 프로그램을 C++로 작성해 보겠습니다.두 개의 정수 m과 n이 주어졌을 때, 아래에 나열된 연산을 가장 적은 횟수로 사용하여 m을 n으로 바꾸는 것이 목표입니다.허용된 연산주어진 숫자에 2를 곱한다주어진 숫자에서 1을 뺀다접근 방법m에서 출발해 n을 만드는 대신, 역으로 n에서 m을 향해 거꾸로 진행하면 문제가 훨씬 단순해집니다.n이 홀수인 경우 → 정방향에서 마지막 연산이 −1이었음을 의미하므로, n에 1을 더해 한 단계 되돌아

이 튜토리얼에서는 길이 N의 숫자를 변환하여 임의의 한 자릿수가 최소 K번 이상 포함되도록 만드는 프로그램을 C++로 구현하는 방법을 살펴봅니다. 문제 개요 길이 N의 숫자 문자열이 하나 주어집니다. 우리가 해야 할 일은 주어진 숫자의 일부 자릿수를 변경하여, 어떤 한 자릿수든 최소 K번 이상 반복되도록 만드는 것입니다. 이때 자릿수 하나를 변경하는 비용은 원래 값과 새로운 값 사이의 절대 차이로 정의되며, 모든 변경 비용의 합을 계산한 뒤 그중 최소 비용과 함께 변환된 숫자를 출력해야 합니다. 접근 방식 이 문제는 다음과 같은 절

개요이 글에서는 C++를 사용해 문장을 해당하는 모바일 숫자 키패드 시퀀스로 변환하는 프로그램을 살펴봅니다.알파벳으로 이루어진 문자열이 주어졌을 때, 그 문자열을 실제로 입력하려면 어떤 숫자 키를 몇 번씩 눌러야 하는지를 나타내는 숫자 시퀀스를 출력하는 것이 목표입니다. 예전 버튼식 휴대폰에서 문자 메시지를 작성하던 방식과 동일한 원리입니다.키패드 매핑 규칙기존 휴대폰의 숫자 키패드에는 다음과 같이 알파벳이 배정되어 있습니다.2 → A, B, C3 → D, E, F4 → G, H, I5 → J, K, L6 → M, N, O7 → P

개요이 튜토리얼에서는 C++을 사용하여 문자열을 문자의 정사각형 행렬 그리드 형태로 변환하는 프로그램을 다룹니다.문자열이 입력으로 주어지면, 해당 문자열을 지정된 행과 열 개수를 가진 행렬 그리드 형식으로 출력하는 것이 우리의 목표입니다.동작 원리변환 과정은 다음과 같은 단계로 진행됩니다.1. 문자열 길이의 제곱근을 기준으로 행(row)과 열(column)의 크기를 계산합니다. 행에는 내림(floor), 열에는 올림(ceil)을 적용합니다.2. 행 × 열의 값이 문자열 길이보다 작으면, 행의 크기를 열과 동일하게 조정하여 모든 문자

이 튜토리얼에서는 C++에서 문자열을 16진수 ASCII 값으로 변환하는 프로그램을 구현하는 방법에 대해 알아보겠습니다.프로그래밍을 하다 보면 문자열 데이터를 16진수 형태로 표현해야 하는 경우가 종종 있습니다. 네트워크 통신에서 데이터를 전송하거나 디버깅 시 메모리 내용을 확인할 때 특히 유용합니다. 이번 글에서는 주어진 문자열의 각 문자를 해당하는 16진수 ASCII 값으로 변환하여 출력하는 코드를 살펴보겠습니다.변환 원리ASCII 문자는 각각 고유한 숫자 값을 가지며, 이 값을 16진수로 표현하면 두 자리 숫자가 됩니다. 예를

이 글에서는 C++을 활용해 하나의 트리를 짝수 개의 노드로 이루어진 포리스트(forest)로 변환하는 알고리즘을 소개합니다.N개의 노드로 구성된 트리가 주어졌을 때, 분리된 각각의 트리가 모두 짝수 개의 노드를 갖도록 만들기 위해 제거할 수 있는 간선의 최대 개수를 구하는 것이 목표입니다.접근 방식: 깊이 우선 탐색(DFS)이 문제는 DFS 한 번의 순회만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.루트 노드에서 DFS를 시작해 각 서브트리에 포함된 노드의 개수를 계산합니다.어떤 서브트리의 노드 수가 짝수라면, 해당

이 튜토리얼에서는 문자열과 정수 k가 주어졌을 때, ASCII 값이 k와 서로소(co-prime)인 모든 소문자를 대문자로 변환하는 프로그램을 C++로 구현하는 방법을 알아봅니다.문제 개요주어진 조건은 다음과 같습니다.하나의 문자열과 하나의 정수 값 k가 입력으로 제공됩니다.문자열을 처음부터 끝까지 순회하면서 각 문자의 ASCII 값을 확인합니다.해당 문자가 소문자(a~z)이고, 그 ASCII 값이 k와 서로소(최대공약수가 1)라면 대문자로 변환합니다.여기서 서로소란 두 수의 최대공약수(GCD)가 1인 경우를 의미합니다. 예를 들어

프로그래밍에서 문자열에 포함된 괄호가 서로 짝이 맞게 열리고 닫혔는지 확인하는 문제는 매우 자주 등장하는 고전적인 알고리즘 문제입니다. 이번 글에서는 C++의 스택(Stack) 자료구조를 활용하여 주어진 표현식의 괄호가 균형 잡혀 있는지(balanced) 판별하는 방법을 알아보겠습니다.문제 정의하나의 표현식(expression)이 주어졌을 때, 그 안에 포함된 괄호들이 올바르게 짝지어져 있는지 검사해야 합니다. 여기서 다루는 괄호의 종류는 소괄호 (), 중괄호 {}, 대괄호 [] 세 가지입니다.예를 들어 다음과 같은 두 개의 문자열

문제 개요계단이 n개 있다고 가정해 봅시다. 어떤 사람이 1번째 계단부터 시작해 n번째 계단까지 올라가려고 합니다. 이때 한 번에 최대 몇 칸의 계단을 오를 수 있는지(max)도 함께 주어집니다. 우리가 구해야 할 것은 이 조건 안에서 n번째 계단에 도달할 수 있는 모든 방법의 수입니다.예를 들어, 한 번에 최대 2칸까지 오를 수 있다고 해보겠습니다. 그렇다면 n번째 계단에 도달하는 방법은 다음 두 가지뿐입니다.(n-1)번째 계단에서 1칸 오르기(n-2)번째 계단에서 2칸 오르기따라서 다음과 같은 재귀 관계식(점화식)을 세울 수 있

파스칼의 삼각형(Pascals Triangle)은 이항계수(binomial coefficient)를 삼각형 배열 형태로 나타낸 것입니다. 맨 위 행은 n=0으로 번호가 매겨지며, 각 행 안의 숫자는 왼쪽부터 k=0으로 시작하여 번호가 붙습니다.각 숫자는 바로 윗행에 있는 두 수, 즉 현재 위치의 바로 위 값과 그 왼쪽 값을 더해서 구합니다. 또한 행 번호 n과 열 번호 k에 대해 조합 공식 C(n, k) = n! / (k! × (n−k)!)를 계산하는 방식으로도 동일한 결과를 얻을 수 있습니다.파스칼의 삼각형 출력 예시입력값이 10

문제 개요정렬된 배열이 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 일은 주어진 숫자 x가 해당 배열의 과반수 요소(majority element)인지 판별하는 것입니다.여기서 과반수 요소란 배열 전체 길이의 절반(n/2)보다 많이 등장하는 원소를 의미합니다. 예를 들어 배열이 {1, 2, 3, 3, 3, 3, 6}이고 x = 3이라면 답은 true입니다. 배열 안에 3이 네 번 등장하고, 배열의 크기는 7이므로 4 > 7/2 조건을 만족하기 때문입니다.접근 방법가장 직관적인 방법은 배열을 한 번 순회하면서 x의 등장

엑셀 열 번호 체계란?엑셀에서 열 이름은 알파벳 문자로 표현됩니다. A부터 시작해서 Z까지 진행된 후, 다시 AA, AB처럼 두 글자 조합으로 넘어가고 ZZ 이후에는 AAA, AAB와 같은 방식으로 계속 확장됩니다. 즉, 1번 열은 A, 26번 열은 Z, 27번 열은 AA에 해당합니다. 이번 글에서는 숫자로 주어진 열 번호를 실제 열 문자로 변환하는 방법을 알아보겠습니다. 예를 들어 열 번호가 80이라면 변환 결과는 CB가 됩니다.변환 알고리즘의 원리숫자 n이 주어졌을 때(예: n = 28), 먼저 n을 26으로 나눈 나머지를 구합

이 글에서는 임의의 수 n에 대해 n!의 결과값 끝에 붙는 0, 즉 후행 0(trailing zeros)의 개수를 구하는 방법을 알아봅니다.예를 들어 n = 5이면 5! = 120이므로 후행 0은 1개입니다. 20! = 2432902008176640000이므로 후행 0은 4개입니다.단순 계산 방식의 한계가장 직관적인 방법은 실제로 팩토리얼 값을 계산한 뒤 0의 개수를 세는 것입니다. 하지만 이 방법은 n이 조금만 커져도 자료형의 오버플로우 때문에 사용할 수 없습니다. 따라서 팩토리얼을 직접 계산하지 않고도 답을 구할 수 있는 수학적