문제 개요이 문제에서는 N×N 크기의 행렬 mat[]가 주어지며, 우리의 목표는 모든 원소가 동일한 가장 큰 정사각형 부분 행렬을 찾는 것입니다.즉, 주어진 행렬 안에서 모든 원소의 값이 서로 같은 부분 행렬 중 최대 크기를 구해야 합니다.예제로 문제 이해하기입력: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}출력: 2설명: a11, a12, a21, a22로 구성된 2×2 부분 행렬의 모든 원소가 동일하므로, 정답은 2가 됩니다.해결 접근 방법1. 브루트 포스(완전 탐색)가장 단순한 방법은 행렬의

문제 개요이 문제에서는 인접 리스트(adjacency list)로 표현된 방향 그래프가 주어집니다. 우리의 과제는 BFS(너비 우선 탐색)를 사용하여 하나의 시작 정점에서 그래프의 나머지 모든 정점까지의 경로를 찾는 프로그램을 작성하는 것입니다.BFS(Breadth First Search, 너비 우선 탐색)는 그래프를 너비 방향으로 순회하는 알고리즘입니다. 탐색 도중 막다른 길(dead end)에 도달하면, 큐(queue)를 사용하여 다음에 탐색을 시작할 정점을 기억해 둡니다.예제로 문제 이해하기입력 −아래와 같은 그래프

이 문제에서는 정렬된 배열 arr[]와 정수 x가 주어지며, 배열 안에서 x의 Floor(바닥) 값을 찾는 프로그램을 작성해야 합니다.여기서 정렬된 배열에서 x의 Floor란, 배열 arr[]에 존재하는 원소 중 x보다 작거나 같은 값 중 가장 큰 원소를 의미합니다.문제 이해를 위한 예시입력: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10출력: 9설명: 위 배열에서 10보다 작거나 같은 수 중 가장 큰 값은 9입니다. 따라서 결과는 9가 됩니다.해결 방법 1: 선형 탐색(Linear Search)가장

이 문제에서는 정수 요소로 구성된 배열 arr[]가 주어지며, 우리의 과제는 같은 배열 안에서 각 요소의 Floor(바닥) 값을 찾는 프로그램을 작성하는 것입니다. 특정 요소의 floor가 존재하면 그 값을 출력하고, 존재하지 않으면 -1을 출력합니다.배열에서 요소의 Floor란, 배열 내에서 해당 요소보다 작거나 같은 값 중 가장 가까운(즉, 가장 큰) 요소를 의미합니다.문제 이해를 위한 예시입력과 출력의 관계를 살펴보면 다음과 같습니다.입력: arr[] = {3, 1, 5, 7, 8, 2}출력: 2 -1 3 5 7 1예를 들어

문제 개요N개의 숫자로 이루어진 배열 arr[]과 정수 값 X가 주어졌을 때, 이진 리프팅(Binary Lifting) 기법을 활용하여 배열의 접두사 합에서 X보다 크거나 같은 첫 번째 요소를 찾는 프로그램을 작성하는 것이 이번 문제의 목표입니다.접두사 합(Prefix Sum)이란 원본 배열에서 각 인덱스까지의 모든 요소를 누적해서 더한 값을 요소로 갖는 배열을 의미합니다.예시array[] = {5, 2, 9, 4, 1}prefixSumArray[] = {5, 7, 16, 20, 21}문제 이해하기예제를 통해 문제를 자세히 살펴보겠

이 문제에서는 N개의 정수로 구성된 배열 arr[]와 크기가 k인 윈도우(창)가 주어집니다. 우리의 과제는 크기 k인 모든 윈도우에서 첫 번째 음의 정수를 찾는 프로그램을 작성하는 것입니다. 해당 윈도우에 음수가 존재하면 그 첫 번째 음수를 출력하고, 존재하지 않으면 음수가 없음을 의미하는 0을 출력합니다.문제 이해를 위한 예시입력: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2출력: -2, -1, -1, 0, -6설명 −윈도우 크기 k = 2일 때,{-2, 2} → 첫 번째 음수는 -2{2, -1} → 첫 번째

문제 개요이 문제에서는 크기가 N인 연결 리스트(LL)가 주어지며, 우리의 목표는 연결 리스트에서 첫 번째로 중복되지 않는(non-repeating) 원소를 찾는 프로그램을 작성하는 것입니다.연결 리스트(linked list)는 노드들이 링크(포인터)를 통해 차례로 연결된 선형 자료구조입니다. 각 노드는 실제 데이터와 다음 노드를 가리키는 참조 값으로 구성됩니다.예제로 문제 이해하기입력: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5출력: 1설명 −이 연결 리스트에서

이 문제에서는 크기가 N인 문자열 배열 str[]이 주어집니다. 우리의 과제는 주어진 배열에서 그 역순(뒤집은 문자열)이 같은 배열 안에도 존재하는 첫 번째 문자열을 찾는 프로그램을 작성하는 것입니다.예시를 통해 문제를 이해해 보겠습니다.입력: str[] = [python, program, C#, language, #C]출력: C#위 예시에서 C#을 뒤집으면 #C가 되고, 이 값이 동일한 배열에 존재하므로 정답은 C#입니다.해결 방법 1: 완전 탐색(Brute Force)가장 직관적인 방법은 문자열 배열의 각 요소를 순회하면서, 해

이 문제에서는 크기가 N인 문자열 str[]과 정수 X가 주어집니다. 우리의 과제는 문자열에서 처음 등장하는 X개의 모음을 출력하는 프로그램을 만드는 것입니다.문자열에서 앞에서부터 X개의 모음을 순서대로 출력하며, 만약 문자열에 포함된 모음의 개수가 X보다 적다면 -1을 출력해야 합니다.문제 이해를 위한 예시입력: str = learn C programming language, X = 5출력: e, a, o, a, i모음은 a, e, i, o, u 입니다.해결 접근 방법이 문제의 간단한 해결 방법은 문자열을 한 글자씩 순회(trav

이 문제에서는 정수 값 N이 주어지며, 우리의 과제는 N번째 짝수 피보나치 수(Even Fibonacci Number)를 찾는 것입니다.피보나치 수열은 이전 두 수를 더하여 다음 수를 생성하는 수열입니다. 피보나치 수열은 두 개의 초기값 F0과 F1에서 시작하며, 초기값은 각각 0, 1 또는 1, 1로 설정할 수 있습니다.예시를 통해 문제를 이해해 보겠습니다.입력 : N = 4출력 : 144해결 접근 방식이 문제의 핵심 아이디어는 피보나치 수열에서 매 세 번째 수가 짝수라는 사실을 활용하는 것입니다. 그리고 짝수 피보나치 수들 역시

이 문제에서는 2차원 이진 행렬이 주어지며, DFS(깊이 우선 탐색)를 사용해 섬의 개수를 찾아야 합니다. 섬(Island)이란 행렬 안에서 가로, 세로, 대각선 방향으로 서로 연결된 하나 이상의 1들이 모여 이루어진 영역을 말합니다. 문제 이해하기 예제를 통해 문제를 살펴보겠습니다. 입력 : bin[][] = {{ 1 0 0 0}     {0 1 0 1}     {0 0 0 0}     {0 0 1 0}} 출력 : 3 설명

이 문제에서는 2차원 이진 행렬(binary matrix)이 주어지며, 우리의 목표는 Disjoint Set(서로소 집합) 자료구조를 이용해 섬의 개수를 찾는 것입니다. 섬(Island)이란 행렬 안에서 서로 연결되어 있는 하나 이상의 1들로 이루어진 영역을 의미합니다. 예시를 통해 문제를 자세히 살펴보겠습니다. 입력 bin[][] = {{ 1 0 0 0} {0 1 0 1} {0 0 0 0} {0 0 1 0}} 출력 3 설명 섬의 위치 : bin00 - bin11 bin13 bin32

이 문제에서는 세 개의 정수 A, B, C가 주어지며, 우리의 목표는 주어진 방정식을 만족하는 해의 개수를 구하는 것입니다.방정식X = B*Sm(X)^A + C여기서 Sm(X)는 X의 각 자릿수의 합을 의미합니다.X는 1부터 109 사이의 어떤 수든 될 수 있으며, 이 범위 내에서 위 방정식을 만족하는 모든 X의 개수를 세어야 합니다.예시를 통해 문제를 이해해 봅시다,입력A = 3, B = 6, C = 4출력3해결 접근 방식이 문제를 해결하는 핵심 열쇠는 바로 자릿수의 합입니다. X의 최댓값은 999,999,999이므로, 자릿수의

문제 개요 계단을 만드는 데 사용할 수 있는 벽돌의 개수 N이 주어졌을 때, 이 벽돌로 만들 수 있는 계단 단계(step)의 최대 개수를 구하는 것이 이 문제의 목표입니다. 계단을 쌓는 규칙은 다음과 같습니다. 첫 번째 단계는 벽돌 2개로 만듭니다. 그 위의 각 단계는 바로 아래 단계보다 정확히 1개 더 많은 벽돌을 사용합니다. 즉, 2개, 3개, 4개… 순으로 필요합니다. 남은 벽돌로 다음 단계를 만들 수 없게 되면, 그 시점까지 완성한 단계 수가 정답이 됩니다. 예시로 이해하기 입력 N = 40 출력 7 풀이 과정 단계 1

이 문제에서는 0과 1로만 구성된 이진 배열 bin[]이 주어지며, 우리의 목표는 배열에 포함된 0의 개수를 찾는 것입니다.배열은 정렬되어 있어서 모든 0이 1 뒤에 함께 배치되어 있습니다.예시를 통해 문제를 이해해 보겠습니다.입력arr[] = {1, 1, 1, 0, 0, 0, 0}출력4문제 해결 접근법이 문제의 핵심 아이디어는 배열이 정렬되어 있다는 특성을 활용하는 것입니다. 배열에서 처음으로 0이 등장하는 위치만 찾으면, 그 이후의 모든 값이 0이므로 배열의 전체 크기 − 첫 번째 0의 인덱스로 0의 개수를 바로 구할 수 있습니

이 문제에서는 소문자로만 구성된 입력 문자열이 주어지며, 우리의 과제는 문자열에서 가장 많이 등장하는 문자를 찾는 것입니다.만약 등장 빈도가 같은 문자가 여러 개 있다면, 사전순으로 더 앞서는(lexicographically smaller) 문자를 출력해야 합니다.문제 이해를 위한 예시입력string = programming출력g위 예시에서 g와 r은 각각 2번씩 등장하지만, 사전순으로 g가 더 앞서므로 결과는 g가 됩니다.해결 접근 방법이 문제를 해결하기 위해 해싱(hash) 기법을 활용할 수 있습니다. 해싱이란 문자열을 한 번

문제 개요 이 문제에서는 크기가 n인 배열 arr[]가 주어지며, 주어진 범위에서 누락된 숫자 하나를 찾는 것이 목표입니다. 배열은 최솟값부터 (최솟값 + n)까지의 모든 값으로 구성되어 있으며, 이 범위 중 단 하나의 요소만 배열에 빠져 있습니다. 우리가 해야 할 일은 바로 이 누락된 값을 찾아내는 것입니다. 예제를 통해 문제를 살펴보겠습니다. 입력 arr[] = {4, 8, 5, 7} 출력 6 위 예제에서 배열의 최솟값은 4이므로, 범위는 4부터 8까지가 됩니다. 이 범위의 값 {4, 5, 6, 7, 8} 중 배열에 존재하지 않

문제 설명이번 문제에서는 크기가 n인 배열 arr[]가 주어지며, 우리의 목표는 배열에서 유일하게 다른 요소를 찾는 것입니다.배열에는 두 가지 종류의 값만 존재하고, 단 하나의 요소를 제외한 나머지는 모두 동일한 값을 가집니다.예시로 문제 이해하기입력:arr[] = {1, 1, 1, 2, 1, 1, 1, 1}출력:2위 예시에서 2만 다른 값을 가지므로 정답은 2입니다.문제 해결 접근 방법방법 1: 완전 탐색 (O(N²))가장 직관적인 방법은 배열을 순회하면서 각 요소를 다른 모든 요소와 비교하는 것입니다. 다른 값을 가진 요소를 발

문제 개요이 문제에서는 크기가 n인 배열 arr[]와 두 정수 a, b가 주어집니다. 우리의 목표는 정확히 b번 등장하는 유일한 원소를 찾는 것입니다.배열의 모든 값은 a번씩 나타나지만, 단 하나의 값만 b번 나타납니다. 바로 그 값을 찾아야 합니다.예제를 통해 문제를 이해해 보겠습니다.입력:arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1, 1, 1}, a = 4, b = 3출력:5풀이 접근 방법가장 단순한 방법은 각 원소의 등장 횟수를 세어 자료구조에 저장한 뒤, 빈도가 b인 값을 찾는 것입니다. 하지만 이 방법의

문제 개요이 문제에서는 크기가 N인 배열 arr[]가 주어집니다. 배열에는 1부터 N까지의 값이 들어 있지만, 그중 단 하나의 값이 누락되어 있습니다. 우리의 목표는 정렬된 배열에서 누락된 그 유일한 숫자를 찾아내는 것입니다.예시를 통해 문제를 이해해 보겠습니다.입력arr[] = {1, 2, 3, 5, 6, 7}출력4접근 방법 1: 선형 탐색가장 직관적인 해결 방법은 정렬된 배열을 처음부터 끝까지 선형으로 순회하는 것입니다. 배열이 오름차순으로 정렬되어 있고 1부터 N까지의 값 중 하나만 비어 있으므로, 인덱스와 값 사이에 arr[