algorithm

계수 정렬은 각 숫자의 등장 횟수를 세어 정렬하는 알고리즘이다.비교 없이 정렬을 수행한다.O(n + k) 시간 복잡도의 알고리즘으로, 범위가 제한된 정수 정렬에 매우 효율적이다. 정수 배열 A를 입력받으면, 최대값과 같은 길이의 배열 B와 A와 동일한 길이의 배열 C를

기수 정렬(Radix Sort)은 비교 기반 정렬이 아닌(non-comparative sorting algorithm) 자릿수(digit)를 기준으로 데이터를 정렬하는 알고리즘입니다. 주로 정수(integer)나 문자열(string) 정렬에 사용됩니다.기수정렬의 시간복

이 부분은 병합 과정(merge step)에서 오른쪽 배열의 요소가 먼저 모두 복사된 경우에만 실행된다.병합(merge) 과정에서 왼쪽 배열(left ~ mid)과 오른쪽 배열(mid+1 ~ high)을 비교하면서 정렬하여 arr에 복사합니다.하지만 왼쪽과 오른쪽 배열

보석의 무게와 가격이 주어졌을 때, 제한된 무게 안에서 최대 가격이 되도록 보석을 담는 문제.가방에 담을 수 있는 보석의 무게는 최대 20kg이며, 각 보석은 한 개씩만 존재한다.잔여 무게가 현재 보석의 무게보다 적어 보석을 담을 수 없음을 의미한다.즉, 현재 보석을

두 개의 문자열 A, B가 주어졌을 때, A를 B로 변환하는 데 필요한 최소 연산 횟수(편집 거리)를 구하는 문제이다.사용할 수 있는 연산은 세 가지이다.삽입 (Insertion) → 원하는 위치에 문자 추가 삭제 (Deletion) → 특정 위치의 문자 제거 수정

1부터 N까지의 숫자로 이루어진 3자리 다이얼이 있는 자물쇠가 있음자물쇠는 원형 구조이며, 1과 N이 인접한 형태로 연결됨두 가지의 숫자 조합이 주어졌을 때, 어느 한 조합이라도 모든 숫자가 거리 2 이내이면 자물쇠가 열림자물쇠가 열리는 서로 다른 조합의 개수를 구하는

A와 B는 서로 숫자 맞추는 게임을 한다. A는 1부터 9까지의 서로 다른 세 개의 숫자로 구성된 세 자리 수를 생각한다. B는 1부터 9까지의 서로 다른 세 개의 숫자로 구성된 세 자리 수를 A에게 묻는다. B가 말한 세 자리 수의 숫자 중 하나가 A가 생각한 세 자

N명의 학생에게 B만큼의 예산으로 선물을 구매.학생마다 가격 P(i)와 배송비 S(i)가 있음.선생님은 선물 하나를 반값으로 살 수 있는 쿠폰을 가짐.최대한 많은 학생에게 선물을 주는 것이 목표.(P + S) 값이 작은 순서로 정렬 → 비용이 적은 선물을 먼저 구매.(

두 개의 숫자 X, Y가 주어지면 X 이상 Y 이하에 있는 '흥미로운 숫자'의 개수를 구하는 문제입니다.'흥미로운 숫자'란 모든 자릿수에 있는 숫자가 같지만, 정확히 한 자리만 다른 숫자를 의미합니다.예를 들어, 33335와 11118은 '흥미로운 숫자'지만, 3333

각 숫자에 대해 문자열 길이의 절반만 비교 (n/2).O(n/2) ≈ O(n)의 시간 복잡도를 가짐.전체 반복 횟수: (y - x) \* n/2.StringBuilder.reverse()는 O(n) 연산.equals() 비교도 O(n)이므로 최종적으로 O(n) + O(

서로 다른 세 정수 A, B, C가 주어질 때, A와 B를 0번 이상 더해서 만들 수 있는 C 이하의 수 중 최댓값을 구하는 문제.A와 B를 반복문으로 조합하여 C 이하의 최댓값을 찾음.두 중첩 반복문을 사용하여 가능한 모든 경우를 탐색.A를 i번 사용한 후, 남은 값

주어진 N개의 좌표를 x축 또는 y축에 평행한 3개의 직선으로 모두 지날 수 있는지 판별하는 문제.0부터 10까지 x 또는 y 값을 기준으로 모든 조합을 탐색.4중 for문을 사용하여 모든 가능한 조합을 검사.점이 3개의 직선 중 하나에 포함되면 continue.시간

N개의 돌들이 1번부터 N번까지 순서대로 놓여 있으며, 각 돌에는 하나의 숫자가 적혀 있습니다. 1번에서 시작하여 K의 거리로 점프하면서 N번 돌에 도달할 때, 지나온 돌들에 적힌 숫자들의 최댓값 중 최소를 구하는 문제입니다.처음과 마지막은 반드시 거쳐가야 한다최소값을

N개의 수가 주어질 때, 이 수열을 정확히 M개의 구간으로 나누려고 한다.이때, 각 구간의 합 중 최댓값이 최소가 되도록 구간을 나누는 프로그램을 작성하라.첫째 줄에 N과 M이 주어지고, 둘째 줄에 N개의 수가 주어진다.2 ≤ M ≤ N ≤ 100각 수는 1 이상 10

N개의 수가 주어지고, 그 중 최대 L개의 서로 다른 원소 값을 1씩 증가시켜 H 점수를 최대화해야 한다.H 점수란 특정 수 H 이상인 원소가 H개 이상 존재하는 경우를 만족하는 최대의 H를 의미한다.예를 들어, 수열 2, 3, 5에서 H 점수는 2이다.모든 값을 복사

케이스를 잘 구분할 것겹치는 지 확인하는 것보다, 겹치지 않는지 여부를 확인하는 것이 간단할 수 있다A, B는 1차원 수직선상에서 구역청소를 진행한다.A는 x = a 구역부터 x = b 구역까지 청소를 진행하고, B는 x = c 구역부터 x = d 구역까지 청소를 진행

1차원 상에서 여러 선분이 전부 겹치는지 판단하는 방법x1, x2가 있고 x1 < x2라고 할 때, min(x2) >= max(x1)이면 모든 선분이 겹친다고 할 수 있다.1차원 직선 상에 N개의 선분이 놓여있다.그 중 한 개를 제거했을 때, N-1 개의 선분이

N명의 사람들이 채팅방에서 메시지를 주고받는다.메시지를 보낼 때마다 그 시점에서 메시지를 읽지 않은 사람의 수 u\[i]가 주어진다.p번째 메시지를 기준으로 누가 이 메시지를 읽지 않았는지 판단해야 한다.N: 사람 수 (1 ≤ N ≤ 26, A~Z로 이름 지정)M: 메

한 지점에서 다른 지점까지 거리 x만큼 이동해야 한다.매초 이동 속도를 1만큼 증가하거나 감소시킬 수 있다.초기 속도는 0이다.도착 지점에서는 속도가 반드시 1이어야 한다.가장 빠르게 도착할 수 있는 시간을 구해야 한다.최단 시간으로 도달하기 위해서는 중간에 속도를 계

세 사람이 일직선 위에 서있다.세 사람이 서있는 위치가 주어지면 양 끝에 있는 사람 중 한 사람을 택해 남은 두 사람 사이로 이동시켜 결국 세 사람의 위치가 연속될 수 있도록 한다.while 루프를 이용해 조건이 만족될 때까지 반복각 단계마다 작은 쪽 또는 큰 쪽을 한

사람들이 살고 있는 위치가 0과 1로 주어질 때,모든 사람들이 와이파이를 사용할 수 있도록거리 m 이내를 커버하는 와이파이를 최소 몇 개 설치해야 하는지 구하는 문제.와이파이는 사람이 없는 위치에도 설치 가능하며,정수 위치에만 설치할 수 있고,설치한 위치로부터 거리 m

주어진 수들을 사용해 각 묶음의 합이 다음 규칙을 만족하도록 여러 개의 묶음을 만들고자 한다:첫 번째 묶음의 합은 짝수두 번째 묶음의 합은 홀수세 번째 묶음의 합은 짝수네 번째 묶음의 합은 홀수...즉, 짝수 → 홀수 → 짝수 → 홀수 ... 형태로 번갈아가며 묶음을

1차원 좌표 위에 여러 개의 선분이 주어진다. 이 중 하나를 제거했을 때, 나머지 선분들을 전부 포함할 수 있는 최소 길이의 선분을 구하는 문제이다.선분은 x좌표의 시작점과 끝점 (x1, x2)로 주어지며, 조건을 만족하는 가장 짧은 선분 길이를 출력해야 한다.각 선분

N x N 격자 미로에서 오른쪽 벽을 짚고 이동하여 탈출하는 시뮬레이션 문제.시작 위치와 초기 방향(우측)이 주어지며, 벽의 상태에 따라 방향을 바꾸거나 이동함.탈출 조건: 격자 밖으로 나가면 탈출 성공.실패 조건: 같은 위치와 방향을 반복하면 탈출 불가능.벽을 짚고

사다리타기(Amida Lotto)는 인접한 세로선 사이에 가로선을 추가하여 사람들의 위치를 뒤섞는 게임이다.주어진 가로선 집합 중 일부만 선택하여도 전체 가로선을 모두 사용했을 때와 동일한 결과가 나오는 최소 조합을 찾는 문제를 다룬다.초기 구현은 실제 이동 경로를 삼

변화하는 값만을 추적한다면 재귀의 파라미터를 사용하여 구현 가능하다. 문제 개요 크기 N × N 격자에 물건이 하나씩 놓여 있으며, 각 물건의 무게는 weighti 두 도둑은 한 행을 각각 선택해 연속한 M칸(구간)에서 물건을 훔친다. 같은 행을 고를 수 있지만, 두 구간이 겹쳐서는 안 됨 각 도둑은 자신의 구간 안에서 몇 개를 고를지 자유롭게 선택 ...

깊이 depth에 대해, 해당 값을 포함하거나 포함하지 않는 두 가지 분기를 수행모든 부분집합을 탐색하며 cnt == m인 경우만 출력시간 복잡도: O(2ⁿ)공간 복잡도: O(n)불필요한 분기 많음조합 조건을 만족하는 원소만 탐색depth는 현재까지 선택한 원소 수,

격자의 좌측 상단에서 우측 하단으로 이동이 가능한지 판별하는 문제.DFS를 이용하여 해결하려 했으나 시간초과가 발생하였다.방문여부를 나타내는 visited\[i]를 초기화하지 않고, 도달 여부만 확인하여 해결.현재 코드는 "좌측 상단에서 우측 하단으로 이동 가능한지"

2 × N 크기의 사각형을 1×2, 2×1, 1×1 타일로 채우는 방법의 수를 구하는 문제다. 단, 경우의 수는 1,000,000,007로 나눈 나머지를 출력한다.예를 들어 N=2일 때는 아래 7가지 방법으로 채울 수 있다:1×2, 1×22×1, 2×11×1 네 개2×

자연수 1부터 N까지의 노드를 사용하여 만들 수 있는 서로 다른 이진 탐색 트리(BST) 의 개수를 구하는 문제이다.BST는 왼쪽 서브트리 < 루트 < 오른쪽 서브트리 조건을 만족하는 이진 트리이다.노드 값 자체가 아닌 노드 개수에 따라 구조의 경우의 수가