이 문제의 목표는 주어진 숫자 n 이하의 범위에서, 첫 번째 비트(최상위 비트)와 마지막 비트(최하위 비트)만 1로 설정되어 있고 나머지 비트는 모두 0인 숫자들을 모두 찾아 출력하는 것입니다. 컴퓨터 언어에서 설정된 비트(set bit)란 값이 1인 비트를 의미하며, 설정되지 않은 비트(unset bit)는 값이 0인 비트를 뜻합니다. 입력: num의 값 = 5 출력: 1 3 5    1은 이진수로 1에 해당합니다    3은 이진수로 11에 해당합니다   &

트리의 중위 순회(inorder)와 전위 순회(preorder) 결과가 주어졌을 때, 이를 이용해 후위 순회(postorder)를 계산하고 출력하는 프로그램을 만들어 보겠습니다.입력:중위 순회 in[] = {4, 2, 5, 1, 3, 6}전위 순회 pre[] = {1, 2, 4, 5, 3, 6}출력:후위 순회 post[] = {4, 5, 2, 6, 3, 1}동작 원리이 문제는 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.전위 순회의 첫 번째 원소는 항상 현재 서브트리의 루트(root)입니다.중위 순회에서 루트 값

연결 리스트(Linked List)가 주어졌을 때, 스택(Stack) 자료구조를 활용하여 리스트의 마지막 요소부터 첫 번째 요소까지 역순으로 출력하는 프로그램을 만들어 보겠습니다.입력 : 10 -> 5 -> 3 -> 1 -> 7 -> 9 출력 : 9 -> 7 -> 1 -> 3 -> 5 -> 10핵심 아이디어는 간단합니다. 연결 리스트를 순회하면서 모든 데이터를 스택에 차례대로 저장(push)한 뒤, 스택의 최상단(top)부터 요소를 하나씩 꺼내면서(pop) 출력하면 자연스럽게 역

이 글에서 다룰 문제는 다음과 같습니다. 주어진 수 N이 소수가 아니라면, 2부터 시작하는 소수를 차례대로 더해가면서 처음으로 소수가 되는 값을 찾아 출력하는 것입니다.입력: N = 6 출력: 11문제 이해 및 풀이 과정예시를 통해 동작 원리를 살펴보겠습니다.N = 6은 소수가 아닙니다.첫 번째 소수인 2를 더하면 6 + 2 = 8이 되지만, 8 역시 소수가 아닙니다.다음 소수인 3을 더하면 8 + 3 = 11이 되고, 11은 소수입니다.따라서 최종 결과로 11을 출력합니다.알고리즘 k = 2부터 k <= i까지 반복:

최대공약수(GCD)란? GCD(Greatest Common Divisor, 최대공약수)는 0을 제외한 두 개 이상의 정수를 모두 나누어 떨어지게 하는 가장 큰 정수를 말합니다. 예를 들어 48과 180의 최대공약수를 소인수분해를 이용해 구해 보겠습니다. 48 = 2 × 2 × 2 × 2 × 3180 = 2 × 2 × 3 × 3 × 5 두 수가 공통으로 가진 소인수는 2, 2, 3이므로 최대공약수는 2 × 2 × 3 = 12입니다. 문제 이해하기 정수 N과 K가 주어졌을 때, 같은 줄에 있는 임의의 두 숫자를 골라도 그 최대공약수가

두 개의 정수 x와 y가 주어졌을 때, 두 수의 k번째 공약수(kth common factor)를 찾아 출력하는 문제를 살펴보겠습니다. 이 문제는 반복문과 조건문만으로 해결할 수 있는 대표적인 기초 알고리즘 문제입니다. 문제 이해하기 예를 들어 x = 12, y = 18이라고 가정해 봅시다. 각 수의 약수는 다음과 같습니다. 12의 약수 : 1, 2, 3, 4, 6, 12 18의 약수 : 1, 2, 3, 6, 9, 18 따라서 두 수의 공약수는 1, 2, 3, 6입니다. 만약 k = 3이라면, 세 번째 공약수인 3을 출력해야 합

뉴먼-콘웨이 수열(Newman-Conway Sequence)은 재귀적인 점화식을 통해 생성되는 흥미로운 정수 수열입니다. 이 수열은 다음과 같은 형태로 나타납니다.1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12수열의 각 항은 앞선 항들의 값을 참조하여 결정되기 때문에, 계산 과정 자체가 하나의 재귀 구조를 이루는 것이 특징입니다.뉴먼-콘웨이 수열의 점화식n개의 항으로 이루어진 뉴먼-콘웨이 수열을 생성하는 공식은 다음과 같습니다.P(n) = P(P(n - 1)) + P(n - P(n - 1))단, P(1)

문제 개요k개의 요소로 구성된 배열이 주어졌을 때, 프로그램은 그중 n개의 가장 작은 요소를 찾아 원래 등장 순서 그대로 출력해야 합니다.예를 들어 다음과 같은 입출력을 생각해 볼 수 있습니다.입력 : arr[] = {1, 2, 4, 3, 6, 7, 8}, k=3 출력 : 1, 2, 3여기서 k가 3이라는 것은 배열에서 가장 작은 3개의 요소를 원래 순서대로, 즉 1, 2, 3 순으로 표시해야 한다는 의미입니다.알고리즘 i=0부터 i<k까지 반복하며 arr[i] 출력 STOP예제 코드다음은 위 알고리즘을 C 언어로 구현한 전체

문제 개요방정식이 주어졌을 때, 프로그램은 a + b ≤ n을 만족하면서 동시에 a + b가 x로 나누어 떨어지는 모든 a의 값을 찾아 출력해야 합니다.예를 들어 b = 10, x = 9, n = 40이라면, a + 10이 40 이하이면서 9의 배수가 되는 경우들을 찾아 해당하는 a 값을 구하는 것입니다.알고리즘START Step 1 -> 변수 b=10, x=9, n=40과 flag=0, divisible을 선언한다. Step 2 -> 반복문 실행: divisible = (b / x + 1) * x 부터 시작하여 &nbs

이번 문제에서는 재귀(Recursion) 방식을 사용하여 주어진 패턴을 화면에 출력하는 방법을 알아봅니다.재귀 함수란 자기 자신을 여러 번 호출하는 함수를 의미합니다. 하나의 프로그램 안에는 재귀 함수가 여러 개 존재할 수 있으며, 재귀를 활용하면 반복문 없이도 간결하게 문제를 해결할 수 있습니다. 다만 재귀 함수는 호출 구조가 복잡해질 수 있어 동작 방식을 정확히 이해하는 것이 중요합니다.알고리즘패턴을 출력하기 위해 두 개의 함수를 사용합니다. 하나는 별(*)을 한 줄에 출력하는 함수이고, 다른 하나는 줄바꿈과 함께 전체 패턴을

문제 소개 이번 글에서는 행렬 확률(Matrix Probability) 문제를 다뤄보겠습니다. 크기가 m×n인 직사각형 행렬이 하나 주어져 있으며, 현재 칸에서는 왼쪽, 오른쪽, 위, 아래 네 방향으로 각각 동일한 확률(1/4)만큼 이동할 수 있습니다. 목표는 시작 위치 M[x, y]에서 정확히 N번 이동한 뒤에도 행렬 경계를 벗어나지 않고 행렬 안에 머무를 확률을 계산하는 것입니다. 접근 방법: DFS 기반 재귀 탐색 이 문제는 DFS(깊이 우선 탐색)와 유사한 방식으로 해결할 수 있습니다. 현재 위치에서 이동 가능한 네 방향을

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 아래에 제시된 두 개의 코드 조각은 모두 이중 중첩 루프로 구성되어 있습니다. 과연 어느 쪽이 더 빠르게 실행될까요? 단, 컴파일러가 코드를 최적화하지 않는다는 조건을 전제로 합니다.코드 조각 1for(int i = 0; i < 10; i++){    for(int j = 0; j<100; j++){       //code    } }코드 조각 2for(int i = 0; i < 100; i++){ &n

이번 글에서는 팬케이크 정렬(Pancake Sort)이라는 독특한 정렬 문제를 살펴보겠습니다. 이름처럼 팬 위에서 팬케이크를 뒤집는 모습에서 착안한 알고리즘으로, 문제 자체는 매우 단순합니다.팬케이크 정렬이란?정렬해야 할 배열이 하나 주어지지만, 사용할 수 있는 연산은 오직 rev(arr, i) 하나뿐입니다. 이 연산은 배열의 첫 번째 요소(인덱스 0)부터 i번째 위치까지의 요소들을 뒤집는 역할을 합니다. 즉, 일반적인 스왑(swap)이나 다른 정렬 기법 없이 앞부분 뒤집기만으로 전체 배열을 오름차순으로 정렬해야 하는 것입니다.팬케

이번 글에서는 흥미로운 C/C++ 퍼즐 하나를 살펴보겠습니다. 아래와 같은 프로그램이 주어졌을 때, 출력 결과가 무엇이고 그 이유는 무엇인지 맞혀보시기 바랍니다.예제 코드#include<iostream> using namespace std; int main() { int x = 0xab; ~x; cout << hex << x; }과연 출력 결과는 무엇일까요? ~x는 비트 보수(complement) 연산을 수행하므로, 16진수 형태로 보수된 결과가 출력될 것이라고 생각하기 쉽습니다

미로 속 쥐(Rat in a Maze) 문제는 백트래킹(backtracking) 기법을 배울 때 가장 널리 알려진 대표 알고리즘 문제 중 하나입니다. 이 글에서는 여기에 약간의 변형을 더한, 점프가 허용되는 미로 문제를 살펴보겠습니다. N×N 크기의 미로 M이 주어졌다고 가정합니다. 시작 지점은 좌측 상단 모서리인 M[0, 0]이고, 목적지는 우측 하단 모서리인 M[N-1, N-1]입니다. 쥐 한 마리를 시작 지점에 놓았을 때, 이 쥐가 목적지에 도달할 수 있는 경로를 찾는 것이 우리의 목표입니다. 일반적인 미로 문제와 달리, 이

문제 개요흥미로운 알고리즘 문제를 하나 살펴보겠습니다. 크기가 n인 이진 배열(binary array)이 주어져 있다고 가정합니다. 단, n은 3보다 커야 합니다. 배열에서 1(true)은 활성(active) 상태를, 0(false)은 비활성(inactive) 상태를 의미합니다. 함께 주어진 숫자 k만큼의 날이 지난 뒤, 배열에 남아 있는 활성 셀과 비활성 셀의 개수를 구하는 것이 목표입니다.상태 변화 규칙은 다음과 같습니다. 매일 i번째 셀은 왼쪽 셀과 오른쪽 셀의 값이 서로 다르면 활성(1)이 되고, 같으면 비활성(0)이 됩니다

연결 리스트로 표현된 숫자에 1 더하기이 글에서는 연결 리스트(Linked List)에 저장된 숫자에 1을 더하는 방법을 살펴보겠습니다. 연결 리스트에서는 숫자의 각 자릿수가 개별 노드에 저장됩니다. 예를 들어 숫자가 512라면 다음과 같은 형태로 표현됩니다.512 = (5)-->(1)-->(2)-->NULL증가(increment) 함수에 리스트를 전달하면, 함수는 1을 더한 결과를 담은 새로운 리스트를 반환합니다. 여기서는 C++ STL의 list 컨테이너를 사용하여 구현합니다. 동작 원리를 더 명확히 이해하기 위

이번 장에서는 흥미로운 문제 하나를 살펴보겠습니다. 하나의 숫자가 주어졌을 때 이 숫자를 1만큼 증가시키는 것은 겉보기에 아주 간단한 작업입니다. 하지만 여기서는 숫자를 배열 형태로 다룬다는 점이 핵심입니다. 숫자의 각 자릿수가 배열의 개별 요소로 저장되며, 예를 들어 숫자가 512라면 {5, 1, 2}와 같이 저장됩니다. 또한 반복문 대신 재귀(recursion) 방식을 사용하여 이 숫자를 1 증가시켜야 합니다. 그럼 알고리즘을 통해 구체적인 동작 과정을 살펴보겠습니다. 알고리즘 increment(arr, n, index) in

문제 개요이번 글에서는 두 배열의 요소를 서로 더해 새로운 배열에 저장하는 문제를 다룹니다. 단순한 덧셈처럼 보이지만, 반드시 지켜야 할 제약 조건이 있습니다. 조건은 다음과 같습니다.덧셈은 두 배열 모두 0번째 인덱스부터 시작합니다.합이 한 자리 수를 초과하면 각 자릿수로 분리하여 해당 위치에 순서대로 저장합니다.길이가 더 긴 배열의 남은 요소들은 그대로 결과 배열에 저장합니다(단, 여러 자릿수라면 분리해서 저장).그럼 이 문제를 해결하기 위한 알고리즘부터 살펴보겠습니다.알고리즘addArrayConstraints(arr1, arr

문제 개요이 글에서는 n개의 숫자로 이루어진 배열이 주어졌을 때, 배열의 모든 요소를 이어 붙여 만든 하나의 정수가 3으로 나누어 떨어지는지 확인하는 방법을 다룹니다.예를 들어 배열 요소가 {15, 24, 23, 13}이라면, 이 요소들을 차례대로 연결하여 15242313이라는 정수를 만들 수 있습니다. 이 수는 3으로 나누어 떨어집니다.핵심 아이디어거대한 숫자를 직접 만들 필요는 없습니다. 수학적으로 잘 알려진 성질에 따르면, 어떤 수가 3으로 나누어 떨어지려면 그 수의 각 자릿수의 합이 3으로 나누어 떨어져야 합니다.배열 요소들