이 글에서는 비트 연산자(bit operator)를 활용하여 주어진 숫자가 양수인지, 음수인지, 아니면 0인지 확인하는 방법을 알아보겠습니다.핵심 원리32비트 정수에서 오른쪽 시프트 연산을 활용하면 부호 정보를 쉽게 추출할 수 있습니다.n >> 31 연산은 산술 시프트(arithmetic shift) 방식으로 동작하기 때문에 다음과 같은 결과가 나타납니다.음수일 경우: -1양수 또는 0일 경우: 0반대로 -n >> 31 연산을 수행하면 부호가 반전된 값에 시프트가 적용되므로, 양수일 때는 -1이 반환됩니다. 그

이 글에서는 비교적 간단한 방법을 사용해 주어진 숫자가 8의 거듭제곱인지 판별하는 방법을 알아보겠습니다. 예를 들어 4096이라는 숫자가 입력되면, 이는 8⁴이므로 프로그램은 true를 반환합니다.핵심 아이디어판별 방식은 매우 간단합니다. 바로 log₈(num) 값을 계산하는 것입니다. 만약 이 로그 값이 정수라면, 그 숫자는 8의 거듭제곱입니다.여기서 로그 밑 변환 공식을 활용합니다. 즉, log₈(n)은 log(n)/log(8)과 같습니다. 계산 결과가 부동소수점 오차를 가질 수 있으므로, cmath 헤더의 trunc() 함수를

이 글에서는 하나의 숫자 n과 밑 값 k가 주어졌을 때, n이 k의 거듭제곱인지 판별하는 프로그램을 살펴봅니다. 특히 진법 변환(base changing) 기법을 활용해 문제를 해결하는 것이 핵심 포인트입니다.예를 들어 숫자가 27이고 k = 3이라고 가정해 보겠습니다. 27을 3진수로 변환하면 1000이 됩니다. 이처럼 진법을 변환한 결과에서 숫자 1이 딱 한 번만 등장하고 나머지 자릿수가 모두 0이라면, 그 수는 k의 거듭제곱이라고 판단할 수 있습니다.해결 절차flag := false로 초기화합니다.number > 0인 동

개요타원이 하나 주어져 있다고 가정해 봅시다. 타원은 중심 좌표 (h, k), 장반축(semi-major axis) a, 단반축(semi-minor axis) b로 정의됩니다. 여기에 임의의 점 (x, y)가 하나 더 주어졌을 때, 이 점이 타원의 내부에 있는지, 외부에 있는지, 아니면 경계선 위에 있는지 판별하는 것이 목표입니다.이 문제는 다음 부등식을 활용하면 간단하게 해결할 수 있습니다.$$\frac{\left(x-h\right)^2}{a^2}+\frac{\left(y-k\right)^2}{b^2}\leq1$$주어진 점 (x,

개요포물선이 하나 주어져 있다고 가정해 봅시다. 포물선의 꼭짓점 좌표는 (h, k)이며, 초점과 꼭짓점 사이의 거리는 a입니다. 여기에 또 다른 점이 주어졌을 때, 해당 점이 포물선의 내부에 있는지, 외부에 있는지, 아니면 포물선 곡선 위에 있는지 판별하는 것이 이 글의 목표입니다.이 문제를 해결하려면 주어진 점 (x, y)를 다음 포물선 표준 방정식에 대입하여 값을 계산합니다.(y-k)² = 4a(x-h)계산 결과가 0보다 작으면 점은 포물선 내부에 위치하고, 0이면 포물선 위에 있으며, 0보다 크면 포물선 외부에 있습니

친구 여러 명이 서로에게 돈을 빌려주고 빌린 상황을 생각해 봅시다. 이처럼 금전 거래가 얽혀 있으면 친구 관계망 안에 여러 갈래의 현금 흐름이 발생합니다. 우리가 풀어야 할 과제는 바로 네트워크 전체의 현금 흐름, 즉 거래 건수와 이동 금액을 최소한으로 줄이는 것입니다.예를 들어 P1, P2, P3라는 세 명의 친구가 있다고 가정하면, 이들 사이의 현재 현금 흐름은 아래와 같습니다.위 다이어그램의 현금 흐름은 아직 최소화되지 않은 상태입니다. 불필요한 중간 거래를 걷어내고 깔끔하게 정산하면 최종적으로 다음과 같은 단순한 구조가 됩니

2차원 평면상에 여러 개의 점이 주어졌을 때, 원점(0, 0)에서 가장 가까운 K개의 점을 찾는 문제를 생각해 봅시다. 예를 들어 점들이 (3, 3), (5, -1), (-2, 4)라고 할 때, 가장 가까운 두 점(K = 2)은 (3, 3)과 (-2, 4)입니다.해결 방법이 문제는 각 점의 유클리드 거리(Euclidean distance)를 기준으로 점 목록을 정렬한 뒤, 정렬된 목록에서 앞쪽 K개의 요소를 선택하는 방식으로 해결할 수 있습니다. 정렬 후 상위 K개의 점이 바로 원점에 가장 가까운 K개의 점입니다.여기서 한 가지 최

이 글에서는 C++로 구현된 단일 순환 연결 리스트(singly circular linked list)에서 최솟값과 최댓값을 찾는 방법을 알아보겠습니다.순환 연결 리스트의 기본 개념단일 순환 연결 리스트는 마지막 노드의 next 포인터가 첫 번째 노드를 가리키는 구조입니다. 또한 시작 노드는 별도의 start 포인터로 관리됩니다. 새로운 요소를 삽입할 때는 마지막 노드 뒤에 추가하며, 이때 새로 삽입된 노드의 next 부분이 start 노드의 주소로 갱신되어 순환 구조가 유지됩니다.최솟값과 최댓값을 찾는 알고리즘알고리즘 자체는 매우

문제 개요평면상에 여러 개의 점으로 이루어진 집합이 주어졌다고 가정해 봅시다. 이때 우리의 목표는 모든 점을 한 번씩 지나가면서 스스로 교차하지 않는 단순 닫힌 경로(simple closed path)를 찾는 것입니다.예를 들어 아래와 같은 점들이 있을 때, 이 점들을 모두 연결하는 하나의 닫힌 경로를 만들 수 있습니다.알고리즘 접근 방법닫힌 경로를 만들기 위해서는 다음 세 단계를 순서대로 수행하면 됩니다.1단계: 점들 중 가장 왼쪽 아래(bottom-left)에 위치한 점을 찾아 기준점 P로 지정합니다.2단계: 나머지 n−1개의

원의 중심 좌표와 반지름이 주어져 있고, 또 다른 한 점 (x, y)가 원의 중심을 기준으로 어느 사분면에 위치하는지 구하는 문제입니다. 점이 원 내부에 존재하면 해당 사분면을 출력하고, 원 바깥에 있다면 오류 메시지를 출력합니다.원의 중심을 (h, k), 점의 좌표를 (x, y)라고 할 때, 원의 방정식은 다음과 같습니다.(x − h)2 + (y − k)2 = r2점의 위치는 아래 조건들을 통해 판단할 수 있습니다.(x − h)2 + (y − k)2 > r2 이면, 점은 원의 외부에 있습니다.(x − h)2 + (y − k)

플립플롭(Flip-Flop)은 순차 논리 디지털 회로의 핵심 구성 요소로, 클럭 신호에 동기화되어 1비트의 데이터를 저장할 수 있는 기본 메모리 소자입니다. 플립플롭에는 여러 종류가 있으며, 이 글에서는 대표적인 플립플롭의 유형과 함께 한 플립플롭을 다른 플립플롭으로 변환하는 규칙과 방법을 자세히 살펴보겠습니다.플립플롭은 크게 다음 네 가지 유형으로 나눌 수 있습니다.SR 플립플롭D 플립플롭JK 플립플롭T 플립플롭1. SR 플립플롭SR 플립플롭은 클럭 신호의 상승 에지(positive transition) 또는 하강 에지(negat

이 글에서는 이진 트리(Binary Tree)가 레벨별로 정렬되어 있는지 확인하는 방법을 알아보겠습니다. 레벨별로 정렬된 이진 트리는 아래와 같은 구조를 가집니다.위 트리처럼 각 레벨에서 노드들은 왼쪽에서 오른쪽으로 정렬되어 있으며, 동시에 각 레벨에 속한 값들이 이전 레벨의 값들보다 항상 커야 합니다.문제 해결 접근 방식이 문제는 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.먼저 큐(Queue)를 사용해 트리를 레

두 개의 이진 트리가 주어졌을 때, 그중 작은 트리가 다른 큰 트리의 서브트리(subtree)인지 판별하는 문제를 살펴보겠습니다. 아래와 같은 두 개의 트리가 있다고 가정해 봅시다.문제 접근 방식위 그림에서 두 번째 트리는 첫 번째 트리의 서브트리입니다. 이 성질을 확인하려면 다음과 같은 절차를 따릅니다.먼저 메인 트리를 후위 순회(post-order) 방식으로 탐색하면서 각 노드를 방문합니다. 그리고 현재 방문한 노드를 루트로 하는 부분 트리가 두 번째 트리와 완전히 동일한 구조와 값을 갖는지 비교합니다. 만약 어느 한 지점에서

이 글에서는 이중 연결 리스트(Doubly Linked List)를 이용해 주어진 문자열이 회문(Palindrome)인지 확인하는 방법을 알아봅니다.회문 판별 알고리즘의 기본 개념먼저 문자열의 각 문자를 하나의 이중 연결 리스트에 순서대로 삽입합니다. 그다음 left와 right라는 두 개의 포인터를 준비합니다.left 포인터는 리스트의 앞쪽(왼쪽)에서 시작합니다.right 포인터는 리스트의 뒤쪽(오른쪽)에서 시작합니다.양쪽 끝에서부터 동시에 스캔을 진행하며, left가 가리키는 문자와 right가 가리키는 문자가 서로 같다면 le

문제 개요정렬되지 않은 배열에서 서로 k 거리 이내에 중복된 요소가 존재하는지 확인하는 방법을 알아보겠습니다. 예를 들어 요소 목록이 {1, 2, 3, 1, 4, 5}이고 k = 3이라면, 두 개의 1 사이 거리가 3이므로 프로그램은 true를 반환합니다.이 문제는 해시 테이블(std::set)을 활용한 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 항상 현재 위치에서 k 거리 이내의 요소들만 집합에 유지하기 때문에 전체 시간 복잡도는 O(n)입니다.알고리즘 접근 방식빈 해시 테이블(집합)을 하나 생성합니다.각 인덱스 i

이 글에서는 주어진 이진 트리가 합 트리(Sum Tree)인지 판별하는 방법을 알아보겠습니다. 먼저 합 트리가 무엇인지부터 정리해 보겠습니다.합 트리(Sum Tree)란?합 트리는 각 노드가 자신의 왼쪽 자식과 오른쪽 자식 노드 값의 합을 저장하는 이진 트리입니다. 이 규칙이 모든 노드에 적용되기 때문에, 결과적으로 루트 노드에는 트리 전체 요소들의 총합이 담기게 됩니다. 다음은 합 트리의 대표적인 예시입니다.판별 방법합 트리 여부를 확인하는 가장 직관적인 방법은 다음과 같습니다.1. 각 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리

원점을 중심으로 하는 두 개의 동심원이 있다고 가정해 보겠습니다. 두 원의 반지름은 각각 r과 R로 주어지며, r은 바깥쪽 원, R은 안쪽 원의 반지름입니다(r > R). 여기에 세 번째 원이 하나 더 존재하는데, 이 원의 반지름 r1과 중심 좌표 (x, y)가 주어졌을 때 해당 원이 두 원 사이의 고리(환형 영역) 안에 완전히 들어가는지 판별하는 것이 이 글의 목표입니다. 접근 방법: 피타고라스 정리 활용 이 문제는 피타고라스 정리를 사용하면 간단하게 해결할 수 있습니다. 먼저 세 번째 원의 중심과 원점 사이의 거리를 다음

합 문자열(Sum String)이란 무엇일까요? 이 글에서는 C++을 이용해 주어진 문자열이 합 문자열(sum-string)인지 판별하는 방법을 살펴보겠습니다. 합 문자열이란, 문자열의 맨 오른쪽 부분 문자열이 바로 앞에 있는 두 부분 문자열의 합으로 표현될 수 있고, 이 규칙이 앞쪽 부분 문자열들에 대해서도 재귀적으로 계속 성립하는 문자열을 의미합니다. 예를 들어 문자열 12243660을 보겠습니다. 12 + 24 = 36 → 문자열 안에서 12와 24 바로 뒤에 36이 등장합니다. 24 + 36 = 60 → 이어서 36 뒤에

이 글에서는 주어진 트리 그래프가 선형(linear)인지 아닌지 확인하는 방법을 알아봅니다. 선형 트리 그래프란 모든 노드를 하나의 직선 위에 나열해 표현할 수 있는 그래프를 의미합니다. 다음은 선형 트리 그래프의 예시입니다. 반면, 아래와 같은 그래프는 선형이 아닙니다. 선형 트리 그래프의 판별 조건 그래프가 선형인지 확인하려면 다음 두 가지 조건 중 하나를 만족하는지 검사하면 됩니다. 노드의 개수가 1개라면 해당 트리 그래프는 선형입니다. n개의 노드 중 (n − 2)개 노드의 차수(degree)가 2라면 선형입니다. 이때

그래프가 강하게 연결(strongly connected)되어 있는지 판별해야 하는 상황이 자주 있습니다. 임의의 두 정점을 골랐을 때 서로에게 도달하는 경로가 항상 존재한다면, 그 그래프는 강하게 연결된 그래프라고 합니다. 무방향 그래프에서는 단순히 연결만 되어 있으면 곧 강하게 연결된 것과 같습니다. 하지만 방향성이 있는 유향 그래프(directed graph)에서는 모든 정점 쌍이 양방향으로 도달 가능해야 한다는 조건이 필요합니다.즉, 일부 유향 그래프는 연결은 되어 있더라도 강하게 연결되지 않을 수 있습니다. 아래는 강하게 연