노래부르다

전형적인 DP문제이다.DP를 워낙 못하다보니, 계속해서 DP에 익숙해지고 감잡는데 초점을 맞춘다... 알고리즘 풀이입력 배열 : 입력받은 입력 배열값. 설명에서 vec이라 하겠음.dp배열 : 해당 인덱스가 최대값일 때, 수열의 최대 원소 갯수값 해당 문제는 점화식이 따로 있다기 보다는 증가하는 수열의 기본적인 문제였다. (1) 현재 vec의 인덱스 i의 원소가 하위(vec[1] ~ vec[i-1]) 원소보다 커야하는 것과 (2) (1)의 조건에 해당하는 원소 중, 길이가 가장 긴 값을 가져와서 dp배열에 +1한 수를 넣는다. 설명이 어렵다면 코드를 보면서 이해를 추가하기를 바랍니다. #include #include using namespace std;int main() { ios::sync_with..

구현, 문자열, 시뮬레이션 알고리즘 문제이다.  알고리즘 풀이눈을 깜빡이는 횟수가 최대 10억인거로 보아서, 일반적인 반복문으로는 시간복잡도를 초과할 것이다.그러므로 눈을 깜빡이는 횟수 N을 줄이는 어떤 방법이 존재한다.이때, 주어진 문자열이 다시 원래대로 돌아오는 사이클이 존재하는 것을 알 수 있다.또 사이클이 문자열의 길이와 상관없이 불규칙적인 것 또한 아는 것이 중요하다. 그러므로, 먼저 사이클의 횟수를 구하고 사이클의 횟수보다 눈을 깜빡이는 횟수가 더 많다면둘을 나눠 남는 나머지를 구한다.해당 나머지는 사이클을 돌고 난 뒤, 마저 깜빡이는 수이다.해당 나머지만큼 실제로 문자를 옮겨준다면 문제는 풀린다.-> 문자열의 이동규칙은 코드를 보며 파악하자.#include #include using name..

https://www.acmicpc.net/problem/2096문제 분석문제 조건생각보다 단순한 문제다. 행은 N(입력값), 열은 3인 배열에서 이동할 수 있는 제약이 있고 이들의 최대/최소값을 구하는 문제이다. 문제를 보자마자 무조건 dp겠다 싶었다. 그래서... dp임은 인지했지만, 답이 잘 나왔음에도 메모리가 초과되었다는 것을 보았다. 4MB????🤔: 대체 4MB는 뭐야?! 문제에서는 N의 최대값은 10만인데... 입력값만 받아도 최대 30만 데이터를 저장하는 배열을 만들어야하는데?이걸 어떻게 풀라는거야...문제 풀이DP문제를 풀기 위해서는 무조건 이전에 계산했던 최적의 값들을 무조건 저장해둬야한다고 생각했다... 그래서 처음 생각했던 오답풀이는 이러하다... ⚠️오답풀이!!!⚠️☠️ 1. 입..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 분석 문제 조건 문제는 적록색약인 사람이 본 그림의 구역과, 적록색약이 아닌 사람이 본 그림의 구역을 출력하도록 한다. 2차원 배열의 그림판이 주어지고, 그림판의 각 칸은 R, G, B 중 하나가 칠해져있다. 적록색약인 사람은 R와 G의 색을 구분하지 못하기에 같은 구역으로 처리한다. 이때, 상하좌우로 인접한 경우에는 같은 구역이라 한다. 💡 문제를 마주하자마자, 깊이 우선 탐색(DFS)로 풀어야한다는 것을 알아야 한다. 깊이 우선 탐색의 대표적인, ..

2195번: 문자열 복사 첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 www.acmicpc.net 문제 분석 원본 문자열 S와 이 문자열을 부분 복사한 집합인 새로운 문자열 P간의 관계에 대한 문제이다. 문제는 copy(s, p)라는 함수를 사용해서 복사하는데, 's번 문자부터 p개의 문자를 P에 복사해서 붙인다'라는 의미이다. ex) S = "abc", P = "abcbcbb"라 할 때, copy(1, 3) / copy(2, 2) / copy(2, 1) / copy(2, 1) 를 수행하여 P를 만들 수 있다. 1단계 : "abc"..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 분석 문제에서는 '규칙'과 함께, 카드를 한묶음으로 만드는 '최소 비교 횟수'를 구하도록 한다. 💡규칙💡 여러 개의 카드 묶음을 뭉치기 위해서는, 두 묶음씩 뭉칠 수 있다. N개의 묶음이 시작이고, 이 중 2개의 묶음을 하나로 뭉쳤다면, 다시 N - 1개의 묶음에서 2개를 골라 뭉친다. 총 1개의 묶음이 완성될 때 까지 이 과정을 반복한다. 문제에서 말한 과정을 짧게 3가지 단계로 표현하였다. 결국 두 묶음씩 조합할 때의 조건이 중요한 거 같..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 분석 문제는 (1) 모든 집을 칠하는 최솟값을 구하고자 한다. N개의 집이 순서대로 있고, i번째 집을 기준으로 i - 1번째, i + 1번째 집은 i번째와 색이 같지 않아야 한다. (2) 즉, 내 집과 양 옆집의 색이 겹치지만 않으면 된다. 집마다 칠할 수 있는 빨, 초, 파 색의 가격이 각각 주어지고, 이의 최솟값을 구해야한다. 🤫 : 음... 각 집마다 칠할 수 있는 가장 싼 색을 고르면, 옆 집이랑 겹칠수도 있고... 그렇다고 ..

18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 분석 좌표 압축의 문제를 읽어보면, 2가지에 초점을 맞추면 쉽게 문제를 해결할 수 있다. N개의 좌표에서 좌표 X를 압축한 결과 X'는, X보다 작은 서로 다른 좌표의 개수이다. 여기서 좌표는 중복될 수 있기에, '서로 다른'에 집중해야한다. ex) 만약 좌표 X = 3이라 할 때, X보다 작은 좌표가 { 1, 1, 2 } 가 있다고 가정하자. 이 경우, 압축 좌표 X' = 2이다. 입출력값이 정렬되지 않는..

13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 분석 트럭 문제를 읽고, 트럭이 순차적으로 다리에 오르는 것에 초점을 맞추고 알고리즘을 생각했다. 이에 while문에서 '1초가 지날 때마다 다리에 오르는 트럭'을 중점으로 뒀다. 그러면 1초가 지날 때마다 생각해야 하는 경우는 무엇이 존재할까? 1초가 지난다면, 다리 위의 트럭이 한 칸씩 움직여야 한다. 다리 끝의 트럭은 1초가 지난다면 다리에서 내리게 되고, 다리가 견디는 현재 하중에서 빠져야 한다. 트럭이..

정렬 알고리즘이란?-> 데이터를 정해진 기준에 따라 의미있는 구조로 재설정하는 것을 말한다. 즉, n개의 입력이 주어지면 내가 원하는 기준에 따라 데이터를 정렬하는 방식이다. ex) 1 ~ 10의 숫자가 무작위로 배치되어있다면, 이를 오름차순으로, 혹은 내림차순으로 설정하여 데이터를 순서대로 설정하는 것을 말한다. 정렬 알고리즘에는 대표적인 6가지의 알고리즘이 존재한다.이를 총 2편에 나눠서 배울 것이며, 시간이 가장 느릴 방식부터, 가장 빠른 방식까지 알아보도록 하겠다. 버블 정렬주어진 데이터의 인접 요소끼리 비교하고, 기준에 따라 swap하는 형식. O(N^2)선택 정렬전체 데이터를 비교한 뒤, 기준에 맞는 데이터를 앞으로 보내는 것을 반복하는 형식. O(N^2)삽입 정렬대상을 선택하고, 정렬된 영역..