삼각형 형태의 숫자 배열이 주어졌을 때, 꼭대기에서 바닥까지 이동하는 최소 경로 합을 구하는 문제를 살펴보겠습니다. 이동 규칙은 간단합니다. 각 단계에서 바로 아래 행에 있는 인접한 숫자로만 이동할 수 있습니다.문제 예시다음과 같은 삼각형이 있다고 가정해 보겠습니다.[ [2], [3,4], [6,5,7], [4,1,8,3] ]이 경우 꼭대기에서 바닥까지의 최소 경로 합은 11입니다. 실제 경로는 2 → 3 → 5 → 1이며, 이들의 합이 정확히 11이 됩니다.해결 접근 방식: 동적 계획법이 문제는 동적

C++ 회문 분할(Palindrome Partitioning)이란?회문 분할은 하나의 입력 문자열을 여러 부분으로 나누었을 때, 분할된 모든 부분 문자열이 회문(팰린드롬)이 되도록 하는 것을 의미합니다. 이 글에서는 주어진 문자열을 회문으로 분할하기 위해 필요한 최소 컷(cut) 횟수를 구하는 방법을 다룹니다.예를 들어 문자열이 ababbbabbababa라고 가정해 보겠습니다. 이 문자열을 아래와 같이 분할하면 딱 3번의 컷만으로 모든 조각을 회문으로 만들 수 있습니다.a | babbbab | b | ababa해결 알고리즘: 동적

문제 소개원 위에 n개의 주유소가 배치되어 있다고 가정해 봅시다. 각 주유소마다 다음 두 가지 데이터가 주어집니다.기름의 양 — 해당 주유소에서 채울 수 있는 연료의 양거리 — 현재 주유소에서 다음 주유소까지의 거리목표는 자동차가 중간에 기름이 바닥나지 않고 원형 코스를 한 바퀴 완주할 수 있는 최초의 출발 지점을 찾는 것입니다. 계산을 단순화하기 위해 기름 1단위로 거리 1단위를 이동할 수 있다고 가정합니다.예를 들어 주유소가 네 곳 있고, 각 주유소의 기름량과 다음 주유소까지의 거리가 [(4, 6), (6, 5), (7, 3),

역폴란드 표기법(Reverse Polish Notation, RPN)은 후위 표기법(postfix expression)이라고도 불리는 수식 표현 방식입니다. 이 표기법은 연산자가 피연산자 뒤에 오는 특징이 있어, 괄호 없이도 연산 우선순위를 명확하게 나타낼 수 있습니다.후위 표기법으로 작성된 수식의 값을 계산할 때는 스택(stack) 자료구조를 활용하는 것이 가장 효율적입니다. 계산 원리는 다음과 같습니다.수식을 왼쪽부터 읽다가 피연산자를 만나면 스택에 push합니다.연산자를 만나면 스택에서 두 개의 항목을 pop한 뒤, 올바른 순

어떤 수식(표현식)이 주어졌을 때, 그 안의 괄호가 서로 균형 잡혀 있는지(balanced) 확인해야 하는 경우가 있습니다. 검사 대상이 되는 괄호의 종류는 (), {}, [] 세 가지입니다.예를 들어 두 개의 문자열이 있다고 가정해 보겠습니다.()[(){()}] → 모든 괄호가 올바른 순서로 짝을 이루므로 유효(valid)합니다.{[}] → 짝이 맞지 않는 괄호가 존재하므로 유효하지 않습니다(invalid).문제 해결 접근 방법이 문제는 스택(Stack) 자료구조를 이용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은

문제 개요 서로 중복되지 않는 숫자들로 구성된 후보 배열과 하나의 목표 값(target)이 주어집니다. 이때 후보 숫자들을 조합하여 그 합이 목표 값과 일치하는 모든 고유한 조합을 찾아야 하며, 동일한 숫자를 두 번 이상 선택할 수는 없습니다. 예를 들어 후보 배열이 [2, 3, 6, 7, 8]이고 목표 값이 10이라면, 가능한 결과는 [[2, 8], [3, 7]]입니다. 해결 접근 방식: 백트래킹 이 문제는 재귀와 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 각 단계에서 숫자를 하나씩 선택해

집합이 [1, 2, 3, ..., n]과 같을 때, 이 집합은 총 n!개의 서로 다른 순열을 가집니다. 모든 순열을 나열하고 순서대로 번호를 붙이면 n = 3일 때 다음과 같은 시퀀스를 얻습니다.[123, 132, 213, 231, 312, 321]따라서 n과 k가 주어졌을 때, k번째 순열 시퀀스를 반환해야 합니다. 여기서 n은 1부터 9까지(포함), k는 1부터 n!까지(포함)의 범위를 가집니다. 예를 들어 n = 4, k = 9가 주어지면 결과는 2314가 됩니다.문제 해결 접근 방식모든 순열을 생성한 후 k번째를 찾는 비효율

연결 리스트(linked list)가 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 일은 이 리스트를 오른쪽으로 k칸 회전시키는 것입니다. 단, k는 음수가 아닌 값입니다.예를 들어 리스트가 [1, 2, 3, 4, 5, NULL]이고 k = 2라면, 마지막 두 개의 노드(4, 5)가 앞으로 이동하여 출력 결과는 [4, 5, 1, 2, 3, NULL]이 됩니다.알고리즘 접근 방식이 문제는 리스트를 임시로 원형(circular) 리스트로 만든 뒤 적절한 위치에서 끊어내는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음

문제 소개 n × m 크기의 격자(n행, m열)가 있고, 그 왼쪽 상단 모서리에 로봇이 위치해 있다고 가정해 봅시다. 로봇은 임의의 시점에서 아래쪽 또는 오른쪽으로만 이동할 수 있습니다. 로봇의 목표는 격자의 오른쪽 하단 모서리(아래 표에서 END로 표시된 지점)에 도달하는 것입니다. 이때 시작점에서 끝점까지 갈 수 있는 고유한 경로의 총 개수를 구하는 것이 이 문제의 핵심입니다. 예를 들어 m = 3, n = 2라면 격자는 다음과 같습니다. Robo     END 이 경우 출력값은 3입니

n×m 크기의 격자(그리드)가 있고, 로봇이 왼쪽 상단 모서리에 위치해 있다고 가정해 보겠습니다. 로봇은 임의의 시점에서 아래쪽 또는 오른쪽으로만 이동할 수 있습니다. 로봇의 목표는 격자의 오른쪽 하단 모서리(아래 표에서 END로 표시된 위치)에 도달하는 것입니다.격자의 일부 칸은 장애물로 표시되어 있으며, 로봇은 해당 칸을 지나갈 수 없습니다. 따라서 우리는 시작 위치에서 도착 위치까지 갈 수 있는 고유한 경로의 총 개수를 구해야 합니다.예를 들어 격자가 [[0,0,0],[0,1,0],[0,0,0]]과 같다면, 격자는 아래와 같이

음이 아닌 정수로 채워진 m × n 크기의 행렬이 있다고 가정해 봅시다. 이때 좌측 상단 모서리에서 우측 하단 모서리까지 이동하는 경로 중, 경로에 포함된 숫자들의 합이 최소가 되는 경로를 찾는 것이 목표입니다.여기서 중요한 제약 조건은 한 번에 이동할 수 있는 방향이 아래쪽 또는 오른쪽으로만 가능하다는 점입니다.예를 들어 다음과 같은 행렬이 주어졌다고 해보겠습니다.131151421이 경우 출력값은 7입니다. 실제 최소 경로는 1 → 3 → 1 → 1 → 1이며, 이 경로를 따라 이동했을 때 숫자의 합이 가장 작아지기 때문입니다.알

이 문제에서는 두 개의 배열 x[]와 y[]가 주어지며, 각 쌍 (x, y)는 2차원 평면 위의 한 점의 좌표를 나타냅니다. 우리의 과제는 모든 좌표점을 오름차순으로 출력하고, 각 점이 나타난 횟수(빈도)를 함께 출력하는 것입니다.문제 이해를 위한 예시입력: x[] = {0, 1, 1, 0, 0} ; y[] = {1, 2, 2, 2, 1}출력:(0, 1) = 2(1, 2) = 2(0, 2) = 1해결 방법이 문제를 해결하려면 각 좌표점의 등장 빈도를 저장해야 합니다. 이를 위해 맵(map) 자료구조를 활용하는 것이 가장 효과적입니다

m x n 크기의 행렬에서 특정 값을 빠르게 찾는 효율적인 알고리즘을 작성해야 한다고 가정해 봅시다. 이 행렬은 다음과 같은 중요한 특성을 가지고 있습니다.각 행은 왼쪽에서 오른쪽 방향으로 오름차순 정렬되어 있습니다.각 행의 첫 번째 숫자는 항상 이전 행의 마지막 정수보다 큽니다.즉, 행렬 전체를 왼쪽 위에서 오른쪽 아래까지 순서대로 읽으면 하나의 정렬된 배열처럼 동작하는 구조입니다. 예를 들어 행렬이 다음과 같다고 해 보겠습니다.1357101116202330345053627898이때 찾으려는 목표 값(target)이 16이라면,

문제 개요정렬된 배열 nums가 주어졌을 때, 각 중복 원소가 최대 두 번까지만 나타나도록 배열 자체(in-place)에서 중복을 제거하고, 새로운 길이를 반환해야 합니다.이 문제의 핵심 제약 조건은 추가 공간을 사용할 수 없다는 점입니다. 즉, O(1)의 공간 복잡도만으로 문제를 해결해야 합니다.예를 들어, 배열이 [0,0,0,1,1,1,1,2,3,3]과 같다면, 출력은 [0,0,1,1,2,3,3]이 되고, 그 길이는 7입니다.해결 알고리즘투 포인터(Two Pointer) 기법을 활용하면 추가 메모리 없이 효율적으로 해결할 수 있

문제 개요오름차순으로 정렬된 배열이 있다고 가정해 봅시다. 이 배열은 우리가 미리 알 수 없는 어떤 피벗(pivot)을 기준으로 회전되어 있습니다. 예를 들어 [0,0,1,2,2,5,6]과 같은 배열은 회전 과정에서 [2,5,6,0,0,1,2]로 바뀔 수 있습니다.여기서 특정 값(target)이 주어졌을 때, 해당 값이 배열 안에 존재하면 true, 존재하지 않으면 false를 반환하는 것이 이번 문제의 목표입니다. 예를 들어 배열이 [2,5,6,0,0,1,2]이고 target이 0이라면, 결과는 true가 됩니다.이 문제가 일반적

이 문제에서는 두 개의 숫자 n과 k가 주어지며, 우리의 과제는 숫자 n의 k번째 최하위 비트(Least Significant Bit)를 출력하는 것입니다.예시를 통해 문제를 이해해 보겠습니다.입력: n = 12, k = 3 출력: 1 설명: n의 이진수 표현을 살펴보면 다음과 같습니다. 12 = 1100위 예제에서 3번째 최하위 비트의 값은 1입니다.문제 해결 접근 방법이 문제를 해결하기 위해서는 숫자의 이진 비트를 활용하여 k번째 비트를 추출해야 합니다. 이를 위해 비트 시프트(bit shift) 연산을 사용합니다.구체적인 방법

정렬된 연결 리스트가 주어졌을 때, 두 번 이상 등장한 모든 요소를 제거하여 고유한(distinct) 요소만 남기는 것이 이 문제의 목표입니다. 예를 들어 입력 리스트가 [1,1,1,2,2,3,5,6,6,7,8]이라면, 1·2·6은 각각 여러 번 나타나므로 모두 제거되고 최종 결과는 [3,5,7,8]이 됩니다.이 문제는 더미(dummy) 노드를 활용해 결과 리스트를 새로 구성하는 방식으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 현재 노드와 다음 노드의 값을 비교하여, 중복 구간 전체를 한 번에 건너뛰고 고유한 값만 결과 리스

이 문제에서는 하나의 숫자 n이 주어지며, 우리의 과제는 해당 숫자의 프리모리얼(Primorial) 값을 출력하는 것입니다. 프리모리얼 수(Pn#)란 처음 n개의 소수를 모두 곱한 값을 의미합니다. 프리모리얼은 일반적인 팩토리얼(factorial)과 매우 유사한 개념입니다. 차이점이 있다면, 팩토리얼은 1부터 n까지의 모든 자연수를 곱하는 반면, 프리모리얼은 오직 소수(prime number)만을 사용하여 곱셈을 수행한다는 점입니다. 구체적인 예시를 통해 문제를 이해해 보겠습니다. 입력: N = 4 출력: 210 설명: 프리모리얼

문제 소개 숫자로 이루어진 집합이 하나 주어졌을 때, 그 집합으로 만들 수 있는 모든 부분집합을 생성해야 합니다. 이렇게 얻어진 전체 집합을 흔히 멱집합(power set)이라고 부릅니다. 다만 주의할 점은 집합의 요소들이 중복될 수 있다는 것입니다. 따라서 동일한 부분집합이 결과에 여러 번 등장하지 않도록 처리해야 합니다. 예를 들어 입력 집합이 [1,2,2]라면, 최종 멱집합은 다음과 같습니다. [[], [1], [2], [1,2], [2,2], [1,2,2]] 풀이 접근 방법 이 문제는 재귀(recursion)를 활용한 백트

문제 설명 이 문제에서는 하나의 소수 N이 주어지며, 우리의 과제는 N modulo N에 대한 원시근(primitive root)을 찾아 출력하는 것입니다. 소수 N의 원시근이란 [1, N-1] 범위에 속하는 정수 x 중에서, k가 [0, N-2] 범위에 있을 때 xk (mod N)의 값들이 모두 서로 다르게 나타나는 수를 의미합니다. 쉽게 말해, x의 거듭제곱을 N으로 나눈 나머지가 1부터 N-1까지의 모든 값을 빠짐없이 한 번씩 순환하는 수입니다. 예시를 통해 문제를 살펴보겠습니다. 입력: 13 출력: 2 13의 경우 2가 원시