티스토리

코딩균의 개발Log

검색하기

블로그 홈

코딩균의 개발Log

codinggyun.tistory.com/m

코딩균 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[DP] 백준 11058 : 크리보드 - 파이썬 Python https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 생각하기 dp[N]을 N번 키보드를 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수라고 한다 먼저 각 버튼의 종류를 살펴보자면 A를 추가 출력하기 위해 한번 누르면 된다 ctrl + A, ctrl + C는 출력을 위한 것이 아니라 ctrl + V의 선행 조건이.. 공감수 0 댓글수 0 2022. 3. 16.
[DP] 백준 12869번 : 뮤탈리스트 - 파이썬 Python https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net DP문제는 내가 제일 어려워하는 유형이라 이 문제는 풀지 못하였다 백준 강의 앞부분에서 힌트를 얻고 풀어본 것을 써본다 생각하기 SCV의 값은 3이하로 매우 작다 각각의 SCV는 체력을 가지고 있다. DP[i][j][k] - SCV의 체력이 i, j, k 일때 모두 파괴하는 최소 공격횟수 SCV가 3마리라고 가정으로 하고 만약 2마리인 경우에는 DP[i][j][0]으로 처리해주면 된다 따라서 3차원 DP를.. 공감수 0 댓글수 0 2022. 2. 16.
[DP] 백준 1496번 : 기타리스트 - 파이썬 Python https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 생각하기 N개의 연주곡 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주 V[i] - i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨 (차이) -> P + V[i] 혹은 P - V[i] 로 연주 가능 이때, 0 공감수 0 댓글수 0 2022. 2. 4.
[DP] 백준 11066번 : 파일 합치기 - Python 파이썬 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 생각하기 파일을 합치는데 연속된 파일들을 합치는 것이 포인트였다 1 2 3 4 의 파일들이 있다면 1 (2,3,4) (1, 2) (3, 4) 1, 2, 3) 4 -> 3가지의 경우 중에서 작은 합치는 비용을 찾으면 된다 결국 작은 문제들이 합쳐져서 큰 문제의 답을 이루는 DP를 사용하면 된다는 것을 알았다 점화식을 세워보면 dp[i][j] 는 i번째 data 부터 j번째 data까지 합치.. 공감수 0 댓글수 0 2022. 1. 21.
[DP] 백준 15989번 : 1,2,3 더하기 4 - 파이썬 Python https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net n을 1,2,3의 합으로 나타내는 개수는 이전 수를 1,2,3의 합으로 나타냈을 때의 수에 영향을 받는다 dp방법으로 풀어내기로 한다 중복되는 1 2 1 / 1 1 2 같은 조합을 없애기 카운팅 안하기 위해서는 각각의 조합에서 대표만 카운팅해야 함 1 1 2 같은 경우만 카운팅 하기 위해서는 1을 사용하는 방법과 2를 사용하는 방법을 .. 공감수 0 댓글수 0 2022. 1. 16.
[DP] 백준 11060번 : 점프 점프 - Python 파이썬 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 생각하기 어디로 가는가? 무조건 오른쪽으로 점프하므로 문제의 크기가 점점 작아진다 마지막 칸에 오는 방법은 모두 이전들 칸에서의 방법중 하나이다 dp[i] : 각 칸 도착시의 최소 점프 횟수 이렇게 설정해놓으면 마지막 칸까지 각칸을 경유해서 점프해 나갈때, 모두 최소인 칸만 경유하는 것이므로 마지막 칸도 최소가 된다 구현하기 0번째 칸부터 시작해서 N-1번째 칸까지 N-1을 넘지 않는 .. 공감수 0 댓글수 0 2022. 1. 12.
DP 풀이방법 5가지 정리 - 백준 11048번 : 이동하기 Python 파이썬 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 방법1 : Top-Down 문제가 점점 작아지는 방식으로 접근 목적지까지 어떻게 왔는지에 대해서 생각하며 접근 결론에 도달하기까지의 과정에 대해 생각하며 접근 dp[i][j] : (1,1)에서 시작하여 (N,M)까지 가는 중에 (i, j) 까지 갔을 때의 가진 최대 사탕의 수 왼쪽에서 온 경우 : (i, j-1)에서 온 경우 왼쪽 위에서 온 경우 : (i-1, j-1)에서 온 경우 .. 공감수 0 댓글수 0 2022. 1. 11.
백준 11048 : 이동하기 - 파이썬 Python https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 생각하기 가져올 수 있는 사탕의 최대를 구하는 것이기 때문에 생각을 했다 DFS로 모든 경우를 다 해봐? 규칙 같은 것을 찾아서 DP로 만들어볼까? DFS로 풀면 시간초과가 발생할 것 같다는 생각이 들었다. 1000 * 1000 인데 각 경우가 3가지 경우만 고려하더라도 각 칸은 세가지의 경우로 뻗어나갈 가지수를 가지고 있으므로 최대 가로 세로 1000칸이라면 3000000의 가지수.. 공감수 0 댓글수 0 2022. 1. 6.
[DP] 백준 6603번 로또 (Python) 생각하기 처음 이 문제를 보고서는 브루트포스 문제라고 생각하고 for문을 중첩하여 풀어야겠다고 생각했다 12345678 이면 678을 67, 68, 78 이렇게 for문으로 처리해야지! 하지만 For문으로 처리하려다 보니까 난리도 아니었다.. 너무 코드가 더러워졌다 더러워지면 질수록 이건 틀린거다..! 그래서 다시 뒤엎고 생각을 했다. 다시한번 잘 보니 이 문제는 DFS 문제였다 사실 어떻게보면 DFS도 모든 경우의 수를 들여다 보는 것이기 때문에 크게 보면 브루트포스에 속하긴한다 브루트포스라고 해서 다 for문 돌리는건 아니다! 구현하기 input으로 들어온 각 수를 돌면서 dfs를 하면 된다 depth : 총 여섯자리까지 구하면 되는 것이기 때문에 Dfs에서 깊이는 6까지만 찍고 올라오면 된다 out.. 공감수 0 댓글수 0 2021. 10. 16.
[DP] 백준 20500번 - Ezreal 여눈부터 가네 - Python 파이썬 생각하기 처음에는 일차원 배열의 DP로 접근을 했었다. N=1,2,3일떄를 써놓고 규칙을 찾아보려해도 아무런 답이 나오지 않았다... 결국 검색을 통해 아이디어를 얻어낼 수 있었다... (아이디어만 봤다.. 아직 실력이 많이 부족.. ㅠ) 1과 5만 사용하기 때문에 기존 숫자에 맨 앞에 1혹은 5를 조합하는 방식이다 예를 들어 1의 자리라면 1, 5가 있을 텐데 앞에 11, 15, 51, 55가 되는 방식! 그렇게 되면 10과 50을 더해주는 것인데 15의 나머지는 10의 나머지 더하기 5의 나머지를 더한 15가 된다 -> 그래서 15는 15의 배수인것이다 (당연한 얘기지만 나머지 관점에서 봤을 떄 15잖아) 두수를 더할 때 두수의 나머지를 더한값과 더한 값의 나머지는 같다 -> 나머지 더한값이 15를 .. 공감수 0 댓글수 0 2021. 10. 15.
[DP] 프로그래머스 고득점킷 N으로 표현 - Python 파이썬 생각하기 N을 사용한 횟수에 따라 단계를 나눌 수 있다 N을 사용한 횟수에 따라 단계를 나누게 된다면 N을 구하기 위해서는 이전에 구했던 것들을 사용해야 한다. 예를 들어 N을 3번 사용했다면 N을 1번 사용한 경우의 수와 N을 2번 사용한 경우의 수를 합치면 된다 따라서 이 문제는 DP를 통해 풀어보는 것으로 한다 구체화하기 dp[i] 는 N을 i번 사용했을 때 만들 수 있는 수의 집합 ex ) N= 3일 때, dp[1] = { 3 } dp[2] = {33, 6, 0, 9, 1} 따라서 dp[i]를 만들기 위해서는 이전까지의 모든 결과들을 조합하여 dp[i]를 만들어야 함 dp[k] = dp[i] 사칙연산 dp[k-i] (i=1 ~ k-1) 이런식으로 점화식 구성이 가능하지 않을까 싶다 1. 33, 3.. 공감수 0 댓글수 0 2021. 10. 10.
[DP] Dynamic Programming 동적계획법 이란? 컴퓨터의 연산 속도는 한계가 있고, 메모리 공간도 한계가 있으니 최대한 돌려쓸 수 있는 방법이 없을까? 다음의 조건이 만족하면 DP로 접근해야 한다. 완전탐색으로 답을 찾으려는데 너무 많은 시간이 걸린다 재귀로 진행했을 시에 오버헤드가 났을 경우 DP로 접근해야 하는지 최종적으로 다음 조건을 판단한다 큰 문제가 작은 문제로 나누어진다 작은 문제에서 구해지는 답들이 큰 문제들의 정답 구하는데에 영향을 준다 DP에는 두가지 방식이 있는데 Top-Down (하향식)과 Down-Top (상향식)이 있다 트리 형식으로 생각하고 Top-Down 피보나치 수열을 통해 한번 정리해본다 피보나치 수열 n번째 수는 n-1 번째 수와 n-2 번째 수의 합 1번째와 2번째 수는 1 Top-Down 하향식 방식 구해야할 답을 .. 공감수 0 댓글수 0 2021. 9. 27.
[DP] 백준 1757번 - 달려달려 DP를 안 쓴다면) 매분 달릴지 말지를 결정하는 완전 탐색을 진행해야 한다. 2^N이 되는데 N DP? DP를 쓴다면) 상태 3가지 존재 1. 몇분 2. 지침 지수 3. 달리는 상태 dis[n] -> 각 시간에서의 갈 수 있는 거리 dp[x][y][z] -> '최대한 갈 수 있는 거리'로 dp를 설정 x : 분 y : 지침 지수 z : 달리는 상태 (1:달림 0:쉼) M은 2라고 가정 지침지수 0인 경우 y=0) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1], dp[x-1][y][0] ) 지침지수 1인 경우 y=1) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1] ) y-1에서 값을 가져올 수 없는 이유 >> y-.. 공감수 0 댓글수 0 2021. 2. 5.
[DP] 백준 15988번 - 1, 2, 3 더하기 3 생각하기 20을 나타내는 방법의 수 = 4를 나타내는 방법의 수 x 16을 나타내는 방법의 수 각 숫자 나타내는 방법의 수 구하는 방법 = 백트레킹? 하짐나 DP로 풀어야 하는 문제이기 때문에 DP적으로 생각! dp[num] = dp[num-1] + dp[num-2] + dp[num-3] 마지막에 각 단계에서 부족했던 숫자들만 더해서 값을 뽑을 수 있다 1을 구하는 방법에서 2을 더하는 방법 2를 구하는 방법에서 1을 더하는 방법 이미 구해 놓은 값들을 통해 구해낸다 * 각 숫자 때마다 dp값을 도출하기 #include #include #include #include #include #include #include #include #include using namespace std; #define end.. 공감수 0 댓글수 0 2021. 1. 28.
[DP] 백준 2748번 - 피보나치 수 2 case1) n이 0 혹은 1일 때, 0 / 1을 출력 case2) n이 2이상 일 때, memoizate해 놓은 이전 두개의 수를 더한 수를 출력 하지만 이런식으로 진행한다면 시간초과가 발생한다 memoization을 사용하여 연산을 최대한 줄여야 한다 #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' int N; long long fib[100]; long long pibo(int n) { if(n==0){ return 0; } if(n==1){ return 1; } if(fib[n]!=-1) return fib[n]; else{ fib[.. 공감수 0 댓글수 0 2021. 1. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.