문제 개요숫자(digit)들로 구성된 비어 있지 않은 단일 연결 리스트(singly linked list)가 하나의 음이 아닌 정수를 나타낸다고 가정해 봅시다. 우리가 해야 할 일은 이 정수에 1을 더하는 것입니다. 단, 0 자체를 제외하면 정수 앞에 붙는 불필요한 0(선행 제로)은 없으며, 연결 리스트에서 최상위 자릿수는 리스트의 머리(head)에 위치한다고 가정합니다.예를 들어 입력이 [1, 2, 3]이라면 1을 더한 결과인 [1, 2, 4]를 출력해야 합니다.접근 방법이 문제의 핵심 아이디어는 간단합니다. 덧셈에서 올림(car

문제 개요 크기가 n인 배열이 주어지고, 모든 원소가 0으로 초기화되어 있다고 가정해 봅시다. 그리고 값 k가 함께 주어지며, 우리는 k번의 업데이트 연산을 수행해야 합니다. 각 연산은 [startIndex, endIndex, inc] 형태의 세 값으로 표현되며, 부분 배열 A[startIndex ... endIndex]의 startIndex부터 endIndex까지(양 끝 인덱스 포함) 모든 원소를 inc만큼 증가시킵니다. 목표는 k번의 모든 연산이 완료된 후의 최종 배열을 구하는 것입니다. 예를 들어 입력이 length = 5,

이번 글에서는 다음과 같은 연산을 지원하는 전화번호부(Phone Directory)를 C++로 설계하는 방법을 알아보겠습니다.get – 아직 아무에게도 할당되지 않은 번호를 하나 반환합니다.check – 특정 번호가 현재 사용 가능한지 여부를 확인합니다.release – 사용 중이던 번호를 회수하여 다시 사용할 수 있도록 반환합니다.생성자(initializer)를 통해 처음에 총 n개의 번호를 초기화할 수 있습니다.해결 접근 방법이 문제는 집합(set)과 큐(queue) 두 가지 자료구조를 활용하면 효율적으로 해결할 수 있습니다.

C++에서 주어진 부분 수열 목록으로부터 원본 수열을 유일하게 재구성할 수 있는지 판별하는 방법을 알아봅니다. 이 문제는 방향 그래프의 위상 정렬(topological sort)을 활용하면 깔끔하게 해결할 수 있으며, 그래프 이론과 알고리즘 설계 능력을 동시에 점검할 수 있는 대표적인 문제입니다.문제 개요원본 수열 org가 seqs에 담긴 여러 수열로부터 유일하게 재구성될 수 있는지 확인하는 것이 목표입니다. 원본 수열은 1부터 n까지의 정수로 이루어진 순열(permutation)이며, n의 범위는 1 ≤ n ≤ 10⁴입니다. 여기

문제 소개 문자 D와 I로만 이루어진 비밀 시그니처(secret signature)가 주어졌다고 가정해 봅시다. D는 두 숫자 사이의 감소 관계를, I는 증가 관계를 의미합니다. 이 시그니처는 1부터 n까지의 서로 다른 숫자를 모두 한 번씩 사용하는 특별한 정수 배열로부터 생성됩니다. 예를 들어 시그니처 DI는 [2, 1, 3] 또는 [3, 1, 2]와 같은 배열로 만들 수 있습니다. 반면 [3, 2, 4]나 [2, 1, 3, 4] 같은 배열로는 만들 수 없는데, 이 배열들은 DI 시그니처를 표현할 수 없는 잘못된 조합이기 때문입

문제 소개이진 배열(0과 1로만 구성된 배열)이 주어졌을 때, 최대 한 번의 0을 1로 뒤집을 수 있다면 배열에서 만들 수 있는 최대 연속된 1의 개수를 구하는 문제입니다.예를 들어 입력이 [1,0,1,1,0]이라면 출력은 4가 됩니다. 첫 번째 0을 뒤집으면 [1,1,1,1,0]이 되어 앞쪽에 연속된 1이 4개 생기기 때문입니다.접근 방법: 슬라이딩 윈도우이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 O(n) 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.두 개의 포인터(i, j)로

문제 설명 미로 안에는 빈 공간과 벽이 있고, 그 사이에 공 하나가 놓여 있다고 가정해 보겠습니다. 공은 상·하·좌·우 어느 방향으로든 굴러가며 빈 경로를 따라 이동할 수 있지만, 벽에 부딪히기 전까지는 절대 멈추지 않습니다. 공이 한 번 멈춘 이후에만 다음 방향을 다시 선택할 수 있습니다. 공의 시작 위치, 목적지, 그리고 미로 정보가 주어졌을 때 우리가 확인해야 할 것은 공이 목적지 위에서 멈출 수 있는지입니다. 미로는 2차원 배열로 표현되며, 1은 벽, 0은 빈 공간을 의미합니다. 미로의 테두리는 모두 벽으로 둘러싸여 있고,

문제 정의 빈 공간과 벽으로 이루어진 미로 안에 공이 하나 놓여 있다고 가정해 보겠습니다. 공은 상, 하, 좌, 우 어느 방향으로든 굴러갈 수 있지만, 벽에 부딪히기 전까지는 절대 멈추지 않습니다. 공이 한 번 멈추면 그 자리에서 다음 방향을 새로 선택할 수 있습니다. 공의 시작 위치, 목적지, 그리고 미로 정보가 주어졌을 때, 공이 목적지 위에서 멈추게 되는 최단 거리를 구해야 합니다. 여기서 거리란 공이 지나간 빈 칸의 개수를 의미하며, 시작 위치는 제외하고 최종적으로 멈춘 지점까지 포함해서 셉니다. 어떤 방법을 써도 공을 목

문제 개요이진 탐색 트리(Binary Search Tree, BST) 안의 한 노드가 주어졌을 때, 해당 노드의 중위 순회 후속자(in-order successor)를 찾는 문제를 살펴보겠습니다. 중위 순회 후속자란 현재 노드의 값보다 큰 키를 가진 노드들 중에서 가장 작은 값을 가진 노드를 의미합니다. 만약 후속자가 존재하지 않는다면 null을 반환하면 됩니다.이 문제의 핵심 제약 조건은 트리의 루트(root)에는 접근할 수 없고, 주어진 노드에만 직접 접근이 가능하다는 점입니다. 대신 각 노드는 자신의 부모 노드에 대한 참조(p

문제 소개 검은색 픽셀과 흰색 픽셀로만 이루어진 그림이 주어졌을 때, 외로운 검은 픽셀(black lonely pixel)의 개수를 찾는 것이 이번 문제의 목표입니다. 그림은 검은 픽셀을 나타내는 B와 흰 픽셀을 나타내는 W로 구성된 2차원 char 배열로 표현됩니다. 외로운 검은 픽셀이란, 자신이 속한 행과 열 어디에도 다른 검은 픽셀이 존재하지 않는 위치에 있는 B를 의미합니다. 예를 들어 입력이 아래와 같다고 가정해 보겠습니다. WWB WBW BWW 이때 출력은 3입니다. 세 개의 B가 서로 다른 행과 서로 다른 열에

양의 정수 n이 주어졌을 때, 연속된 양의 정수들로 이루어진 목록 중 그 합이 정확히 n이 되는 경우의 수를 구하는 문제입니다.예를 들어 n = 15라면 정답은 4가 됩니다. 가능한 목록은 다음과 같습니다.[1, 2, 3, 4, 5][4, 5, 6][7, 8][15]접근 방법: 슬라이딩 윈도우(투 포인터)이 문제는 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 구간의 시작점(begin)과 끝점(end)을 두 포인터로 관리하면서, 두 포인터 사이 값들의 합(sum)을 조건에 맞게 늘리거나 줄여가며 답을 셉니다.알고리즘 단계

문제 개요정렬된 두 개의 리스트가 주어졌을 때, 이 두 리스트를 합쳤을 때의 중앙값(median)을 구하는 것이 목표입니다. 예를 들어 배열이 [1,5,8]과 [2,3,6,9]라면, 두 배열을 병합하면 [1,2,3,5,6,8,9]가 되고 전체 길이는 7(홀수)이므로 중앙값은 5입니다.두 배열을 단순히 병합한 뒤 중앙값을 찾는 방법은 O(n+m)의 시간이 걸리지만, 이진 탐색(Binary Search)을 활용하면 O(log(min(n, m))) 시간 안에 훨씬 효율적으로 해결할 수 있습니다.알고리즘 접근 방법핵심 아이디어는 두 배열을

어떤 수 n이 주어졌을 때, n번째 못생긴 수(ugly number)를 찾아야 합니다. 여기서 못생긴 수란 소인수가 오직 2, 3, 5뿐인 수를 의미합니다. 예를 들어 10번째 못생긴 수는 12입니다. 처음 몇 개의 못생긴 수가 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 순으로 나열되기 때문입니다.해결 알고리즘이 문제는 동적 계획법(DP)의 개념을 활용하면 효율적으로 풀 수 있습니다. 이미 구한 못생긴 수에 2, 3, 5를 곱한 값 역시 반드시 못생긴 수라는 성질을 이용합니다. 세 개의 포인터(인덱스)를 두고, 각 단계

문제 소개정수 N이 입력으로 주어졌을 때, 1≤A≤N과 1≤B≤N을 만족하는 모든 쌍 (A, B) 중에서 최대공약수 GCD(A, B)가 B가 되는 쌍의 개수를 구하는 것이 목표입니다. 즉, 모든 유효한 쌍에서 B가 곧 두 수의 최대공약수가 되어야 합니다.예시를 통해 자세히 살펴보겠습니다.입력 − N=5출력 − gcd(A, B)가 B가 되는 (A ≤ N, B ≤ N) 쌍의 개수 − 10설명gcd(A, B)가 B가 되는 (A ≤ N, B ≤ N) 쌍은 다음과 같습니다 −(1,1), (2,1), (3,1), (4,1), (5,1), (2

숫자 N이 입력으로 주어졌을 때, 자릿수에 포함된 0의 개수가 짝수인 모든 N자리 숫자의 개수를 구하는 것이 이 문제의 목표입니다. 여기서는 앞자리 0(선행 0)도 허용합니다. 예를 들어 N=3이라면 001, 002, 003 … 010 … 처럼 0으로 시작하는 숫자들까지 모두 포함됩니다. 구체적인 예시를 통해 살펴보겠습니다. 입력 − N=4 출력 − 0이 짝수 개 포함된 N자리 숫자의 개수 − 7047 설명 − 4자리 숫자들은 다음과 같이 구성됩니다. 가장 작은 수는 0000이며, 그다음은 0011, 0012, 0013, 0014

문제 개요 숫자 N이 입력으로 주어집니다. 목표는 0을 홀수 개 포함하는 모든 N자리 숫자의 개수를 구하는 것입니다. 단, 000과 같이 선행 0(앞자리 0)으로 시작하는 조합도 유효한 숫자로 간주합니다. 입력 및 출력 예시 입력: N = 3 출력: 244 설명: 가능한 3자리 숫자 조합은 아래와 같이 구성됩니다. 가장 작은 수는 000이며, 이어서 011, 012, 013, 014 … 형태로 진행되어 가장 큰 수는 990입니다. 입력: N = 5 출력: 33616 설명: 가능한 5자리 숫자 조합은 아래와 같이 구성됩니다. 가장

두 문자열 str_1과 str_2가 입력으로 주어졌을 때, str_1에 포함된 문자들을 각각 한 번씩만 사용하여 str_2와 동일한 문자열을 최대 몇 개 만들 수 있는지 그 개수를 구하는 것이 목표입니다.참고 − 두 문자열의 모든 알파벳은 대소문자가 서로 일치한다고 가정합니다.구체적인 예시를 통해 이해해 보겠습니다.예시 1입력 − str_1 = abcaaaabca, str_2 = bca출력 − 생성 가능한 문자열의 발생 횟수: 2설명 − str_1 안에는 bca에 해당하는 조합이 두 곳에 존재합니다.str_1[1-3]=bca 와 s

이 문제에서는 0, 1, 2로만 구성된 문자열 str이 주어집니다. 목표는 0, 1, 2가 각각 같은 개수로 포함된 모든 부분 문자열을 찾아 그 개수를 구하는 것입니다. 예를 들어 str이 12012라면 조건을 만족하는 부분 문자열은 120, 201, 012 세 가지이므로 답은 3이 됩니다. 예제로 이해하기 입력 − str = 112200120 출력 − 0, 1, 2의 개수가 같은 부분 문자열의 개수: 5 설명 − 조건을 만족하는 부분 문자열은 다음과 같습니다. str[0-5]=112200, str[1-6]=122001, str[2

문제 소개 문자열 str이 주어졌을 때, str의 부분 문자열 중 첫 번째 문자와 마지막 문자가 서로 같은 것의 개수를 세는 것이 이번 문제의 목표입니다. 예를 들어 입력이 baca라면 조건을 만족하는 부분 문자열은 b, a, c, a, aca로 총 5개입니다. 예시로 이해하기 입력 − str=abaefgf 출력 − 첫 문자와 끝 문자가 같은 부분 문자열의 개수: 9 설명 − 조건을 만족하는 부분 문자열은 다음과 같습니다. a, b, a, e, f, g, f, aba, fgf → 총 9개 입력 − str=abcdef 출력 − 첫 문

문제 개요문자열 str이 주어졌을 때, str의 모든 부분 문자열 중에서 각 문자가 최대 k번까지만 등장하는 부분 문자열의 개수를 구하는 것이 목표입니다. 예를 들어 입력이 abc이고 k=1이라면, 조건을 만족하는 부분 문자열은 a, b, c, ab, bc, abc로 총 6개입니다.예제로 이해하기입력 − str = abc, k = 1출력 − 각 문자가 최대 1번씩 등장하는 부분 문자열의 개수: 6설명 − 조건을 만족하는 부분 문자열은 다음과 같습니다.a, b, c, ab, bc, abc. 총 6개입력 − str = bbddehj,