문제 소개 y = mx + c 형태의 직선이 여러 개 주어져 있다고 가정해 봅시다. 이 직선들과 수직 구간(세로 경계)이 이루는 영역 안에서, 주어진 구간에 서로 다른 직선의 교차점이 존재하는지 판별하는 것이 목표입니다. 예를 들어 다음과 같은 네 개의 직선이 있다고 합시다. L1 = y = x + 2 L2 = y = −x + 7 L3 = y = −3 L4 = y = 2x − 7 그리고 수직 구간은 x = 2부터 x = 4까지로 주어집니다. 이 예제에서는 L1과 L2의 교차점이 해당 구간 안에 포함되므로 정답은 true가 됩니다

크기가 각각 m과 n인 두 개의 양의 정수 배열이 있다고 가정해 보겠습니다(단, m > n). 우리는 두 번째 배열에 0을 삽입하여 두 배열의 내적(dot product)을 최대화해야 하며, 이때 주어진 배열의 원소 순서는 절대 변경할 수 없다는 점에 유의해야 합니다.예를 들어 배열 A = [2, 3, 1, 7, 8], 배열 B = [3, 6, 7]이 있다고 합시다. 두 번째 배열의 첫 번째와 세 번째 위치에 0을 삽입하면 내적은 다음과 같이 계산되어 최댓값 107을 얻을 수 있습니다.2 × 0 + 3 × 3 + 1 × 0 +

문제 개요n개의 객체로 이루어진 배열이 있다고 가정해 보겠습니다. 각 객체는 고유한 너비 W[i]를 가지며, 이 객체들을 다음 두 조건을 만족하도록 피라미드 형태로 쌓아야 합니다.위쪽 층(i번째)의 총 너비는 바로 아래 층((i+1)번째)보다 작아야 합니다.위쪽 층의 객체 수 역시 바로 아래 층보다 적어야 합니다.예를 들어 객체의 너비가 [40, 100, 20, 30]과 같다면 결과는 2입니다. 배열을 정렬하면 [20, 30, 40, 100]이 되고, 가장 작은 값인 20을 꼭대기에 놓습니다. 그다음 층은 30과 40을 합쳐 총 너

양수로만 이루어진 세 개의 스택이 주어져 있다고 가정해 봅시다. 목표는 각 스택에서 맨 위(top) 요소를 제거할 수 있다는 조건 하에, 세 스택의 합이 모두 같아질 수 있는 최댓값을 찾는 것입니다. 스택은 배열로 표현되며, 배열의 첫 번째 인덱스가 곧 스택의 맨 위 요소를 의미합니다. 예를 들어 스택이 [3, 10], [4, 5], [2, 1]처럼 구성되어 있다면 결과는 0이 됩니다. 세 스택의 합(각각 13, 9, 3)을 같게 만들려면 모든 요소를 전부 제거하는 수밖에 없기 때문입니다. 문제 해결 접근법 이 문제의 핵심 아이디

문제 설명양의 정수로 이루어진 두 배열 X와 Y가 주어집니다. x는 배열 X의 원소, y는 배열 Y의 원소일 때, xy > yx를 만족하는 쌍(x, y)의 개수를 구하는 것이 이 글의 목표입니다.예를 들어 X = [2, 1, 6], Y = [1, 5]라고 가정해 보겠습니다. 이 경우 조건을 만족하는 쌍은 (2, 1), (2, 5), (6, 1)로 총 3개이므로 결과값은 3이 됩니다.핵심 아이디어모든 쌍을 하나씩 검사하는 브루트 포스 방식은 O(m×n)의 시간이 걸려 비효율적입니다. 대신 다음과 같은 수학적 성질을 활용하면 문제

문자열이 하나 주어졌을 때, 문자열을 두 부분으로 나누는 지점 중 왼쪽 부분과 오른쪽 부분이 정확히 같은 문자 집합을 포함하는 위치, 즉 균형 위치(balance point)의 개수를 찾는 문제입니다. 이때 각 문자의 등장 빈도는 중요하지 않으며, 해당 문자가 양쪽에 존재하기만 하면 됩니다.예를 들어 문자열이 ABAABA라고 한다면, 균형 위치는 총 3개입니다.AB | AABAABA | ABAABAA | BA해결 접근 방식이 문제는 효율적인 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.먼저 문자열을 한 번 순회하면

이 글에서는 C++에서 사용자로부터 정수를 입력받아 화면에 출력하는 방법을 알아보겠습니다. 입력을 받을 때는 cin 연산자를 사용하고, 출력할 때는 cout 연산자를 사용합니다. 기본 문법은 다음과 같습니다.입력 문법int x; cin >> x;출력 문법int x = 110; cout << x;예제 코드아래 예제에서는 사용자에게 값을 입력받은 후 그 값을 출력하고, 미리 초기화된 변수 y의 값도 함께 출력합니다.#include<iostream> using namespace std; int main(i

C++ 개발자 면접에서 반복적으로 등장하는 핵심 질문들을 정리했습니다. C와 C++의 차이, 포인터와 참조의 차이, 가상 함수(virtual function), 그리고 this 포인터까지, 실전 면접에서 꼭 알아야 할 개념들을 예제 코드와 함께 살펴보겠습니다.1. C와 C++의 차이점은 무엇인가요?C와 C++은 문법적으로 유사하지만, 언어의 설계 철학과 지원하는 프로그래밍 패러다임에서 큰 차이가 있습니다. 아래 표에서 주요 차이점을 확인해 보세요.구분CC++개발 배경데니스 리치(Dennis Ritchie)가 1969년경 AT&T 벨

이 글에서는 시스템 호출(system call)을 활용하여 C++로 타이머를 구현하는 방법을 알아봅니다. 그래픽이나 애니메이션은 일절 사용하지 않으며, 순수하게 콘솔 환경에서만 동작합니다.여기서 말하는 타이머는 스톱워치(stopwatch), 즉 시간을 0부터 위로 올려가며 카운트하는 방식의 시계를 의미합니다. 이 예제에서 사용되는 핵심 시스템 호출은 다음 두 가지입니다.핵심 시스템 호출1. sleep(n)프로그램을 n초 동안 대기(슬립) 상태로 만드는 함수입니다. 1초마다 화면을 갱신하는 타이머의 핵심 역할을 담당합니다.2. sys

C++은 세계에서 가장 널리 사용되는 객체 지향 프로그래밍 언어 중 하나입니다. 탄생한 지 오랜 시간이 지났음에도 불구하고 지금도 시스템 프로그래밍, 게임 개발, 데이터베이스, 임베디드 시스템 등 다양한 분야에서 핵심적인 역할을 담당하고 있습니다. 그렇다면 수많은 프로그래밍 언어 중에서 왜 C++을 배워야 할까요? 이 글에서는 C++을 선택해야 하는 주요 이유를 하나씩 살펴보겠습니다.1. 높은 인기와 높은 연봉C++은 전 세계적으로 가장 인기 있는 프로그래밍 언어 중 하나로, 약 440만 명의 개발자가 사용하고 있습니다. 또한 C+

C++ 프로그래밍에서 서로 다른 데이터 타입 간에 값을 주고받는 상황은 매우 흔하게 발생합니다. 이때 필요한 것이 바로 타입 변환(Type Conversion)입니다. C++의 타입 변환은 크게 두 가지 방식으로 나눌 수 있습니다.암시적 변환(Implicit Conversion): 컴파일러가 자동으로 수행명시적 변환(Explicit Conversion): 개발자가 의도적으로 지정1. 암시적 타입 변환 (Implicit Type Conversion)암시적 타입 변환은 자동 타입 변환이라고도 부릅니다. 사용자가 별도의 코드를 작성하지

두 개의 정수 x와 n이 주어졌다고 가정해 봅시다. 이때 x^1, x^2, …, x^(n-1), x^n으로 계산되는 모든 값에 등장하는 숫자(0~9)의 등장 횟수를 담은 배열을 구해야 합니다.예를 들어 x = 15, n = 3이라면, 거듭제곱 값은 차례대로 15, 225, 3375입니다. 이 세 수에 나타난 자릿수를 모두 세면 결과는 다음과 같습니다.[0, 1, 2, 2, 0, 3, 0, 1, 0, 0]즉, 숫자 1은 한 번, 2는 두 번, 3은 두 번, 5는 세 번, 7은 한 번 나타나고 나머지 숫자는 등장하지 않습니다.해결 접근

문제 개요정점(vertex) 목록과 각 정점의 차수(degree, 해당 정점에 연결된 간선의 수)가 주어져 있다고 가정해 보겠습니다. 이 차수 수열로부터 하나의 무방향 그래프(undirected graph)를 생성해야 하며, 그래프에는 루프(loop, 자기 자신으로 향하는 간선)나 중복 간선(multiple edge)이 포함되어서는 안 됩니다.예를 들어 차수 수열이 [2, 2, 1, 1]이라면, 다음과 같은 그래프를 만들 수 있습니다.해결 접근 방법이 문제는 탐욕(greedy) 방식으로 해결할 수 있습니다. 차수가 아직 남아 있는

이번 글에서는 언어 L = {AⁱBʲCᵏ | i × j = k; i, j, k ≥ 1}를 인식하는 튜링 머신(Turing Machine)을 설계하는 방법을 살펴보겠습니다. 이 언어는 문자 A, B, C 세 가지만으로 구성된 문자열들의 집합으로, C의 개수(k)가 A의 개수(i)와 B의 개수(j)를 곱한 값과 정확히 일치해야 한다는 규칙을 따릅니다. 예를 들어 문자열 w = AABBBBCCCCCCCC를 생각해 볼 수 있습니다. 이 문자열은 A가 2개, B가 4개, C가 8개로 이루어져 있고 2 × 4 = 8이 성립하므로, 튜링 머신은

이 글에서는 언어 L = {AⁱBʲCᵏ | i < j < k, i ≥ 1}를 인식하는 튜링 기계(Turing Machine)를 만드는 방법을 살펴봅니다.언어의 정의와 조건이 언어는 오직 A, B, C 세 가지 문자만으로 구성된 문자열들을 포함합니다. 여기서 중요한 조건은 각 문자의 개수가 반드시 i < j < k 관계를 만족해야 한다는 것입니다. 즉, B의 개수가 A보다 많고, C의 개수는 다시 B보다 많아야 합니다.예를 들어 w = AABBBBCCCCC인 경우를 생각해 보겠습니다. 이 문자열은 A가 2개, B

이 글에서는 언어 L = {aⁱbʲcᵏ | i > j > k, k ≥ 1}를 인식하는 튜링 머신(Turing Machine)을 만드는 방법을 살펴봅니다. 이 언어는 오직 세 개의 문자 a, b, c로만 구성된 문자열들을 다루며, 각 문자의 개수가 엄격한 순서 관계를 만족해야 합니다. 즉, a의 개수(i)가 b의 개수(j)보다 많고, b의 개수(j)가 c의 개수(k)보다 많아야 하며, c는 최소 1개 이상 존재해야 합니다.예를 들어 입력 문자열이 w = aaaaaabbbbccc라고 해봅시다. 여기서 a는 6개, b는 4개,

언어 L = {0ⁿ1ⁿ2ⁿ | n≥1}을 위한 튜링 기계이 글에서는 언어 L = {0n1n2n | n ≥ 1}을 인식하는 튜링 기계(Turing Machine)를 설계하는 방법을 살펴봅니다. 이 언어는 0, 1, 2 세 가지 문자만으로 구성되며, 세 문자의 개수가 모두 동일한 문자열들의 집합을 의미합니다. 예를 들어 w = 000111222라면 0, 1, 2가 각각 3개씩 존재하므로 튜링 기계는 이 문자열을 수용(accept)합니다.해결 접근 방식이 문제는 마커(marker) 기호를 이용해 이미 처리한 문자를 표시해 가며 해결할 수

언어 L = {ww | w ∈ {0,1}}란?이번 글에서는 언어 L = {ww | w ∈ {0,1}}를 인식하는 튜링 기계(Turing Machine)를 만드는 방법을 살펴보겠습니다. 이 언어는 0과 1 두 개의 문자만으로 구성된 문자열 w가 자기 자신과 한 번 더 연결된 형태, 즉 ww의 집합을 의미합니다. 예를 들어 w = 10110이라면, 튜링 기계는 z = 1011010110이라는 입력 문자열을 받아들여야 합니다.문제 해결 접근 방식1단계: 문자열의 중간 지점 찾기가장 먼저 할 일은 문자열의 중간 지점(midpoint)을 찾

이 글에서는 언어 L = {wwr | w ∈ {0, 1}}를 인식하는 튜링 기계(Turing Machine)를 만드는 방법을 살펴봅니다. 이 언어는 0과 1이라는 두 개의 문자만으로 구성된 문자열을 다루며, w는 임의의 문자열이고 wr은 해당 문자열을 거꾸로 뒤집은 역순(reverse)을 의미합니다.예를 들어 w = 10110이라면, wr은 01101이 됩니다. 따라서 튜링 기계는 z = 1011001101과 같은 형태의 문자열을 수용(accept)해야 합니다.문제 해결 접근 방식이 문제는 다음과 같은 단계별 방법으로 해결할 수 있

전위 순회(preorder traversal) 결과 하나만 주어졌을 때, 이를 바탕으로 이진 탐색 트리(BST)를 복원하는 방법을 알아보겠습니다. 예를 들어 순회 결과가 [10, 5, 1, 7, 40, 50]이라면 아래 그림과 같은 트리가 완성됩니다.핵심 아이디어: 노드별 값의 범위(min~max) 설정이 문제를 해결하는 핵심 기법은 각 노드가 가질 수 있는 값의 범위 {min…max}를 지정하는 것입니다. 알고리즘은 다음 순서로 진행됩니다.먼저 루트 노드의 범위를 {INT_MIN…INT_MAX}로 초기화합니다. 전위 순회의 첫 번