본문 바로가기

전체 글

 (403)
백준 14499번 주사위 굴리기 (C++) 맞왜틀 때문에 정말 고생한 문제.. 사람들이 x,y 어쩌구 하는데 난 그게 문제가 아니었고 (그게 무슨 소리인지도 모르겠더라) 문제를 해석하는게 가장 중요했다. 1. 주사위가 기본적으로 어떻게 세팅되어있는지 확인해야한다. 2. 타일과 닿아있는 부분이 바뀌는데 출력은 주사위 윗부분임을 주의해야한다. 3. 주사위를 보드 바깥으로 보내면 반드시 아무 작업도 이루어지지 않아야한다. 난 3번을 그냥 출력만 안나오게 짰다가 맞왜틀의 늪에 빠져서 몇시간을 낭비했다 ㅠㅠ 가장 중요한 로직은 주사위를 동서남북으로 돌릴때 어떻게 돌려줘야할지가 문제이다. 다른 사람들은 모르겠지만 나는 전개도를 4x4 로 구성해 전개도를 계속 갱신해주었다. 이런식으로 주사위의 전개도를 갱신한다. 위는 예로 북쪽으로 이동했을 시이고 동서남북 ..
백준 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가 들어왔을 때 -> 아무것도 없고 처음이므로 증가 하는..

티스토리툴바