문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/68646 인접한 풍선 2개를 선택해서 둘 중 하나를 터트리는 행동을 풍선이 최종적으로 1개 남을 때까지 반복한다. 두 풍선 중 번호가 더 작은 것을 터트리는 행동은 최대 1번밖에 할 수 없다. 즉, 횟수 제한이 없는 것은 두 풍선 중 번호가 더 큰 풍선을 터트리는 행동이다. 그리고 최후까지 남을 수 있는 풍선의 개수를 구한다. 문제 접근 단계 제한 사항에서 얻을 수 있는 정보 제한 사항부터 살펴보자. 일단 배열의 길이, 그러니까 풍선의 개수는 최대 1,000,000개까지 가능하다. 이게 뜻하는 바는, 시간복잡도가 O(N^2)까지 가면 10^12이므로 10초가 훌쩍 넘어버린다. 그러니까..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/92343? 이진트리가 있는데, 각 노드에는 양(0) 또는 늑대(1)가 있다. 무조건 루트노드에서 출발하여 양을 획득해야 한다. 루트 노드는 항상 양이다. 획득하는 과정에서 양의 수가 항상 늑대 수보다 많음을 유지해야 한다. 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아올 때 모을 수 있는 최대 양의 수를 구하는 문제 문제 접근 단계 제한 사항 파악 제한 사항부터 보면 노드(info)는 최대 17개까지이다. 이에 따라, 항상 이진트리를 유지하기 때문에 간선(edges) 또한 100개가 넘어가지 않는다 즉, 완전 탐색이 가능할 만큼 탐색할 범위가 작음을 알 수가 있다. 움직이는 경..

하노이의 탑(Tower of Hanoi) 문제란? 유례나 역사 같은 것은 다 생략하고, 문제의 조건 같은 본론부터 바로 말하겠다. 3개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기에 원판들이 존재한다. 맨 처음 시작할 때, 원판의 크기가 큰 것부터 1번 기둥에 모두 쌓는다. 맨 왼쪽 기둥부터 순서대로 1번, 2번, 3번 기둥이라고 한다. 문제에서 요구하는 것은 아래의 조건을 만족하면서, 1번 기둥에 쌓여있는 모든 원판들을 3번 기둥으로 옮기는 것이다. 조건 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. N개의 원판이 최소 경로로 이동할 때의 경로를 출력하라는 것이 문제에서 요구하는 것이다. 이 문제를 왜 알아야 할까? 중요한 것은 학습의 목적이다. 프로..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/12904? 팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 뜻한다. 입력으로 문자열 s가 주어질 때, s의 부분 문자열 중에 가장 긴 팰린드롬의 길이를 구하는 문제 문제 접근 단계 제한사항부터 살펴보자. 문자열의 길이 s는 2,500 이하의 자연수이고, 알파벳 소문자로만 구성되어 있다. 팰린드롬이라는 좌우대칭 규칙성을 판단할 때는 보통 스택을 사용한다. 이 문제에서 사용하려고 했는데, 각 자리마다 스택을 사용하여 넣었다 뺐다 하는 것은 굉장히 비효율적이다. 그리고 예전에 백준 포스팅에서 이런 유사한 문제를 다룬 적이 있다. https://howudong.tistory.com/319 [C+..

문제 이해 단계 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS는 두 수열이 주어졌을 때, 두 수열의 공통이 되는 부분 수열 중 가장 긴 것을 찾는 문제이다. 가장 긴 수열의 길이를 출력하고, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지일 경우엔 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄은 출력하지 않는다. 문제 접근 단계 LCS 길이 구하기 [C++] 백준 9251 ..

문제 이해 단계 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net N개의 앱이 존재한다. N개의 앱에는 2가지 정보가 들어있는데, (사용 중인 메모리의 바이트 수, 비활성화했을 때의 비용) 2가지이다. M 바이트를 확보해야 하기 때문에, N개의 앱 중 몇 가지를 골라서 비활성화해야 한다. 이때 비활성화 했을 때의 비용을 최소화하여 M 바이트를 확보해야 한다. 최소 비용일 때를 출력하는 문제 문제 접근 단계 제한 사항 분석 앱의 개수(N)는 최대 100개..

문제 이해 단계 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net NxM 크기의 맵이 존재하고, 빨간 구슬과 파란 구슬이 존재한다. 맵의 테두리는 모두 벽으로 막혀있고, 하나의 구멍이 존재한다. 목표는 파란 구슬은 구멍은 남겨둔 채, 빨간 구슬을 구멍을 통해 빼내는 것. 할 수 있는 동작은 상하좌우로 기울이는 것이다. 기울인다는 것은 해당 쪽에 벽에 닿을 때까지 쭉 흐른다는 것. 예를 들어, 오른..

구현해 보는 이유 C++ 헤더 에 lower_bound와 upper_bound 함수가 있다. 근데 있는 거 두고 굳이 왜 직접 구현해 보는 걸까? 이유는 총 2가지이다. 1. 학습적인 목적(이진탐색 구현) 2. 이진 탐색 변형 이 목적으로 한번 구현해 본다. lower_bound와 upper_bound 메서드 lower_bound lower_bound는 찾고자 하는 값보다 크거나 같은 값이 처음 나타난 곳의 인덱스를 반환한다. 예를 들어서, {2,4,6,7,9}에서 lower_bound를 사용하여 2를 찾는다면 배열에서 2의 인덱스인 0을 반환한다. 또한 5를 찾는다면, 처음으로 5보다 큰 6의 인덱스인 2를 반환한다. upper_bound upper_bound는 찾고자 하는 값보다 큰 값이 처음 나타난..