수학적 표현식을 컴퓨터로 계산하려면 전위 표기법(prefix) 또는 후위 표기법(postfix) 형태로 바꾸는 것이 효율적입니다. 중위 표기식(infix)을 후위 표기식으로 변환한 뒤에는, 정확한 결과를 얻기 위해 후위 표기식 평가(postfix evaluation) 알고리즘이 필요합니다. 후위 표기식을 평가할 때에도 스택(Stack) 자료구조를 활용합니다. 기본 동작 원리는 다음과 같습니다. 표현식을 왼쪽에서 오른쪽으로 한 글자씩 읽습니다. 피연산자(숫자)를 만나면 스택에 push합니다. 연산자를 만나면 스택에서 두 개의 값을

서로 다른 동전의 목록 C(c₁, c₂, …, cₙ)와 목표 금액 V가 주어졌을 때, 이 문제는 가장 적은 수의 동전을 사용하여 금액 V를 만드는 방법을 찾는 것입니다.참고: 각 종류의 동전은 무한개 있다고 가정합니다.이 문제에서는 동전의 종류가 C{1, 2, 5, 10}으로 주어지며, 각 동전은 무한개 사용할 수 있습니다. 요청된 금액을 만들기 위해 어떤 종류의 동전이든 가장 적은 개수를 사용하려고 합니다. 예를 들어 금액이 22라면 {10, 10, 2}, 즉 3개의 동전이 최소 개수가 됩니다.입력과 출력입력: 목표 금액. 예:

문제 개요이 문제에서는 양의 정수로 이루어진 리스트가 주어집니다. 각 정수는 현재 위치에서 최대 이동할 수 있는 칸 수를 의미합니다. 첫 번째 원소에서 출발하여 리스트의 마지막 원소에 도달할 때까지 필요한 최소 점프 횟수를 구하는 것이 목표입니다.동적 계획법(DP) 접근 방식동적 계획법으로 해결할 때는 최소 점프 횟수를 저장하기 위한 jumps 배열을 정의합니다. 여기서 jumps[i]는 0번 인덱스에서 i번 인덱스까지 도달하는 데 필요한 최소 점프 횟수를 나타냅니다.입력 및 출력 예시입력:정수 리스트 {1, 3, 5, 8, 9,

문제 개요모든 자연수는 하나 이상의 완전제곱수(1, 4, 9, 16, 25, ...)의 합으로 표현할 수 있습니다. 이 문제에서는 주어진 값을 완전제곱수의 합으로 나타낼 때 필요한 항의 최소 개수를 구해야 합니다.예를 들어 값이 95라면 다음과 같이 네 개의 제곱수로 표현할 수 있으므로 답은 4가 됩니다.95 = 92 + 32 + 22 + 12문제를 해결하는 기본 아이디어는 1부터 시작하여 점차 더 큰 완전제곱수를 차례로 살펴보는 것입니다. 값이 1부터 3 사이일 때는 반드시 1만을 사용해 표현해야 하므로, 각각 1개, 2개, 3개

문제 소개 모바일 숫자 키패드가 하나 주어집니다. 현재 누른 버튼을 기준으로 상·하·좌·우에 인접한 키만 누를 수 있으며, 대각선 방향의 키는 누를 수 없습니다. 또한 키패드의 *과 # 버튼은 사용이 금지되어 있습니다. 자릿수가 주어졌을 때, 위 규칙을 모두 지키면서 키패드로 만들 수 있는 숫자의 총 개수를 구하는 것이 이 문제의 목표입니다. 키 이동 규칙 예시 1 → 1, 2, 4 5 → 5, 2, 4, 6, 8 0 → 0, 8 7 → 7, 4, 8 (*은 제외) 입력과 출력 입력: 자릿수. 예를 들어 3자리 숫자 출력: 주

하나의 숫자가 주어졌을 때, 그 숫자를 n/2, n/3, n/4로 나누는 작업을 반복하여 세 부분씩 쪼개고, 이렇게 나누어 얻을 수 있는 최대 합을 구하는 것이 이번 문제의 목표입니다.예를 들어 50은 {25, 16, 12}로 나눌 수 있습니다. 이후 집합 {25, 16, 12}에 속한 각 숫자를 다시 세 부분으로 나누는 과정을 반복합니다. 모든 나누기가 끝나면 각 경우의 합을 계산하여 그중 최댓값을 찾습니다.이 문제는 재귀 호출로도 해결할 수 있지만, 재귀 방식에서는 동일한 값을 여러 번 중복 계산하게 됩니다. 따라서 동적 계획법

최적의 이진 탐색 트리(Optimal Binary Search Tree)란?정렬된 상태로 주어진 정수 집합과 각 키(key)의 검색 빈도(frequency) 배열이 있을 때, 이 데이터로 이진 탐색 트리(Binary Search Tree, BST)를 구성하여 모든 검색에 드는 총 비용을 최소화하는 것이 이 문제의 목표입니다.검색 비용은 노드의 깊이 × 해당 키의 빈도로 계산되므로, 자주 검색되는 키일수록 루트에 가까운 위치에 배치하는 것이 유리합니다. 이 문제는 부분 문제의 해를 저장하고 재활용하는 동적 계획법(Dynamic Pro

이 문제에서는 하나의 메인 문자열과 와일드카드 패턴이 주어지며, 주어진 와일드카드 패턴이 메인 텍스트와 일치하는지 여부를 판별하는 것이 목표입니다.와일드카드 패턴은 일반 문자 외에도 * 또는 ? 기호를 포함할 수 있습니다. ?는 임의의 단일 문자 하나와 대응되고, *는 빈 문자열을 포함한 임의 길이의 문자 시퀀스와 대응됩니다.매칭 규칙*를 만난 경우: 별표 문자 자체를 건너뛰고 패턴의 다음 문자 검사로 진행할 수 있습니다.?를 만난 경우: 텍스트의 현재 문자 하나만 소비하고, 패턴과 텍스트 모두 다음 문자로 넘어갑니다.일반 문자인

어떤 그룹에 n명의 친구가 있다고 가정해 봅시다. 각 사람은 혼자 남을 수도 있고, 다른 친구와 한 쌍(pair)을 이룰 수도 있습니다. 이때 친구들이 혼자 있거나 짝을 이루는 모든 가능한 방법의 수를 구하는 것이 이 문제의 목표입니다.여기서 한 가지 중요한 조건이 있습니다. 두 친구 p와 q가 한 쌍을 이룰 때, (p, q)와 (q, p)는 같은 경우로 봅니다. 즉, 순서는 고려하지 않습니다.문제 접근 방식n명의 친구가 있을 때, 짝을 이루거나 혼자 남는 방법의 수를 f(n)이라고 정의하겠습니다. 그러면 n번째 사람의 입장에서 두

회문 분할(Palindrome Partitioning) 알고리즘은 하나의 문자열을 입력으로 받아, 분할된 모든 부분 문자열이 회문(palindrome)이 되도록 문자열을 나누는 방법을 다룹니다.여기서 우리가 구해야 할 것은 주어진 문자열을 회문 단위로 분할하기 위해 필요한 최소 컷(cut)의 개수입니다.입력과 출력입력: 하나의 문자열. 예: ababbbabbababa 출력: 회문으로 분할하기 위한 최소 컷의 개수. 이 예제에서는 3번의 컷이 필요합니다. 분할 결과: a | babbbab | b | ababa알고리즘이 문제는 동적 계

이 문제에서는 주어진 집합을 각 부분집합의 합이 서로 같아지도록 두 개로 분할할 수 있는지 판별합니다.가장 먼저 집합에 포함된 모든 원소의 합을 구해야 합니다. 합이 짝수라면 두 집합으로 나눌 가능성이 있지만, 홀수라면 절대로 균등하게 나눌 수 없습니다.합이 짝수인 경우에는 partTable이라는 표를 만들어 다음 조건을 이용해 문제를 해결합니다.partTable[i, j]는 배열의 array[0]부터 array[j-1]까지의 원소들만 사용해 합이 i인 부분집합을 만들 수 있으면 true, 그렇지 않으면 false입니다.입력과 출력

가장 긴 회문 부분 수열이란?가장 긴 회문 부분 수열(Longest Palindromic Subsequence)은 주어진 문자열에서 순서를 유지한 채 일부 문자를 선택해 만들 수 있는 부분 수열(subsequence) 중, 앞에서 읽으나 뒤에서 읽으나 같은 회문(palindrome)이 되는 것 중 가장 긴 것을 찾는 문제입니다.여기서 중요한 점은 부분 수열은 반드시 연속적일 필요가 없다는 것입니다. 예를 들어 ABCDEEAB라는 문자열이 주어졌다면, 문자를 건너뛰어 선택해도 되므로 A, E, E, A를 골라 AEEA라는 길이 4의

행렬 체인 곱셈(Matrix Chain Multiplication)이란?여러 개의 행렬이 체인 형태로 주어졌을 때, 곱셈 연산 횟수를 최소화하는 최적의 곱셈 순서를 찾는 것이 행렬 체인 곱셈 문제의 목표입니다.행렬 곱셈은 결합법칙(associative law)이 성립하기 때문에, 네 개의 행렬 A, B, C, D가 있을 경우 A(BCD), (AB)(CD), (ABC)D, A(BC)D 등 다양한 순서로 계산할 수 있습니다. 그러나 어떤 순서로 묶어서 계산하느냐에 따라 필요한 스칼라 곱셈의 총 횟수가 크게 달라집니다. 따라서 우리의 과

두 개의 정수로 이루어진 쌍(pair)들의 사슬(chain)이 주어집니다. 각 쌍에서 첫 번째 정수는 항상 두 번째 정수보다 작으며, 사슬을 구성할 때도 동일한 규칙이 적용됩니다. 즉, 쌍 (x, y)를 쌍 (p, q) 뒤에 추가하려면 반드시 q < x 조건을 만족해야 합니다.이 문제는 가장 긴 증가 부분 수열(LIS) 문제와 유사한 방식으로 접근할 수 있습니다. 해결 순서는 다음과 같습니다.주어진 쌍들을 첫 번째 원소를 기준으로 오름차순 정렬합니다.각 쌍의 두 번째 원소(b)와 앞선 쌍의 두 번째 원소를 비교하여, 현재 쌍의

문제 개요0과 1로만 구성된 이진 행렬(binary matrix)이 주어졌을 때, 모든 원소가 1로 이루어진 가장 큰 정사각형 부분행렬을 찾는 것이 이 문제의 목표입니다.이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심은 원본 행렬과 같은 크기의 보조 행렬(size matrix)을 하나 만드는 것입니다. 보조 행렬의 각 칸 Size[i, j]에는 해당 위치를 오른쪽 아래 꼭짓점으로 하는, 모두 1로 이루어진 정사각형의 한 변 길이가 저장됩니다. 보조 행렬을 모두 채운 후 최

한 명의 거래자가 아침에 주식을 매수하고 저녁에 매도하는 방식으로 거래를 진행한다고 가정해 봅시다. 하루에 허용되는 거래는 최대 두 번이며, 두 번째 거래는 반드시 첫 번째 거래가 완료된 이후에만 시작할 수 있습니다. 이처럼 주식 가격 목록이 주어졌을 때, 거래자가 얻을 수 있는 최대 이익을 구하는 것이 이 문제의 목표입니다.입력과 출력입력:주식 가격 목록 {2, 30, 15, 10, 8, 25, 80}출력:총 이익은 100입니다. 가격 2에 매수하여 가격 30에 매도하면 이익은 28입니다.이후 가격 8에 다시 매수하여 가격 80에

최대 합 증가 부분 수열(Maximum Sum Increasing Subsequence)은 주어진 정수 목록에서 만들 수 있는 부분 수열 중, 모든 원소가 오름차순으로 배치되어 있으면서 그 합이 가장 큰 부분 수열을 의미합니다.이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 각 인덱스 i에 대해 arr[i]로 끝나는 최대 합 증가 부분 수열을 저장하는 배열 L을 사용하며, 여기서 L[i]는 array[i]로 끝나는 최대 합 증가 부분 수열이 됩니다.입력 및 출력입력: 정수 수열 {3,

문제 개요정수로 구성된 2차원 행렬이 주어졌을 때, 원소들의 합이 최대가 되는 직사각형(경우에 따라 정사각형) 부분 행렬을 찾는 것이 목표입니다.이 알고리즘의 핵심 아이디어는 왼쪽 열과 오른쪽 열을 고정하는 것에서 출발합니다. 두 열을 고정한 상태에서 각 행마다 왼쪽 열부터 오른쪽 열까지의 원소 합을 계산하여 임시 배열(temp)에 저장합니다. 그다음 이 1차원 배열에 카데인 알고리즘(Kadanes Algorithm)을 적용하면 최대 합을 가지는 연속 구간, 즉 위쪽 행(top)과 아래쪽 행(bottom)의 위치를 구할 수 있습니다

서로 다른 비용이 기록된 행렬(matrix)이 주어지고, 목적지 셀(destination cell)의 좌표도 함께 제공됩니다. 이때 시작 셀인 (0, 0)에서 목적지 셀까지 이동하는 최소 비용 경로를 찾아야 합니다.행렬의 각 셀은 해당 셀을 통과할 때 드는 비용을 의미합니다.한 셀에서 임의의 방향으로 자유롭게 이동할 수는 없습니다. 이동 가능한 방향은 다음 세 가지뿐입니다.오른쪽 셀바로 아래 셀오른쪽 아래 대각선 셀입력과 출력입력:비용 행렬과 목적지 좌표. 이 예제에서 목적지는 (2, 2)입니다.1 2 34 8 21 5 3출력:(0

다각형 내부에서 서로 교차하지 않는 대각선들이 삼각형을 이루도록 분할하는 것을 삼각분할(Triangulation)이라고 합니다. 이 글에서 다룰 문제는 다양한 삼각분할 방법 중 최소 비용이 드는 삼각분할을 찾는 것입니다.삼각분할의 총비용은 그것을 구성하는 개별 삼각형들의 가중치를 모두 더한 값으로 정의됩니다. 여기서 각 삼각형의 가중치는 세 변의 길이를 모두 더한 값, 즉 삼각형의 둘레(perimeter)로 계산합니다.입력과 출력입력: 다각형을 이루는 점들 {(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)} 출