문제 개요 하나의 원과 하나의 직선이 주어졌을 때, 그 직선이 원에 접하는지, 원을 교차(관통)하는지, 아니면 원의 바깥쪽을 지나가는지 판별하는 것이 이 글의 목표입니다. 직선과 원의 위치 관계는 크게 세 가지 경우로 나뉩니다. 직선이 원에 한 점에서 닿는 경우 (접선) 직선이 원을 두 점에서 통과하는 경우 (교차) 직선이 원과 만나지 않고 지나가는 경우 (외부) 판별 알고리즘 다음 두 단계만 거치면 손쉽게 판별할 수 있습니다. 원의 중심과 주어진 직선 사이의 수직 거리 P를 구합니다. 거리 P를 반지름 r과 비교합니다. P

이 글에서는 C++을 사용하여 주어진 행렬이 가역 행렬(invertible matrix), 즉 역행렬이 존재하는 행렬인지 확인하는 방법을 알아보겠습니다.역행렬과 가역 조건행렬 M의 역행렬 M⁻¹은 다음 공식으로 정의됩니다.$$M^{-1}=\frac{adj(M)}{|M|}$$여기서 adj(M)은 수반 행렬(adjugate), |M|은 행렬식(determinant)입니다. 공식에서 알 수 있듯이 행렬식이 0이 아닐 때만 역행렬을 구할 수 있습니다. 행렬식이 0이면 분모가 0이 되어 역행렬이 정의되지 않기 때문입니다.따라서 행렬이 가역인

N × M 크기의 2차원 배열이 주어졌을 때, 모든 행에서 숫자를 하나씩 선택하여 선택된 요소들의 XOR 값이 0이 아닌(즉, 0보다 큰) 값이 되도록 할 수 있는지 확인하는 것이 이 글의 목표입니다.예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.77710107첫 번째 행에서는 7, 두 번째 행에서는 10을 선택하면 7 XOR 10의 결과가 되는데, 서로 다른 두 수의 XOR은 절대 0이 될 수 없으므로 답은 0이 아닌 값이 됩니다.문제 해결 접근 방법이 문제의 풀이법은 의외로 간단합니다. 핵심 아이디어는 다음 두 가지 조

이진(binary) 문자열 하나와 정수 k가 주어졌을 때, 해당 문자열이 k비트 이진수의 모든 순열을 포함하고 있는지 확인하는 문제입니다.예를 들어 문자열이 "11001"이고 k = 2라고 가정해 보겠습니다. 이 경우 2비트 이진수의 모든 순열인 00, 01, 10, 11 네 가지가 반드시 문자열 안에 존재해야 합니다. "11001"에는 길이 2의 부분 문자열로 "11", "10", "00", "01"이 모두 등장하므로 유효한

일반적인 이진 트리가 주어졌다고 가정해 봅시다. 이 트리는 이진 탐색 트리(BST)가 아니므로 노드 값 사이에 특정한 정렬 규칙이 없습니다. 따라서 트리 안에 동일한 값이 두 번 이상 등장하는지 확인하려면 다른 방식의 접근이 필요합니다.가장 효율적인 해결 방법은 해싱(hashing)을 활용하는 것입니다. 트리를 순회하면서 각 노드의 값을 해시 집합(unordered_set)에 저장하고, 어떤 노드의 값이 이미 집합에 존재한다면 그 즉시 중복이 있다고 판단하여 true를 반환합니다. 모든 노드를 순회했는데도 중복이 발견되지 않으면 f

이진 트리가 하나 주어졌다고 가정해 보겠습니다. 이때 확인해야 할 것은 해당 트리 안에 크기가 2 이상인 중복된 서브트리(하위 트리)가 존재하는지 여부입니다. 예를 들어 다음과 같은 이진 트리가 있다고 합시다.위 트리에는 크기가 2인 완전히 동일한 서브트리가 두 개 존재합니다. 이 문제는 트리 직렬화(serialization)와 해싱(hashing) 기법을 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 서브트리를 문자열 형태로 직렬화한 뒤 해시 테이블(집합)에 저장하고, 리프 노드가 아닌 어떤 서브트리의 직렬화

이번 글에서는 이진 트리가 레벨(level) 단위로 정렬되어 있는지 확인하는 방법을 알아보겠습니다. 레벨별로 정렬된 이진 트리는 다음과 같은 형태를 가집니다.레벨별 정렬된 이진 트리란?레벨별로 정렬된 이진 트리는 두 가지 조건을 만족해야 합니다.- 각 레벨 내에서 노드들이 왼쪽에서 오른쪽 방향으로 오름차순으로 정렬되어 있어야 합니다.- 상위 레벨의 모든 노드 값이 하위 레벨의 모든 노드 값보다 작아야 합니다. 즉, 아래로 내려갈수록 값이 커집니다.해결 접근 방법이 문제는 레벨 순서 순회(Level Order Traversal), 즉

점(.)과 숫자로 구성된 문자열이 하나 주어졌다고 가정해 보겠습니다. 점은 해당 셀이 비어 있음을 의미하고, 어떤 셀에 숫자 x가 적혀 있다면 그 셀에서 문자열 범위 안에서 왼쪽 또는 오른쪽으로 정확히 x칸 이동할 수 있습니다. 우리의 목표는 특정 셀을 두 번 이상(서로 다른 경로로) 방문할 수 있는지 확인하는 것입니다.예를 들어 문자열이 . 2 . . . 2 . .와 같다면, 네 번째 셀은 두 가지 서로 다른 방법으로 도달할 수 있습니다. 두 번째 셀에서 오른쪽으로 두 칸 이동하거나, 여섯 번째 셀에서 왼쪽으로 두 칸 이동하면 됩

배열에 저장된 요소들이 어떤 이진 탐색 트리(Binary Search Tree, BST)의 전위 순회(preorder traversal) 결과가 될 수 있는지 판별하는 문제를 살펴보겠습니다.예를 들어 수열이 {40, 30, 35, 80, 100}이라면, 이 수열은 다음과 같은 이진 탐색 트리를 구성할 수 있습니다.접근 방법: 스택 활용이 문제는 스택(stack) 하나만으로 O(n) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.빈 스택을 정의하고, 현재 루트(root) 값을 음의 무한대(INT_MIN)로 초기화합니

Hankel 행렬이란?정방행렬(square matrix)이 하나 주어졌을 때, 이 행렬이 Hankel 행렬인지 아닌지 판별하는 것이 우리의 과제입니다. Hankel 행렬은 왼쪽에서 오른쪽으로 거슬러 올라가는 각 반대각선(skew-diagonal) 위의 원소들이 모두 동일한 값을 갖는 정방행렬을 의미합니다.예를 들어, 아래와 같은 5×5 행렬을 살펴보겠습니다.1234523456345674567856789위 행렬에서 왼쪽 아래 방향으로 올라가는 각 대각선을 따라 원소를 읽어 보면, 같은 대각선 위의 값들이 서로 일치하는 것을 확인할 수

10자리 휴대폰 번호가 주어졌을 때, 이 번호가 멋진 번호(Fancy Number)인지 판별하는 것이 우리의 과제입니다. 멋진 번호가 되기 위한 조건은 세 가지가 있으며, 이 중 하나라도 만족하면 해당 번호는 멋진 번호로 간주됩니다.멋진 번호의 세 가지 조건같은 숫자가 연속으로 세 번 나타나는 경우 — 예: 555연속된 세 숫자가 오름차순 또는 내림차순인 경우 — 예: 123 또는 321특정 숫자가 네 번 이상 나타나는 경우 — 예: 8965499259에서 숫자 9가 네 번 등장예를 들어 9859009976은 세 번째 조건(숫자 9

문제 개요 숫자 n과 자릿수 d가 주어졌을 때, n이 2부터 32까지의 임의의 진법에서 d자리 숫자로 표현될 수 있는지 확인하는 것이 목표입니다. 예를 들어 n = 8, d = 4라고 가정해 보겠습니다. 8은 이진법(2진수)에서 1000으로 표현되며 자릿수가 정확히 4이므로 조건을 만족합니다. 접근 방법 핵심 아이디어는 2부터 32까지의 모든 진법을 하나씩 검사하는 것입니다. 각 진법에 대해 다음 규칙으로 판단할 수 있습니다. 성공 조건: 숫자가 해당 진법보다 작고 남은 자릿수가 1이면 true를 반환합니다. 재귀 단계: 자릿수

정수가 하나 주어졌을 때, 해당 숫자가 각 자릿수의 계승(팩토리얼) 값들의 합을 나눌 수 있는지 확인해야 합니다. 예를 들어 숫자가 19라고 가정해 보겠습니다. 각 자릿수 계승의 합은 (1! + 9!) = 362881이며, 이 값은 19로 나누어 떨어지므로 조건을 만족합니다.이 문제를 해결하는 방법은 간단합니다. 먼저 주어진 숫자를 임시 변수에 저장한 후, 각 자릿수를 추출하여 그 계승 값을 구하고 모두 더합니다. 마지막으로 이 합이 원래 숫자로 나누어 떨어지면 true를 반환하고, 그렇지 않으면 false를 반환하면 됩니다.알고리

프로닉 수(Pronic Number)란 무엇인가? 이번 글에서는 C++을 활용해 주어진 숫자가 프로닉 수(Pronic Number)인지 판별하는 방법을 살펴보겠습니다. 프로닉 수란 여러 개의 점을 직사각형 모양으로 배열할 수 있는 수를 말합니다. 프로닉 수는 수학적으로 두 개의 연속된 정수의 곱으로 정의됩니다. 즉, 어떤 수 n이 n = x × (x + 1) 형태로 표현될 수 있다면 그 수는 프로닉 수입니다. 처음 몇 가지 프로닉 수는 다음과 같습니다. 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 13

이 글에서는 하나의 큰 숫자를 합이 같은 둘 이상의 구간(세그먼트)으로 나눌 수 있는지 판별하는 C++ 프로그램을 살펴봅니다.예를 들어 숫자가 74325라고 가정해 보겠습니다. 이 숫자는 (7), (4, 3), (2, 5)의 세 부분으로 나눌 수 있으며, 각 구간의 합은 모두 7로 동일합니다. 따라서 이 숫자는 조건을 만족하는 숫자입니다.문제 해결 접근 방식이 문제는 다음 단계를 통해 해결할 수 있습니다.숫자를 문자열 형태로 입력받습니다.배열을 사용하여 각 자릿수의 누적합(prefix sum)을 저장합니다.두 번째 요소부터 마지막

매우 큰 숫자가 13으로 나누어 떨어지는지 확인해야 하는 경우가 종종 있습니다. 이런 숫자는 int나 long long 같은 일반적인 정수 자료형에 담을 수 없기 때문에, 문자열(string) 형태로 입력받아 처리해야 합니다. 숫자가 13으로 나누어 떨어지는지 판별하는 대표적인 방법은 다음 두 가지입니다. 교대 합(Alternating Sum) 방식 : 숫자를 오른쪽에서 왼쪽으로 세 자리씩 묶은 블록들을 번갈아 더하고 빼는 교대 합이 13으로 나누어 떨어지면, 원래 숫자도 13으로 나누어 떨어집니다. 예를 들어 2911285의

개요이 글에서는 C++에서 주어진 연결 리스트(Linked List)가 원형 연결 리스트(Circular Linked List)인지 판별하는 방법을 알아봅니다.판별 원리는 간단합니다. 먼저 시작(헤드) 노드를 별도의 변수에 저장해 둔 뒤 리스트를 순회합니다. 순회 중 어떤 노드의 next 포인터가 NULL을 가리키면 마지막 노드가 존재하는 것이므로 일반 연결 리스트입니다. 반대로 순회하다가 처음에 저장해 둔 시작 노드와 동일한 노드를 다시 만나게 되면, 리스트의 끝이 시작점으로 되돌아오는 것이므로 원형 연결 리스트라고 판단할 수 있

문제 개요n개의 요소를 가진 연결 리스트 L이 주어졌을 때, 이 리스트가 쌍별(pairwise)로 정렬되어 있는지 확인해야 합니다. 예를 들어 리스트가 {8, 10, 18, 20, 5, 15}라고 하면, (8, 10), (18, 20), (5, 15)의 각 쌍이 모두 정렬되어 있으므로 이 리스트는 쌍별로 정렬된 것입니다.리스트의 요소 개수가 홀수인 경우에는 마지막에 짝이 없어 남는 하나의 요소를 검사 대상에서 제외합니다.접근 방식풀이 방법은 매우 간단합니다. 리스트를 왼쪽에서 오른쪽으로 한 번 순회하면서 인접한 두 요소씩 짝을 지어

이번 글에서는 어떤 숫자가 비정상 수(Unusual Number)인지 판별하는 방법을 알아보겠습니다. 비정상 수란, 그 수의 가장 큰 소인수가 해당 수의 제곱근보다 엄격하게 큰 경우를 말합니다.비정상 수의 예시는 다음과 같습니다: 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46해결 접근 방식이 문제를 해결하려면 먼저 주어진 수의 가장 큰 소인수를 구한 뒤, 그 값이 해당

Bleak 수란 무엇인가?이 글에서는 특정 숫자가 Bleak(블리크) 수인지 판별하는 방법을 알아보겠습니다. Bleak 수란 어떤 양의 정수 x와 그 수의 세트 비트(set bit, 1로 설정된 비트) 개수의 합으로 표현될 수 없는 수를 의미합니다. 즉, 임의의 음이 아닌 정수 x에 대해 x + set_bit_count(x) ≠ n 이 항상 성립한다면, 그 수 n은 Bleak 수입니다.반대로 1부터 n 미만까지의 수 중에서 자기 자신과 자신의 세트 비트 개수를 더했을 때 n이 되는 수가 하나라도 존재한다면, n은 Bleak 수가 아