문제 이해 단계 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개가 넘어가지 않는다 즉, 완전 탐색이 가능할 만큼 탐색할 범위가 작음을 알 수가 있다. 움직이는 경..

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

문제 이해 단계 입력으로 사원의 정보가 주어지는데 각각 (근무 태도 점수, 동료 평가 점수)로 이루어져 있다. 목표는 사원의 등수를 정하는 것이다. 이 중에서 다른 사원과 비교했을 때, 한 번이라도 다른 사원보다 두 점수가 둘 다 낮은 사원은 등수에서 제외한다. 그리고 등수는 점수가 높은 순으로 선정한다. 동점자가 존재하면 그 사원은 같은 등수이고, 그 뒤에 등수 하나가 없어진 등수가 다음 사원에게 간다. 해당 조건에서 가장 처음에 들어온 입력(인덱스 0) 사원의 등수를 구하는 문제 제외됐다면 -1을 출력 문제 접근 단계 문제의 제한 사항부터 살펴보자. scores의 길이, 그러니까 사원의 최대 수와 점수의 최댓값은 100,000이다. 여기서 더하는 행위는 근무 태도 + 동료 평가 밖에 없기 때문에 In..

문제 이해 단계 연속 부분 수열과 같은 길이의 펄스 수열이 존재한다. 펄스 수열 : {1,-1,1,-1...} or {-1,1,-1,1,-1..} 이런 식으로 1과 -1이 번갈아가며 나오는 수열 연속 부분 수열 : 한 수열에서 끊기지 않고 연속해서 나열되어 있는 수열 ex ) {4,5,-3,2,0,-2,-1,-2}에서 {4,5-3}, {0,-2}, {-2,-1,-2} , {-1}은 연속 부분 수열임 연속 부분 수열과 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만든다고 가정한다. 이때 나올 수 있는 부분 집합 중, 원소의 합이 가장 큰 부분 집합을 구해서 그때의 합을 구하는 문제 문제 접근 단계 이 문제를 복잡하게 하는 부분은 연속 부분 수열의 시작점을 모른다는 것과 펄스 수열이 -1로 시작할..

문제 이해 단계 집이 원형으로 배치되어 있고, 한 집을 선택하면 양 옆에 있는 집을 선택할 수 없게 된다. 이러한 조건일 때 얻을 수 있는 가장 많은 숫자 합을 고르는 문제 문제는 엄청나게 간단하다. 문제 접근 단계 일단 배치를 신경 쓰지 말고, 그냥 일반적인 문제처럼 일렬로 집이 있다고 생각해 보자. 그러니까 해당 문제에서 원으로 배치된 것을 어떤 집을 기준으로 일렬로 배치한 것이다. 입력을 주어진 그대로 일렬로 배치해 봤다. 구해야 하는 것은 이 중 최적의 집들을 선택해서 최댓값을 구하는 것이다. 3번 집부터 시작한다고 생각하자. 해당 문제에서 집은 최소 3개라고 했으니 3개부터 살펴본다. 그러니까 현재는 왼쪽에 있는 [2,3,4] 집 밖에 없다고 생각하는 것이다. 집 하나를 고르면 양 옆은 고를 수..

문제 이해 단계 입력으로 2차원 맵과, 지나갈 수 없는 장애물(물 웅덩이)이 0~10개 사이로 주어진다. 이때 집과 학교의 위치는 각각 (1,1) (m, n) 위치에 고정이다. 움직일 수 있는 방법은 오른쪽/아래로 움직이는 방법밖에 없을 때, 최단경로로 집에서 학교로 갈 수 있는 경로의 수를 구하는 문제이다. 문제 접근 단계 일단 출발지에서 목적지까지 경로를 구해야 하고, 맵과 장애물이 주어졌다. 높은 확률로 그래프 탐색 문제로 해결하는 것으로 보인다. 일단 움직일 수 있는 조건을 보면 오른쪽과 아래로밖에 이동하지 못한다. 그리고 찾아야 하는 것은 최단경로의 개수이다. 그렇다면 해당 경로가 최단경로인지 아닌지 어떻게 판단할 수 있을까? 사실 판단할 필요 없다. 왜냐하면 오른쪽과 아래로만 움직일 수 있다면..

문제 이해 단계 주어지는 입력은 사용할 수 있는 숫자 N과 만들어야 하는 Number 2개이다. 숫자 N을 통해 할 수 있는 작업은 아래의 2가지 작업 밖에 없다. 1. 사칙연산 2. N을 연속해서 이어 붙이기(ex : 22, 33, 555) 이를 이용해서 Number를 만드는데, 숫자 N을 최대한 적게 사용해야 한다. 이때 숫자 N은 몇 개일까? 만약 8개가 넘는다면 -1을 반환한다. 문제 접근 단계 처음에는 해당 문제가 단순한 사칙연산을 이용한 수학 연산 문제라고 생각했는데, N을 연속해서 이어 붙일 수 있다는 조건에서 단순한 수학 연산은 아닐 것이라는 생각이 들었다. 그래서 일단 N이 1개 일 때부터 만들 수 있는 조합에 대해 적어보기로 했다. N이 1개일 때 N N이 2개일 때 NN, (N+N),..