문제 개요큐(Queue)를 사용하여 하나의 스택(Stack)을 구현한다고 가정해 보겠습니다. 이를 위해서는 스택에 필요한 다음과 같은 메서드들을 정의해야 합니다.push(x) − x를 스택에 삽입합니다.pop() − 스택의 최상단 요소를 제거한 후 반환합니다.top() − 스택의 최상단 요소를 반환합니다.empty() − 스택이 비어 있는지 여부를 반환합니다.예를 들어, push(10)과 push(20)을 차례로 호출한 뒤 pop()을 두 번 호출하면 출력 결과는 20, 10 순서로 나타납니다. 이는 스택의 LIFO(Last In

문제 개요하나의 패턴(pattern)과 하나의 문자열(str)이 주어졌을 때, 문자열이 해당 패턴을 따르는지 확인하는 문제입니다. 여기서 패턴을 따른다는 것은 패턴의 각 문자와 문자열 내의 비어 있지 않은 단어 사이에 전단사(bijection) 관계, 즉 일대일 대응이 성립한다는 의미입니다.예를 들어 입력이 다음과 같다면:pattern = cbbcstr = word pattern pattern word출력은 True가 됩니다. c는 word에, b는 pattern에 각각 일관되게 대응되기 때문입니다.해결 접근 방식핵심 아이디어는 패

문제 소개두 명의 플레이어가 함께 즐기는 님 게임(Nim Game)을 생각해 봅시다. 돌무더기가 하나 주어지고, 플레이어들은 번갈아 가며 자신의 차례에 1개부터 3개까지의 돌을 제거합니다. 마지막 돌을 가져가는 사람이 승자가 되며, Player1이 항상 먼저 시작합니다. 또한 두 플레이어 모두 매우 똑똑하여 항상 최적의 전략으로 게임을 진행한다고 가정합니다.우리가 설계해야 할 것은 돌무더기에 있는 돌의 개수 n이 주어졌을 때, Player1이 이 게임에서 승리할 수 있는지를 판단하는 알고리즘입니다.예시입력이 5라고 가정해 보겠습니다

정수가 하나 주어졌을 때, 그 수가 4의 거듭제곱인지 아닌지를 판별하는 것이 이번 문제의 목표입니다. 예를 들어 입력값이 16이라면, 16은 4²(=16)이므로 결과는 True가 됩니다. 해결 접근 방법 이 문제는 비트 연산(bit manipulation)을 활용하면 매우 효율적으로 해결할 수 있습니다. 알고리즘은 다음 단계를 따릅니다. num이 0보다 작다면 → false를 반환합니다. num & (num - 1)의 결과가 0이 아니라면 → false를 반환합니다. (num & 010101010101010101

문제 소개두 개의 배열이 주어졌을 때, 두 배열의 교집합(intersection)을 구하는 문제입니다.예를 들어 입력이 [1,5,3,6,9]와 [2,8,9,6,7]이라면, 두 배열에 공통으로 존재하는 원소는 9와 6이므로 출력은 [9,6]이 됩니다.해결 접근 방법이 문제는 해시 맵(unordered_map)을 활용하면 효율적으로 해결할 수 있습니다. 각 배열의 원소 빈도를 기록한 뒤, 양쪽 모두에 존재하는 원소만 결과에 담는 방식입니다.알고리즘은 다음과 같은 단계로 진행됩니다.두 개의 맵 mp1, mp2를 정의합니다.결과를 저장할

문제 소개숫자 추측 게임(Guess Game)을 한 번쯤 해본 적이 있을 것입니다. 이 게임의 규칙은 다음과 같습니다.플레이어 1이 1부터 n 사이의 숫자 하나를 정합니다. 플레이어 2는 그 숫자가 무엇인지 맞춰야 하며, 틀릴 때마다 플레이어 1은 정답이 자신이 고른 숫자보다 높은지 낮은지 알려줍니다.이를 위해 guess(num) 함수를 사용할 수 있으며, 이 함수는 다음 세 가지 결과 중 하나를 반환합니다.-1: 플레이어 1의 숫자가 추측한 값보다 낮음1: 플레이어 1의 숫자가 추측한 값보다 높음0: 숫자를 정확히 맞춤예를 들어

소문자로만 구성된 두 문자열 s와 t가 있다고 가정해 보겠습니다. 문자열 t는 문자열 s를 무작위로 섞은 뒤, 임의의 위치에 한 글자를 추가하여 생성됩니다. 우리가 해야 할 일은 바로 t에 새롭게 추가된 그 문자를 찾아내는 것입니다.예를 들어 입력이 mnopq, pqmnot라면 출력은 t가 됩니다. 이 t가 바로 추가된 문자입니다.해결 접근 방법이 문제는 아스키(ASCII) 코드 값의 합을 활용하면 매우 효율적으로 해결할 수 있습니다. 문자마다 고유한 아스키 코드 값이 존재한다는 점을 이용하여, 두 문자열의 전체 합을 비교하는 것입

정수가 하나 주어졌을 때, 이를 16진수(hexadecimal) 문자열로 변환하는 알고리즘을 설계해야 합니다. 이때 음수가 입력되는 경우에는 2의 보수(twos complement) 방식을 적용하여 처리합니다.예를 들어 입력값이 254와 -12라면, 결과는 각각 fe와 fffffff4가 됩니다.문제 해결 접근 방법이 문제는 다음 단계를 통해 해결할 수 있습니다.입력값 num1이 0이라면 즉시 0을 반환합니다.num에 num1을 저장합니다.빈 문자열 s를 준비합니다.num이 0이 아닐 때까지 다음 과정을 반복합니다.temp = num

문제 개요소문자 또는 대문자로만 이루어진 문자열이 주어졌을 때, 이 문자들을 조합하여 만들 수 있는 가장 긴 회문(palindrome)의 길이를 찾아야 합니다.단, 문자열은 대소문자를 엄격하게 구분하므로 Aa는 회문으로 인정되지 않습니다.예를 들어 입력이 abccccdd라면, 만들 수 있는 가장 긴 회문 중 하나는 dccaccd이며 그 길이는 7입니다. 따라서 출력값은 7이 됩니다.해결 접근 방법회문의 핵심 성질을 활용하면 문제를 쉽게 해결할 수 있습니다.각 문자의 등장 횟수를 먼저 계산합니다.짝수 개로 등장하는 문자들은 회문 양쪽

비어 있지 않은 정수 배열이 주어졌을 때, 이 배열에서 세 번째로 큰 수(third maximum number)를 찾는 문제입니다. 만약 세 번째 최댓값이 존재하지 않는다면 배열의 최댓값을 대신 반환해야 합니다.이 문제의 핵심 조건은 선형 시간 복잡도 O(n)으로 해결해야 한다는 점입니다. 즉, 배열을 정렬하는 방식(O(n log n))은 사용할 수 없으며, 배열을 한 번만 순회하면서 답을 구해야 합니다.문제 이해하기예를 들어 입력 배열이 [5, 3, 8, 9, 1, 4, 6, 2]라고 가정해 보겠습니다. 이 배열을 내림차순으로 정

문제 개요문자열 s가 주어졌을 때, 이 문자열에 포함된 세그먼트(segment)의 개수를 구하는 것이 목표입니다. 여기서 세그먼트란 공백을 포함하지 않는 연속된 문자들의 묶음을 의미합니다.예를 들어, 입력 문자열이 Hello, I love programming이라면 세그먼트가 총 4개이므로 출력값은 4가 됩니다.해결 접근 방법이 문제는 문자열을 한 번만 순회하면 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.세그먼트 개수를 저장할 변수 n을 0으로 초기화합니다.i를 0으로 초기화하고, i가 문자열 길이보다 작은 동안

문제 설명n개의 동전이 주어지고, 이를 계단 모양으로 배치하려고 합니다. 이때 k번째 행에는 반드시 정확히 k개의 동전이 놓여야 합니다. 따라서 동전의 총 개수 n이 주어졌을 때, 만들 수 있는 완전한 계단 행의 개수를 구하는 것이 목표입니다.예를 들어 입력이 5라면 출력은 2가 됩니다. 5개의 동전으로는 두 개의 완전한 계단 행을 만들 수 있지만, 세 번째 행을 완성하려면 3개가 더 필요한데 동전은 2개만 남기 때문입니다 −*****해결 접근 방식이 문제는 수학적 공식을 사용하면 반복문 없이 O(1) 시간 복잡도로 바로 해결할 수

크기가 n인 배열이 주어졌을 때, 모든 배열 요소를 동일하게 만들기 위해 필요한 최소 이동 횟수를 구하는 문제입니다. 여기서 한 번의 이동은 n - 1개의 요소를 1씩 증가시키는 연산을 의미합니다.예를 들어 입력 배열이 [3, 2, 3, 4]라면, 필요한 최소 이동 횟수는 4입니다.핵심 아이디어이 문제의 핵심은 관점을 바꾸는 것입니다. n - 1개의 요소를 1씩 올리는 것은, 상대적인 차원에서 보면 나머지 하나의 요소를 1씩 내리는 것과 수학적으로 동일합니다. 따라서 모든 요소가 같아질 때까지 각 요소를 최솟값까지 낮추는 데 필요한

= gi를 만족하면 쿠키 j를 아이 i에게 나눠 줄 수 있고, 그 아이는 만족하게 됩니다. 우리의 목표는 만족하는 아이의 수를 최대화하고, 그 최대값을 출력하는 것입니다.예를 들어 입력이 [1,2]와 [1,2,3]이라면 출력은 2가 됩니다. 두 명의 아이 탐욕 계수는 각각 1과 2이고, 세 개의 쿠키 크기는 모든 아이를 만족시키기에 충분하기 때문에 결과는 2입니다.해결 접근 방법이 문제는 대표적인 그리디(Greedy) 알고리즘 문제로, 다음 단계를 따르면 해결할 수 있습니다.아이들의 탐욕 계수 배열 g를 오름차순으로 정렬합니다.쿠키

특정한 직사각형 웹 페이지 면적이 주어졌다고 가정해 봅시다. 우리의 과제는 다음 세 가지 조건을 모두 만족하는 길이 L과 너비 W를 가진 직사각형 웹 페이지를 설계하는 것입니다.웹 페이지의 면적은 주어진 목표 면적과 정확히 같아야 합니다.너비 W는 길이 L보다 클 수 없습니다. 즉, 항상 L >= W를 만족해야 합니다.L과 W의 차이는 가능한 한 최소가 되어야 합니다.예를 들어 입력값이 4라면 출력은 [2,2]가 됩니다. 목표 면적이 4일 때 가능한 조합은 [1,4], [2,2], [4,1] 세 가지입니다. 두 번째 조건에 따

단어 목록이 주어졌을 때, 표준 QWERTY 키보드 배열에서 한 줄에 있는 알파벳만으로 입력할 수 있는 단어들을 찾는 문제입니다.예를 들어, 입력이 [hello, world, mom, dad, try, type, tom]이라면 출력은 [dad, try, type]이 됩니다. dad는 키보드 두 번째 줄(a, s, d, f...)의 문자로만, try와 type은 첫 번째 줄(q, w, e, r...)의 문자로만 구성되어 있기 때문입니다.문제 해결 접근 방법이 문제는 다음 단계를 통해 해결할 수 있습니다:결과를 저장할 output 배열

N명의 선수들의 점수 목록이 주어졌을 때, 각 선수의 상대 순위를 구하는 문제입니다. 이때 가장 높은 점수를 기록한 상위 세 명의 선수에게는 각각 Gold(금메달), Silver(은메달), Bronze(동메달)가 부여되며, 나머지 선수들은 자신의 등수를 문자열 형태로 받게 됩니다. 예를 들어 입력이 [2,5,3,1,0]이라면 출력은 [Bronze, Gold, Silver, 4, 5]가 됩니다. 즉, 5점이 금메달, 3점이 은메달, 2점이 동메달을 차지하고, 1점과 0점을 기록한 선수는 각각 4위, 5위가 됩니다. 문제 해결 접근

이번 글에서는 주어진 숫자가 완전수(Perfect Number)인지 판별하는 방법을 C++ 코드와 함께 살펴보겠습니다.완전수란?완전수란 자기 자신을 제외한 모든 양의 약수의 합이 자기 자신과 같아지는 수를 말합니다. 예를 들어 28의 경우 자기 자신을 제외한 약수는 1, 2, 4, 7, 14이며, 이들의 합은 다음과 같습니다.1 + 2 + 4 + 7 + 14 = 28따라서 입력값이 28이라면 출력 결과는 True가 됩니다. 문제에서 주어진 수 n의 범위는 10⁸ 이하입니다.해결 접근 방식완전수는 놀랍도록 드문 수입니다. 10⁸ 범위

두 개의 문자열이 주어졌을 때, 이 문자열들의 가장 긴 비공통 부분 수열(Longest Uncommon Subsequence)의 길이를 구하는 문제입니다. 여기서 비공통 부분 수열이란 한 문자열의 부분 수열 중에서 다른 문자열에는 나타나지 않는 것을 의미합니다. 즉, 한쪽 문자열에서만 찾을 수 있는 가장 긴 부분 수열의 길이를 구해야 하며, 만약 그러한 부분 수열이 존재하지 않는다면 -1을 반환해야 합니다.예를 들어 입력이 aabbac와 aabbcc라면, 출력은 6이 됩니다.문제 해결 접근 방법이 문제는 언뜻 복잡해 보이지만, 사실

배열과 정수 k가 주어졌을 때, 배열 안에 존재하는 고유한 k-diff 쌍의 개수를 구하는 문제입니다. 여기서 k-diff 쌍이란 (i, j) 형태를 가지며, i와 j가 모두 배열에 존재하고 두 값의 절댓값 차이가 k와 같은 경우를 의미합니다.예를 들어 입력이 [3, 1, 4, 1, 5]이고 k = 2라고 가정해 보겠습니다. 이 경우 출력은 2가 됩니다. 배열에는 (1, 3)과 (3, 5)라는 두 개의 2-diff 쌍이 존재하기 때문입니다.문제 해결 접근 방법이 문제는 해시 맵(map)과 집합(set)을 활용하면 효율적으로 해결할