문제 개요한 명의 셰프가 있다고 가정해 봅시다. 셰프는 자신이 만들 수 있는 n개의 요리에 대한 만족도(satisfaction) 데이터를 미리 수집해 두었습니다. 셰프는 어떤 요리든 1단위 시간 안에 완성할 수 있습니다.각 요리의 좋아요 시간 계수(Like-time coefficient)는 해당 요리까지 포함한 누적 조리 시간에 그 요리의 만족도를 곱한 값으로 정의됩니다. 즉, time[i] * satisfaction[i] 입니다.우리의 목표는 요리 준비 과정에서 얻을 수 있는 좋아요 시간 계수의 합 중 최댓값을 찾는 것입니다. 요

Amal과 Bimal이 돌 무더기를 가지고 게임을 하고 있습니다. 여러 개의 돌이 한 줄로 나열되어 있으며, 각 돌에는 stoneValue 배열에 주어진 숫자 값이 매겨져 있습니다. 두 사람은 번갈아 가며 차례를 진행하며, Amal이 먼저 시작합니다. 각 차례마다 플레이어는 줄 맨 앞에 남아 있는 돌 중에서 1개, 2개 또는 3개를 가져갈 수 있습니다. 각 플레이어의 점수는 자신이 가져간 돌 값들의 합이며, 초기 점수는 0입니다. 게임의 목표는 최대한 높은 점수로 마무리하는 것이고, 가장 높은 점수를 얻은 플레이어가 승자가 되며

n × 3 크기의 그리드가 있고, 각 칸을 빨강(Red), 노랑(Yellow), 초록(Green) 세 가지 색 중 정확히 하나로 칠하려고 합니다. 단, 인접한 두 칸은 서로 다른 색이어야 한다는 제약 조건이 있습니다. 그리드의 행 개수 n이 주어졌을 때, 이 그리드를 칠할 수 있는 서로 다른 방법의 수를 구하는 것이 문제입니다. 답이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.예를 들어 입력이 1이라면 출력은 12가 됩니다.문제 접근 방법이 문제의 핵심 아이디어는 각 행의 색 배치를 두 가지 유형으로 분

문제 개요배열 A의 원소들을 차례대로 출력하는 프로그램이 있다고 가정해 봅시다. 그런데 이 프로그램에 작은 실수가 있어 각 원소 사이에 공백이 삽입되지 않았습니다. 이렇게 얻은 하나의 문자열만으로 원래 배열을 다시 복원할 수 있을까요? 단, 배열의 모든 원소는 1부터 k 사이의 값이라는 조건이 주어집니다.문자열 s와 정수 k가 주어졌을 때, 배열을 복원할 수 있는 서로 다른 방법의 수를 구해야 합니다. 답이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 반환합니다.예를 들어 입력이 S = 1318, k = 2000이라면 출력

배열 nums와 정수 k가 주어졌을 때, 특정 조건을 만족하는 비어 있지 않은 부분 수열(subsequence) 중 합이 최대가 되는 값을 구하는 문제입니다.조건은 다음과 같습니다. 부분 수열에서 인접한 두 원소 nums[i]와 nums[j](i < j)에 대해 항상 j - i <= k를 만족해야 합니다.여기서 부분 수열이란 배열에서 일부 원소를 삭제한 뒤, 남은 원소들의 원래 순서를 그대로 유지한 것을 의미합니다.예를 들어 입력이 [10, 2, -9, 5, 19]이고 k = 2라면, 부분 수열 [10, 2, 5, 19]

n명의 사람과 1부터 40까지 번호가 매겨진 40가지 종류의 모자가 있다고 가정해 보겠습니다. 2차원 배열 hats가 주어지며, hats[i]는 i번째 사람이 선호하는 모자 번호들의 목록을 의미합니다. 우리가 구해야 할 것은 n명의 사람이 모두 서로 겹치지 않는 모자를 쓰도록 배정하는 방법의 수입니다. 답이 매우 커질 수 있으므로, 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다. 예를 들어 입력이 [[4,6,2],[4,6]]라고 한다면 출력은 4가 됩니다. 첫 번째 사람은 4, 6, 2번 모자 중 하나를, 두 번째

문제 개요m × n 크기의 행렬 mat과 정수 k가 주어졌다고 가정해 봅시다. 이 행렬의 각 행은 비내림차순(오름차순)으로 정렬되어 있습니다. 우리는 각 행에서 정확히 하나의 원소를 선택하여 하나의 배열을 만들 수 있으며, 이렇게 만들 수 있는 모든 배열의 합 중에서 K번째로 작은 합을 찾아야 합니다.예제로 이해하기입력이 다음과 같다고 가정해 보겠습니다.mat = [[1,3,11],[2,4,6]]1311246이때 k = 5라면 출력은 7이 됩니다. 각 행에서 하나씩 원소를 선택했을 때 가장 작은 합 5개는 순서대로 [1,2], [1

두 개의 문자열 S와 T가 주어졌을 때, S의 부분 수열 중 T와 정확히 일치하는 서로 다른 경우가 몇 가지인지 세어야 합니다. 먼저 부분 수열(subsequence)의 개념부터 살펴보겠습니다. 부분 수열이란 원본 문자열에서 일부 문자(없을 수도 있음)를 제거하되, 나머지 문자들의 상대적인 순서는 그대로 유지한 채 만들어진 새로운 문자열을 의미합니다. 예를 들어 ACE는 ABCDE의 부분 수열이지만, AEC는 문자 순서가 바뀌었으므로 부분 수열이 아닙니다. 입력 문자열이 baalllloonnn과 balloon이라면, 두 번째 문자열

이진 트리(binary tree)가 하나 있다고 가정해 보겠습니다. 이때 재귀 함수를 사용하지 않고, 오직 반복(iterative) 방식만으로 이 트리의 후위 순회(postorder traversal) 결과를 구해야 합니다.예를 들어 아래와 같은 트리가 있다고 합시다.이 트리에 대한 후위 순회 결과는 다음과 같습니다.[9, 15, 7, 10, -10]후위 순회란 무엇인가?후위 순회는 트리 순회 방식 중 하나로, 각 노드를 왼쪽 자식 → 오른쪽 자식 → 부모(루트) 순서로 방문하는 방법입니다. 즉, 자식 노드들을 모두 처리한 뒤에야

C++에서 Set과 MultiSet은 모두 데이터를 효율적으로 저장하고 빠르게 접근·삽입할 수 있도록 설계된 연관 컨테이너(associative container)입니다. 두 자료구조는 사용 방법이 매우 유사하지만, 중복 값을 처리하는 방식에서 결정적인 차이가 있습니다.아래 표에서 Set과 MultiSet의 핵심적인 차이점을 항목별로 살펴보겠습니다.Set과 MultiSet의 주요 차이점번호구분 기준SetMultiSet1정의Set은 C++의 연관 컨테이너로, 각 원소의 값(value)이 곧 그 원소를 식별하는 키(key) 역할을 하며

C++에서 set과 unordered_set은 모두 데이터를 효율적으로 저장하고 빠르게 접근·삽입할 수 있도록 설계된 연관 컨테이너(associative container)입니다. 두 컨테이너는 이름이 비슷해 같은 기능을 하는 것처럼 보이지만, 내부 구현 방식과 데이터 저장 순서, 성능 특성에서 중요한 차이가 있습니다.아래 표에서 set과 unordered_set의 핵심적인 차이점을 확인해 보세요.set과 unordered_set의 주요 차이점번호구분setunordered_set1정의C++ STL(표준 템플릿 라이브러리)에서 제공하

문제 개요 정렬된 배열과 하나의 목표 값(target)이 주어졌을 때, 해당 값이 배열에 존재한다면 그 인덱스를 찾아야 합니다. 만약 값이 존재하지 않는다면, 정렬 순서가 유지되도록 삽입했을 때의 인덱스를 반환해야 합니다. 예를 들어, 입력 배열이 [1, 3, 4, 6, 6]이고 target이 5라면 결과는 3이 됩니다. 인덱스 3에 5를 삽입하면 배열이 [1, 3, 4, 5, 6, 6]이 되어 정렬 상태가 유지되기 때문입니다. 접근 방법: 이진 탐색 활용 이 문제는 이진 탐색(Binary Search)을 활용하면 O(log n)의

문자열 s가 주어졌다고 가정해 봅시다. 이 문자열은 영어 알파벳과 공백(white-space)을 포함할 수 있습니다. 우리가 해야 할 일은 이 문자열에서 마지막 단어의 길이를 구하는 것이며, 만약 마지막 단어가 존재하지 않는다면 0을 반환하면 됩니다.예를 들어, 입력 문자열이 I love Programming이라면 마지막 단어는 Programming이고, 그 길이는 11이므로 출력 결과는 11이 됩니다.문제 해결 접근 방법이 문제는 다음과 같은 단계로 해결할 수 있습니다.결과를 저장할 변수 n을 0으로 초기화합니다.문자열을 단어 단

문제 개요정렬된 연결 리스트(Linked List)가 주어졌을 때, 모든 중복 요소를 제거하여 각 값이 한 번만 나타나도록 만들어야 합니다.예를 들어 입력이 [1,1,2,3,3,3,4,5,5]라면, 출력은 [1,2,3,4,5]가 됩니다.접근 방법리스트가 이미 정렬되어 있으므로, 서로 인접한 노드끼리만 비교하면 중복을 쉽게 찾을 수 있습니다. 이때 더미(dummy) 노드를 활용하면 헤드 노드 처리 로직을 단순화할 수 있습니다. 알고리즘의 진행 순서는 다음과 같습니다.값이 INT_MIN인 더미 노드를 생성하고, 그 next를 head에

두 개의 이진 트리가 주어졌을 때, 이 두 트리가 서로 같은지 판별하는 함수를 정의해야 합니다. 두 이진 트리는 구조적으로 완전히 동일하고 각 노드의 값까지 일치할 때 같은 트리(Same Tree)로 간주됩니다. 예를 들어 입력이 [1,2,3]과 [1,2,3]으로 동일하다면 출력은 True(참)가 됩니다. 문제 해결 접근 방법 이 문제는 재귀(Recursion)를 활용하면 간단하게 해결할 수 있습니다. 다음 단계를 따릅니다. 두 개의 트리 노드 p와 q를 매개변수로 받는 isSameTree 함수를 정의합니다. p와 q가 모두 NU

문제 설명 하나의 이진 트리(binary tree)가 주어졌을 때, 해당 트리의 최소 깊이(minimum depth)를 구하는 것이 이 글의 목표입니다. 여기서 최소 깊이란 루트 노드에서 가장 가까운 리프(leaf) 노드까지의 최단 경로에 포함된 노드의 개수를 의미합니다. 예를 들어, 아래와 같은 이진 트리가 입력으로 주어진다고 가정해 보겠습니다. 루트 노드(3)에서 가장 가까운 리프 노드는 9이므로, 이 경우 출력 결과는 2가 됩니다. 접근 방법: BFS(너비 우선 탐색) 이 문제는 레벨 순회(level-order traver

파스칼의 삼각형(Pascals Triangle)은 각 행의 양 끝이 1이고, 나머지 값은 바로 위 행의 인접한 두 수를 더해 만들어지는 삼각형 형태의 수열입니다.이 문제에서는 0 이상의 인덱스 k(k ≤ 33)가 주어졌을 때, 파스칼의 삼각형에서 k번째 행을 구하는 것이 목표입니다.예를 들어 입력이 3이라면, 출력은 다음과 같습니다.[1, 3, 3, 1]접근 방법이 문제는 O(k)의 추가 공간만 사용하는 제자리(in-place) 갱신 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 한 개의 배열만 사용하면서, 각 단계마다

문제 개요양의 정수가 하나 주어졌을 때, 이를 엑셀 시트에서 실제로 사용되는 열 제목으로 변환하는 문제입니다. 엑셀의 열 제목은 다음과 같은 규칙을 따릅니다.1 → A2 → B26 → Z27 → AA28 → AB예를 들어 입력값이 28이라면 출력 결과는 AB가 됩니다.접근 방법이 문제는 26진법 변환과 유사하지만, 엑셀 열 제목에는 0에 해당하는 개념이 없다는 점이 특징입니다. 즉, A부터 Z까지가 1~26에 대응하기 때문에 일반적인 진법 변환과는 약간 다른 처리가 필요합니다.해결 알고리즘은 다음과 같습니다.n이 0이 아닌 동안 아

두 개의 문자열 s와 t가 주어졌을 때, 이 두 문자열이 동형(isomorphic)인지 확인하는 문제를 살펴보겠습니다.동형 문자열이란?동형 문자열이란 s에 포함된 문자들을 다른 문자로 치환했을 때 t를 만들 수 있는 경우를 의미합니다. 단, 치환 과정에서 다음 규칙을 반드시 지켜야 합니다.모든 문자는 순서를 유지한 채 일관되게 치환되어야 합니다. 즉, 한 번 치환된 문자는 이후에도 항상 같은 문자로 치환되어야 합니다.서로 다른 두 문자가 같은 문자로 매핑될 수는 없습니다.반면, 한 문자는 자기 자신으로 매핑되는 것이 허용됩니다.예를

문제 개요배열 하나와 정수 k가 주어졌을 때, 배열 안에서 서로 다른 두 인덱스 i와 j가 존재하여 다음 두 조건을 동시에 만족하는지 판별하는 문제입니다.nums[i] = nums[j] (두 위치의 값이 같음)|i − j| ≤ k (두 인덱스의 절댓값 차이가 k 이하)예를 들어 입력 배열이 [1, 2, 4, 1]이고 k = 3이라면, 값 1이 인덱스 0과 3에 존재하고 두 인덱스의 차이가 3으로 k 이하이므로 결과는 True가 됩니다.해결 접근 방식이 문제는 값과 인덱스를 묶어 정렬한 뒤 인접한 원소들을 비교하는 방식으로 해결할 수