01. 🔎 문제 탐색N: 수열의 크기 $(1 \leq N \leq 2,000)$(각 원소는 100,000보다 작거나 같은 자연수)M: 질문의 개수 $(1 \leq M \leq 1,000,000)$S, E: 팰린드롬인지 판단할 부분 수열의 범위01-1. 알고리즘 선택 & 시간 복잡도각 범위에 대하여 양 끝을 제외한 부분수열이 팰린드롬인지 판단하고 양 끝을 비교하는 것으로 팰린드롬인지 알 수 있음-> 따라서, 이전 결과를 다음 결과에 이용하므로 DP로 풀 수 있음예시로 S=1 E=5가 주어지고 S의 원소와 E의 원소가 같을 때 S+1, E-1의 부분수열이 팰린드롬이면 S, E의 부분수열 또한 팰린드롬이다.이중 for문을 통해 모든 경우의 수를 구할 수 있으므로, 시간 복잡도 $O(N^2)$에 지배02. ?..

01. 🔎 문제 탐색N: 보석의 개수, K: 가방의 개수$M_i, V_i$: 보석의 무게와 가치$C_i$: 가방에 담을 수 있는 보석의 최대 무게하나의 가방에는 하나의 보석만 담을 수 있음각 가방에 보석을 담았을 때, 가져갈 수 있는 최대 가치를 출력01-1. 알고리즘 선택 & 시간 복잡도각 가방에 주어진 무게에 대해, 넣을 수 있는 최대 가치의 보석을 넣으면 되는 그리디 문제정렬을 통해 보석과 가방을 오름차순으로 정렬 후, 탐색하여 담을 수 있는 보석을 알 수 있음담을 수 있는 보석을 판단 후, 우선순위큐를 이용하여 그 중 최대 가치를 골라낼 수 있음02. 📝 코드 설계하기보석과 가방의 정보를 입력보석과 가방을 오름차순으로 정렬가방을 순차적으로 탐색현재 선택된 가방에 들어갈 수 있는 보석을 탐색하여..

01. 🔎 문제 탐색n: 노드의 개수이진트리에 대하여 주어진 in-order와 post-order를 바탕으로 pre-order를 구하는 문제 01-1. 알고리즘 선택 & 시간 복잡도post-order를 통해 root 노드를 쉽게 구할 수 있음.root 노드를 기준으로 주어진 in-order를 왼쪽 서브트리, 오른쪽 서브트리로 나누어 계산나누어진 서브트리는 위와 같이 post-order에서 root노드를 구하고 다시 in-order에서 왼쪽/오른쪽 서브트리를 나눌 수 있음따라서, 이것은 재귀적으로 해결할 수 있으며, 서브트리를 나누어 해결하는 것에서 분할정복으로 볼 수 있음 02. 📝 코드 설계하기노드 개수 n과 트리에 대한 in-order와 post-order를 입력1~n까지의 범위에서 post-or..

01. 🔎 문제 탐색N: 행렬의 개수 $(1 \leq N \leq 500)$r, c: 행렬의 크기 $(1 \leq r, c \leq 500)$ 행렬의 곱을 수행했을 때, 순서에 따라 연산 횟수가 달라지게 되는데, 연산 횟수가 가장 낮아지는 순서로 계산하였을 때 나오는 최소 연산 횟수를 출력01-1. 알고리즘 선택 & 시간 복잡도이전 행렬 곱의 연산 횟수를 다음 연산 횟수에 이용해 사용할 수 있으므로, DP로 해결할 수 있음dp배열은 2차원 배열로 나타낼 수 있으며, i와 j는 i번째 행렬부터 j번째 행렬까지 행렬 곱을 진행했을때, 최소 연산 횟수를 담음i부터 j까지 범위의 행렬 곱 최소 연산 횟수 dp[i][j]는 아래와 같은 점화식으로 나타낼 수 있음$dp[i][j] = min_{k=i}^{j-1}..

01. 🔎 문제 탐색매 게임시작 시 건물을 짓는 순서가 주어짐(각 게임마다 건물을 짓는 순서가 다를 수 있음)모든 건물은 각각 건설을 시작(다음 건물은 선행 건물이 모두 완성되어야 건설 시작 가능)N: 건물의 개수K: 건설 순서 규칙의 개수$D_1, D_2, ..., D_N$: 1~N번 건물의 건설에 걸리는 시간X, Y: X건물이 선행되어야 Y건물을 건설할 수 있음W: 목표 건물목표 W번 건물이 건설완료 하는데 드는 최소 시간을 출력01-1. 알고리즘 선택 & 시간 복잡도시작 건물과 건물을 짓는 순서가 게임마다 바뀌므로, 위상 정렬을 이용하여 주어지는 건설 순서로 탐색을 진행이전 건물 건설에 걸린 최대 시간이 다음 건물 건설 시작 시작에 영향을 받으므로, DP를 이용하여 이를 구현02. 📝 코드 설계..

01. 🔎 문제 탐색NxN 크기의 마을의 우체국에서 출발해 모든 집에 방문해야 함62500각 칸마다 고도가 정해져있고, 지나온 경로의 최대 고도 - 최소 고도 = 피로도가 됨이 때, 모든 집을 방문할 수 있는 최소 피로도를 구하는 문제INPUTN: 마을 크기(NxN) $(2 \leq N \leq 50)$(N개의 줄에 마을의 상태{'P': 우체국(시작점), 'K': 집, '.': 목초지}를 입력)(NxN 크기에 대한 각 칸의 고도를 입력) (고도 = 1,000,000이 최대인 자연수)01-1. 알고리즘 선택 & 시간 복잡도투 포인터로 배달원이 갈 수 있는 최소 고도와 최대 고도를 제한 $\rightarrow$ 시간 복잡도 $O(N)$BFS를 이용해 정해진 고도 범위 내에서 배달원이 모든 집을 방문할 수 ..

01. 🔎 문제 탐색1개 회사에 대한 미래 N일간 주식 변동을 가지고 있음N일간 주식 가격 N개가 주어짐주어진 주가를 바탕으로 주식을 K번 매수하기로 함(단, 하루에 1번 매수 가능)또한, 직전 날에 매수했던 주가보다 높은 주가에 구매해야 함(매수하는 주가가 점점 상승한다는 말)N: N일에 대한 주가 N개K: 희망 거래 횟수주어진 N개의 주가에대해 하루에 한 번 구매한다고 했을 때, 점점 상승하도록 K번 구매할 수 있는 지 여부를 출력01-1. 알고리즘 선택 & 시간 복잡도LIS(최장 증가 부분 수열) 알고리즘으로 점점 증가하도록 수열을 만들었을 때, 그 길이가 K 이상이면 가능한 경우의 수이다.주어진 주가 N에 대해서 1번 탐색하며, 수열의 자리를 이분탐색으로 알 수 있으므로, 시간 복잡도는 $O(N..

01. 🔎 문제 탐색N: NxN크기의 평지 $(4 \leq N \leq 50)$(N개의 줄에는 각 칸의 상태{0: 빈 칸, 1: 나무, B: 통나무, E: 목적지}가 주어짐)통나무(B)와 목적지(E)는 항상 연속적으로 3개가 놓임 (BBB가 1개, EEE가 1개)통나무와 목적지는 대각선으로 놓일 수 없으며, 항상 x축이나 y축과 평행함통나무는 상, 하, 좌, 우, 90도 회전 과 같이 5가지 행동을 할 수 있음(행동 반경에 나무(1)가 존재할 경우, 이동/회전 할 수 없음)통나무를 5가지 행동으로 목적지까지 이동시키되, 최소 동작 횟수를 출력01-1. 알고리즘 선택 & 시간 복잡도통나무를 목적지까지 이동시키기 위한 최소 동작을 묻는 문제로, BFS를 활용할 수 있다.(단, 연속된 B(통나무)는 함께 움..