본문 바로가기

전체 글

 (386)
백준 11054 가장 긴 바이토닉 부분 수열 (C++) 부분 수열 시리즈 3번째이다. https://tigerfrom2.tistory.com/33 먼저 이 문제를 풀고 왜 dp를 쓰는지 알고 오는 것이 좋다. 백준 11053 가장 긴 증가하는 수열(C++) 처음 봤을 땐 "엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다. 그런데 정답률이 낮아서 의아했다. 그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중 tigerfrom2.tistory.com 매우 비슷한 문제이지만 dp의 갱신 조건이 더 까다로워졌다. 위 문제는 증가하기만 하면 +1로 갱신이 편리했지만 바이토닉 수열은 따질 것이많다. 우선 바이토닉 수열이 무엇인지 알아야한다. 바이토닉은 증가하다가 감소하는 수열이다. 여기서 순증가나 순감소 수열도 바이토닉 수열에 ..
프로그래머스 - 짝지어 제거하기(C++) 문제 설명 처럼 2개 짝짓고 제거하면 시간초과로 풀 수 없다. 첫 풀이는 다음과 같았다. 먼저 abcc 이런식으로 a, b가 홀수개이면 절대 문장은 제거되지 않는다. 그렇기 때문에 먼저 원소들의 개수를 세는 작업을 했고 이 작업을 통과하였을 때 제거 연산을 해봤다. 그러나 별짓을 다 해도 저 3개의 효율 테스트를 통과할 수가 없었다... 결국 아이디어를 구하기 위해 질문하기를 보았는데 답은 "스택" 이었다. 최대 크기가 100만일 때 부터 알아봤어야하는데 나는 아직 멀었다. 85점까진 받았기 때문에 코테나 대회였다면 바로 넘겼을 문제이기는 하다. 스택을 사용한다. ex) dcaabbcd 가 들어왔을 때 1. d를 꺼내 c와 비교한다. 둘은 다르다! 그러므로 꺼낸 d를 또다른 서브 스택에 넣어둔다 . 현재..
백준 11055 가장 큰 증가 부분 수열(C++) https://tigerfrom2.tistory.com/33 백준 11053 가장 긴 증가하는 수열(C++) 처음 봤을 땐 "엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다. 그런데 정답률이 낮아서 의아했다. 그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중 tigerfrom2.tistory.com 수열 시리즈 문제이다. 이번에는 합을 DP에 담아서 갱신하면 된다. 코드가 매우 유사하므로 먼저 위 문제를 풀어보는게 좋다. 1 3 2 4 를 예로 들어보자. 모든 DP[N] = N 으로 갱신되어있다. 왜? 본인은 언제나 합에 포함되니까 1. 1이 들어오면 -> DP[1] = 1 2. 3이 들어오면 -> DP[3] = max(DP[1] + DP[3] , DP[3]) ..
백준 1932 정수 삼각형(C++) DP의 기본적인 문제. 프로그래머스에서는 같은 문제가 레벨3로 어려운 문제에 속했는데 백준에선 실버 판정을 받았다. 하삼각행렬로 삼각형을 저장하고 각 행렬의 숫자를 적절하게 갱신해주면 되는 문제다. #include #include using namespace std; int DP[501][501]; int main() { int n; cin >> n; for (int i = 0; i > DP[i][j]; } } for (int i = n - 2; i > -1; i--) { for (int j = n - 2; j > -1; j--) { if (i < j) continue; DP[i][j..
프로그래머스 - 귤 고르기(C++) 이번에도 빡구현문제다. 프로그래머스 구현문제들은 문제를 이해하긴 되게 쉬운데 막상 어떻게 하지? 생각하면 잘 안풀리는게 특징이다. * 문제풀이 * 1. 주어진 귤의 사이즈대로 map에 삽입한다. 2. 갯수가 큰 순서대로 sort 한다. 3. 1개씩 더하고 k 보다 크거나 같아지면 멈추고 지금까지 넣은 사이즈의 귤의 갯수를 리턴한다. 다른 사람들 풀이보니까 짧고 간단하게 했던데.. 봐도 이해도 안가고 모르겠다. 그리고 실행시간을 보니 그닥 좋은 풀이는 아닌 것 같다. #include #include #include #include #include using namespace std; bool compare(const int a, const int b){ return a > b; } int solution(..
프로그래머스 - 할인 행사 (C++) 문제 자체는 이해하기 어렵지 않다. 또 주어지는 배열의 길이가 길지 않기 때문에 시간초과를 걱정할 필요가 없어 완전탐색 식으로 전부 비교해보며 풀었다. 문제 유형은 별다른 알고리즘을 요구하는 문제는 아니고 그냥 빡구현이다. - 문제풀이 먼저 주어진 want 와 number를 각 맵을 이용해 넣어둔다 apple : 2 banan : 3 이런식으로 넣어둔다. 그 다음 discount는 10개씩 탐색해야하므로 만약 14개의 discount 가 주어졌다면 0~9 1~10 2~11 3~12 4~13 이렇게 5번 탐색해야한다. 그러므로 discount.size() - 10 으로 범위를 잡아준다. 그리고 discount도 중복을 제외하고 맵에 넣어둔다 apple : 2 banana : 3 pork : 2 이런식으로,..
백준 11053 가장 긴 증가하는 수열(C++) 처음 봤을 땐 "엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다. 그런데 정답률이 낮아서 의아했다. 그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중요한 건 문제 해석을 완벽히 해야한다.. 이 문제의 이름을 잘 보자 " 가장 긴 -증가하는- 수열 " 그러니까 예를들어 5 4 3 2 1 이라는 순서로 들어왔을 때 그냥 1 2 3 4 5라고 생각할 수 있지만 이 문제는 "수열" 이다. 순서를 절대 바꾸면 안된다. 그러므로 증가하는 부분 수열의 길이는 1이다. 이 문제는 들어오는 숫자가 과연 증가하는 수열을 만들수 있는가? 물어보는 문제이다. 예를 들어보자! 5 2 4 3 2 순으로 들어왔다고 가정하자. 1) 5가 들어왔을 때 -> 아무것도 없고 처음이므로 증가 하는..
백준 1076 저항(C++) 뭔가 PS하나는 풀고싶은데 머리는 쓰기싫어서 브론즈 문제 하나 풀어봤다! 그냥 열심히 매핑하고 값이 매우 크니까 long long 자료형을 쓰고 쓸대없지만 왜인지 처음에 문자열로 더할 값을 받아서 문자를 정수로 바꿔줬다. #include #include #include using namespace std; map reg; map regi; int main() { reg.insert(make_pair("black", 1)); reg.insert(make_pair("brown", 10)); reg.insert(make_pair("red", 100)); reg.insert(make_pair("orange", 1000)); reg.insert(make_pair("yellow", 10000)); reg.inser..

티스토리툴바