이 글에서는 임의의 숫자에 대한 팩토리얼(계승) 결과에서 후행 0(끝자리 0)의 개수를 계산하는 방법을 살펴보겠습니다. 예를 들어 n = 5이면 5! = 120이므로 후행 0은 하나뿐입니다. 20!의 경우 20! = 2432902008176640000이므로 후행 0은 4개입니다.문제 접근 방식가장 간단한 방법은 실제로 팩토리얼 값을 계산한 뒤 0의 개수를 세는 것입니다. 하지만 이 방법은 n의 값이 커지면 오버플로우가 발생하여 실패하게 됩니다. 따라서 우리는 다른 접근 방식을 사용해야 합니다.핵심 아이디어는 다음과 같습니다. 후행

이 글에서는 서로 다른 연결 리스트(Linked List)에 저장된 두 숫자를 더하는 방법을 살펴보겠습니다. 연결 리스트에는 숫자의 각 자릿수가 한 노드씩 저장됩니다. 예를 들어 숫자 512는 다음과 같이 표현됩니다.512 = (5)-->(1)-->(2)-->NULL이러한 형태의 두 개의 리스트가 주어졌을 때, 우리의 목표는 두 리스트를 더하여 그 합계를 계산한 결과를 얻는 것입니다. 여기서는 C++ STL의 list 컨테이너를 활용합니다. 구현 내용을 더 잘 이해할 수 있도록 먼저 알고리즘부터 확인해 보겠습니다.알

이번 글에서는 간단한 프로그래밍 문제를 다뤄보겠습니다. 주어진 리스트(배열) 안에서 회문(Palindrome)에 해당하는 모든 숫자를 찾아 출력하는 것이 목표입니다.회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열이나 숫자를 의미합니다. 예를 들어 121, 111, 858처럼 숫자를 거꾸로 뒤집어도 원래 값과 동일한 수가 바로 회문 숫자입니다.접근 방식해결 방법은 매우 직관적입니다. 리스트의 각 숫자를 하나씩 꺼내 해당 숫자가 회문인지 검사하고, 회문이라면 화면에 출력하면 됩니다.알고리즘: getAllPalindrome(ar

이 글에서는 사용자가 입력한 비트 수 n에 대해, 왼쪽 절반과 오른쪽 절반의 비트 합이 서로 같은 모든 이진수를 생성하는 방법을 알아봅니다.예를 들어 5비트 숫자 10001을 살펴보겠습니다. 왼쪽 절반 10과 오른쪽 절반 01의 각 자릿수 합은 모두 1로 동일합니다. 바로 이런 조건을 만족하는 숫자들을 모두 찾아내는 것이 목표입니다.알고리즘 개요핵심 아이디어는 재귀적으로 양쪽 절반을 동시에 채워나가면서, 현재까지의 좌우 비트 합 차이(diff)를 추적하는 것입니다. 남은 비트 수로 차이를 메울 수 없는 경우에는 가지치기를 하여 탐색

이 글에서는 주어진 범위 [L, R] 안에서 만들 수 있는 서로소(co-prime) 쌍의 개수를 구하는 방법을 알아봅니다. 단, 하나의 숫자는 오직 한 개의 쌍에만 포함될 수 있다는 조건이 있습니다.서로소(Co-prime)란?서로소란 두 수의 공약수가 1뿐인, 즉 최대공약수(GCD)가 1인 숫자들의 조합을 의미합니다. 예를 들어 3과 4는 공약수가 1뿐이므로 서로소 관계입니다.예를 들어 하한이 1, 상한이 6이라면 만들 수 있는 서로소 쌍은 다음과 같이 세 가지입니다: (1, 2), (3, 4), (5, 6).접근 방법핵심 아이디어

이번 글에서 다룰 문제는 다음과 같습니다. 자릿수 N과 밑수(base) B가 주어졌을 때, 선행 0(leading zero)이 없는 N자리 숫자가 총 몇 개인지 세는 것입니다.예를 들어 N이 2이고 B가 2라고 가정해 보겠습니다. 이 경우 만들 수 있는 두 자리 값은 00, 01, 10, 11로 네 가지입니다. 하지만 선행 0이 없어야 한다는 조건을 만족하는 값은 10과 11뿐이므로, 유효한 숫자는 두 개입니다.수학적 접근 방법밑수가 B라면 사용할 수 있는 각 자리의 숫자는 0부터 B−1까지 총 B개입니다. 따라서 선행 0을 포함하

이번 글에서는 주어진 문자열로 만들 수 있는 모든 길이의 문자열을 생성하는 방법을 살펴보겠습니다. 이 기법은 각 문자의 조합을 비트마스킹으로 추출한 뒤, 추출된 문자들의 순열을 모두 출력합니다. 예를 들어 입력 문자열이 ABC라면 다음과 같은 결과가 생성됩니다.{A, B, C, AB, BA, BC, CB, CA, AC, ABC, ACB, BAC, BCA, CAB, CBA}길이가 n인 문자열에서 만들 수 있는 부분 집합(조합)은 공집합을 제외하면 총 2n − 1개이며, 각 조합마다 가능한 모든 순열을 추가로 생성하는 것이 이 알고리즘

C나 C++에서 system() 함수를 활용하면 의외로 강력한 작업들을 수행할 수 있습니다. 이번 글에서는 system() 함수를 사용했을 때 얻을 수 있는 흥미로운 결과들을 살펴보겠습니다.system() 함수는 Windows, Linux, macOS 등 주요 운영체제에서 모두 사용할 수 있으며, 명령 프롬프트(커맨드 라인)에서 실행 가능한 시스템 명령어를 C/C++ 코드 내에서 직접 호출하는 역할을 합니다.여기서는 system() 함수의 두 가지 대표적인 활용 예시를 소개합니다. 첫 번째는 C++ 프로그램으로 IP 설정 정보를 조

이 글에서는 n번째 피보나치 수가 10의 배수인지 효율적으로 판별하는 방법을 알아봅니다. 피보나치 수열은 다음과 같습니다. {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987} 여기서 15번째(0부터 셀 때) 피보나치 수는 10으로 나누어 떨어집니다. 따라서 n이 15일 경우 참(true)을 반환하면 됩니다. 단순한 접근법의 한계 가장 직관적인 방법은 주어진 항까지 피보나치 수를 모두 계산한 뒤, 해당 값이 10으로 나누어 떨어지는지 확인하는 것입니다. 하지만 이

이번 글에서는 1부터 n까지의 이진수를 생성하는 아주 흥미로운 방법을 소개합니다. 핵심 아이디어는 자료구조 중 하나인 큐(Queue)를 활용하는 것입니다.동작 방식은 다음과 같습니다. 처음에 큐에는 첫 번째 이진수인 1만 넣어둡니다. 그다음 큐에서 요소를 하나 꺼내(dequeue) 출력하고, 방금 꺼낸 문자열 뒤에 0을 붙인 값과 1을 붙인 값을 각각 만들어 다시 큐에 삽입(enqueue)합니다. 이 과정을 n번 반복하면 1부터 n까지의 모든 이진수가 순서대로 출력됩니다.알고리즘genBinaryNumbers(n)Begin 빈

이 글에서는 n보다 작은 모든 소수를 효율적으로 구하는 흥미로운 방법을 살펴봅니다. 핵심 아이디어는 윌슨의 정리(Wilsons theorem)입니다. 윌슨의 정리에 따르면, 어떤 수 k가 소수일 때 ((k - 1)! + 1) mod k의 값은 반드시 0이 됩니다. 즉, 이 성질을 역으로 이용하면 특정 수가 소수인지 판별할 수 있습니다.다만 이 방법에는 중요한 제약이 있습니다. C나 C++처럼 고정 크기 정수형을 사용하는 언어에서는 그대로 적용하기 어렵습니다. 팩토리얼은 기하급수적으로 커지기 때문에, 예를 들어 13!만 되어도 32비

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 하나의 이진 트리가 주어졌을 때, 이 트리를 반시계 방향(anti-clockwise) 나선형으로 순회하는 것입니다.순회 과정은 아래 그림과 같습니다.위 트리를 반시계 방향으로 순회하면 다음과 같은 순서로 노드를 방문하게 됩니다.순회 결과: 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7알고리즘 개념핵심 아이디어는 간단합니다. 트리의 최상위 레벨(1)부터 최하위 레벨(트리의 높이)까지 두 개의 포인터 i와 j를 사용하여 양쪽 끝에서 안쪽으로

호 길이 계산 개요이번 글에서는 주어진 각도를 이용해 호(arc)의 길이를 구하는 방법을 알아보겠습니다. 하나의 원과 그 반지름이 주어져 있으며, 목표는 반지름과 각도 두 값을 활용해 호의 길이를 계산하는 것입니다. 이때 각도는 도(degree) 단위로 주어진다고 가정합니다.호 길이 공식위 그림에서 r(반지름)과 x(중심각)가 주어졌을 때, 구해야 할 값은 호의 길이 L입니다. 공식은 아래와 같습니다.𝐿 = 2𝜋𝑟 × (𝑥/360)공식의 원리는 간단합니다. 원의 전체 둘레는 2πr이고, 이는 360도에 해당합니다. 따라서 중

문제 정의반지름이 R인 반원이 하나 주어져 있다고 가정해 봅시다. 이 반원 안에는 가로 길이 l, 세로 높이 b인 직사각형이 내접하고, 그 직사각형 안에는 다시 반지름 r인 원이 내접합니다. 우리가 구해야 할 값은 바로 가장 안쪽에 있는 이 원의 넓이입니다.수학적 접근1단계: 반원에 내접하는 최대 직사각형반원에 내접하는 가장 큰 직사각형은 밑변이 반원의 지름 위에 놓이고, 윗면의 두 꼭짓점이 반원의 곡선에 닿는 형태입니다. 반원의 중심에서 직사각형 윗면 꼭짓점까지의 거리가 곧 반지름 R이므로, 피타고라스 정리에 의해 다음 관계식이

이 글에서는 아래 그림과 같이 정사각형 ABCD 내부에 존재하는 잎(leaves) 모양 도형의 넓이를 구하는 방법을 알아보겠습니다. 정사각형의 각 변의 길이는 a입니다.문제 접근 방법잎 모양 도형은 서로 대칭인 두 개의 동일한 부분으로 나눌 수 있습니다. 각 부분의 넓이를 p라고 하면 다음과 같습니다.따라서 잎 모양 도형 전체의 넓이는 2p가 됩니다.넓이 공식 유도각 부분 p는 사분원(반지름 a)의 넓이에서 직각삼각형의 넓이를 뺀 값입니다.사분원의 넓이: πa² / 4직각삼각형의 넓이: a² / 2따라서 한쪽 부분의 넓이는 p =

이 글에서는 반지름이 주어졌을 때 n변 정다각형의 넓이를 구하는 방법을 살펴보겠습니다. 여기서 말하는 반지름은 다각형의 중심에서 임의의 꼭짓점까지의 거리를 의미합니다.문제를 해결하기 위해 중심에서 한 변으로 수선을 내립니다. 각 변의 길이를 a라고 하면, 수선은 이 변을 두 부분으로 나누며 각 부분의 길이는 a/2가 됩니다. 수선과 반지름이 이루는 각을 x, 반지름의 길이를 r이라고 하겠습니다.정다각형을 삼각형으로 나누기그림에서 확인할 수 있듯이 정다각형은 N개의 합동인 삼각형으로 나눌 수 있습니다. 중심에서의 각도 총합은 360°

뢸로 삼각형이란?뢸로 삼각형(Reuleaux Triangle)은 정삼각형의 세 꼭짓점을 중심으로 그린 세 개의 원호가 서로 만나 이루어지는 곡선 삼각형입니다. 어느 방향에서 재더라도 폭이 항상 동일한 일정폭 곡선의 대표적인 예로 알려져 있으며, 이번 글에서는 아래와 같은 뢸로 삼각형의 넓이를 계산하는 방법을 살펴보겠습니다.뢸로 삼각형의 내부에는 하나의 정삼각형이 포함되어 있습니다. 정삼각형의 한 변의 길이, 즉 원호의 반지름을 h라고 할 때, 이 도형은 반지름이 h인 세 개의 원이 서로 겹치는 영역(세 원의 교집합)으로 만들어집니다

처음 N개의 자연수(1부터 N까지)가 주어졌을 때, 인접한 두 요소 간의 절대 차이가 항상 1보다 큰 순열(permutation)을 만드는 것이 우리의 과제입니다. 만약 그러한 순열이 존재하지 않는다면 -1을 반환해야 합니다.이 문제는 그리디(Greedy) 알고리즘을 사용하면 아주 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.모든 홀수를 오름차순 또는 내림차순으로 먼저 나열합니다.그다음 모든 짝수를 내림차순 또는 오름차순으로 이어서 나열합니다.홀수끼리의 차이는 최소 2이고, 짝수끼리의 차이 역시 최소 2이며, 마지

길이가 n(n < 10)인 문자열이 주어졌을 때, 모음과 자음의 상대적인 위치를 변경하지 않으면서 문자열을 재배치할 수 있는 경우의 수를 구하는 문제입니다.접근 방법은 매우 간단합니다. 먼저 주어진 문자열에서 모음과 자음의 개수를 각각 센 뒤, 모음끼리 배치할 수 있는 경우의 수와 자음끼리 배치할 수 있는 경우의 수를 따로 계산합니다. 그리고 이 두 값을 곱하면 전체 경우의 수를 얻을 수 있습니다.여기서 중요한 점은 중복되는 문자가 있을 때입니다. 같은 문자가 여러 번 등장하면 단순 팩토리얼 값에 각 문자의 빈도수 팩토리얼을

문제 소개 1부터 n까지의 숫자가 무작위 순서로 섞여 있는 배열이 있다고 가정해 보겠습니다. 여기에 정수 K가 하나 더 주어집니다. N명의 사람들이 배드민턴 경기를 하기 위해 줄을 서서 대기 중이며, 게임은 다음 규칙에 따라 진행됩니다. 대기열 맨 앞의 두 명이 먼저 경기를 시작합니다. 진 사람은 대기열의 맨 뒤로 이동합니다. 이긴 사람은 대기열의 다음 사람과 계속해서 경기를 진행합니다. 누군가 K번 연속으로 승리하면 그 사람이 최종 우승자가 됩니다. 예제로 살펴보기 대기열이 [2, 1, 3, 4, 5]이고 K = 2일 때,