전체 글 (336) 썸네일형 리스트형 백준 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.. 백준 13913번 숨바꼭질 4 (C++) 시험기간엔 PS가 재밌어진다 ㅎ 숨바꼭질 1,2,3에 이은 4번째이다. bfs라는 풀이법은 변하지 않았지만 조금 씩 세부적인 사항을 요구한다. 이번에는 지나온 경로에 관해 출력해야한다. 지나온 경로를 출력하는 것에 가장 좋은 방법은 dfs이지만 이 문제에는 "최단거리" 이기 때문에 dfs를 선택하면 무조건 시간초과가 뜬다. 때문에 bfs에서 함수를 더해 경로를 저장해야한다. 그 방법은 배열을 만들고 그 배열에 이전 정보를 저장해놓는 것이다. DP와 비슷하다고 보면 된다. #include #include #include #include using namespace std; queue Q; int currentnumber[100001] = {0,}; int n, m; bool visited[100001] =.. 백준 17070번 파이프 옮기기 1(C++) 가장 먼저 생각할 수 있는 방법은 DFS였다. 최소로 이동하는 것도 아니고 각 지점마다 움직일 수 있는 방법이 한정되어있다. 각 노드에서 따질 것이 많다면 DFS가 유리하다. 각 지점마다 방향의 상태를 지정해줘야하기 때문이다. 그런데 이 문제를 보면 시간제한이 1초로 빡세지만 집의 크기가 무려 3~16으로 매우 편하게 주었다. N이 조금만 커져도 이 문제는 dfs bfs로 풀 수 없다. 나름 잘 풀었다고 생각했는데도 시간은 104ms로 오래걸렸다. 이 문제의 의도는 다이나믹 프로그래밍이다. dfs로 최적화하는법도 있겠지만 이문제는 온리 DP로만 풀이가 가능한 것 같다. 채점 현황을 보니 골드 하위정도 티어들은 모두 그래프로 풀고 골드 상위부턴 DP로 풀이했다. 다음에 DP로 다시 풀어봐야겠다. 1. 맨 .. 이전 1 ··· 36 37 38 39 40 41 42 다음
