깜태

링크 : https://www.acmicpc.net/problem/1937 DP와 DFS를 적절히 섞어서 푸는 문제이다. 오래 매달리다가 해답을 검색해보고 풀었다. 푸는 방법 1. dfs에서 첫 방문하는 지점을 1로 초기화한다. 2. 주변 4방향에 더 큰 값이 있는지 비교해보고, 있으면 현재값과 비교해 더 큰 값을 취한 뒤, 더 방문할 곳이 없으면 반환한다. 3. 모든 지점에 대해 1,2를 반복한다. 오래 걸렸던 이유 1. 고정관념 백준에서 다이나믹 프로그래밍 카테고리에 있어 DP만으로 풀어보려고 했는데, DP만으로 불가능하단 생각이 들고나서야 DFS를 생각하고 접근해보았다. 이 생각이 들기까지 시간이 오래 걸린 것도 나의 공부가 모자란 것도 컸다. 다음부턴 문제를 꼭 DP라고만 생각하지 않고 어떻게 풀..

최근에 백준에서 다이나믹 프로그래밍(DP)를 공부하다가 처음 보는 유형의 문제가 있어 글을 쓰게 되었습니다. [ 관련 문제 : 백준 12865 평범한 배낭 www.acmicpc.net/problem/12865 ] Knapsack 문제란? 어떤 도둑이 보석상에 들어가 보석을 훔친다고 했을 때, 배낭의 용량을 넘치지 않게 담아야 하고, ( 넘치면 훔칠 수 없다는 가정 ) 돈을 가장 많이 벌 수 있도록 담는 방법에 대해 얘기하는 것을 Knapsack 문제라고 합니다. Knapsack 문제의 경우는 담는 물건이 나눌 수 있는 경우, 단순하게 담을 수 있냐 없냐 (0-1) 두 가지의 종류가 있지만 지금은 단순하게 담는 0-1 Knapsack 문제에 대해 쓰겠습니다. 이게 DP랑 무슨 상관?? 단순하게 생각해보면 ..

문제링크 : www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 푸는 방법 자세히 보면 수는 0으로 시작할 수 있다는 말이 있는데, 이는 01 02 03 04 05 도 가능하다는 말이 됩니다. 엥?? 그럼 1로 시작하는 건 당연히, 12 ~ 19까지, 2로 시작하는건 22~ 29 까지 8로 시작하는건 89까지 입니다. 그럼 [i][n]에 해당하는 값은 i-1에서 n~9까지의 값을 더하면 됩니다. 이전에 계단수 문제를..

문제 링크 www.acmicpc.net/problem/19947 푸는 방법 DP를 이용해 해당 년도에 얻을 수 있는 최대값을 구하면 됩니다. 점화식은 다음과 같습니다. dp[i] = max(dp[i-1]*1.05, dp[i-3]*1.2, dp[i-5]*1.35) 만약 10000원과 6년이 주어졌다고 하면, 1년 뒤에 얻을 수 있는 최대 금액은 dp[1] = dp[0] *1.05 = 10,000 * 1.05=10,500, 2년 뒤에 얻을 수 있는 금액은 dp[2] = dp[1] * 1.05 = 10,500 *1.05=11,025, 3년 뒤에 얻을 수 있는 금액은 dp[3] = max(dp[2] * 1.05 , dp[0] * 1.2) = max(11,025 * 1.05, 10000*1.2) = max (11..

푸는 방법 DP(Dynamic Programming)을 이용하여 행이 증가될 때마다, 최고의 값을 구합니다. 행을 거듭해가며 더할 때마다 삼각형을 해체해서 경우를 살펴보면 다음과 같습니다. 1. 왼쪽으로만 진행하는 경우 3. 오른쪽으로 증가하는 경우 에는 단순하게 이전행의 마지막값을 더해주면 됩니다. 하지만 2번 같이 값이 겹쳐지는 경우에는 각각 더했을 때 최대가 되는 경우를 비교해 선택하면 됩니다. 코드 n = int(input()) tri = [] for _ in range(n): tri.append(list(map(int, input().split()))) for i in range(1, n): for j in range(i+1): if j==0: #왼쪽 행 tri[i][j] +=tri[i-1][j..

문제 링크 : www.acmicpc.net/problem/19621 처음 접근한 방법은 완전탐색 알고리즘이였습니다. 가능한 경우의 수를 나열해보자는 방식이였는데, 경우의 수를 알아야 나열할 수 있는데 자꾸 재귀적으로 짤 수 밖에 없었고, 방법이 잘못되었단 생각이 들었습니다. 결국 실패해서 검색해보고 접근방법을 깊이우선탐색(DFS)로 변경하여 배웠습니다. [참고] [1]: jinho-study.tistory.com/926, [2]: txegg.tistory.com/138 푸는 방법 각 시간을 기준으로 잡았을 때 가능한지를 탐색해야 합니다. 1. 알고리즘 상의 탐색할 데이터의 끝을 설정하여, 끝에 다가갔다면 마지막 값을 리스트에 담습니다. 2. 끝이 아니라고 생각하면, 현재 값을 계속 추가해가며 더합니다. ..

링크 : www.acmicpc.net/problem/14502 푸는 방법 해당 문제가 왜 브루트포스에 있는가부터 고민을 하다가 해결하게 되었습니다. 벽을 3개 설치한다는 것은 0으로 되어있는 빈 공간 중 3개를 설치하는 것을 의미하고, 0인 행렬 포지션들을 나열해서 그중 3개를 선택하는 순열을 이용했습니다 그 다음, 백트래킹을 이용해 바이러스가 퍼지는 알고리즘을 설계하여 퍼뜨린 후 그 내부 안에서 0의 숫자를 세서 순열 중에서 최고값을 반환하게 만들었습니다. 나름 가독성 있게 써봤는데, 만족하셨으면 좋겠네요 감사합니다 코드 import itertools import copy N, M = map(int, (input().split())) arr = [0 for x in range(N)] for i in r..

링크 : www.acmicpc.net/problem/18429 푸는 방법 1. N일동안 A개의 운동을 선택해서 진행하므로, itertools를 이용해 순열을 생성합니다. 그리고, 이 경우가 할수 있는 운동의 최대 개수입니다. 2. N일동안 운동하는 중에, 근손실이 발생하면 안되므로 매일마다 운동량이 0보다 작아지는지 확인하고 만약 작아진다면 최대 개수에서 1개씩 뺍니다. 3. 전체 가능한 운동 개수에서 근손실이 발생한 경우를 뺀 나머지를 출력합니다. 코드 import itertools N, K = map(int, input().split()) A = list(map(int, input().split())) cases = list(itertools.permutations(A, N)) count = len(..

링크 : www.acmicpc.net/problem/2231 푸는 방법 1. 숫자를 입력받고, 반복문을 돌며 한자리씩 나눕니다. 2. 각 자리수의 합과 수의 합이 입력받은 숫자와 같다면 생성자 리스트에 추가합니다. 3. 마지막으로 최소값을 반환합니다. 코드 N = int(input()) hap = list() for i in range(N): D = str(i) sum = 0 for x in D: sum += int(x) if sum + i == N: hap.append(i) if hap != []: print(min(hap)) else: print(0)

링크 : www.acmicpc.net/problem/14888 푸는 방법 가능한 연산의 경우를 순서대로 배열해야 되기 때문에, itertools 내부의 permutation(=순열)를 이용합니다. (itertools 라이브러리를 이용하면 편-안하게 다양한 경우의 수를 만들 수 있습니다) 1. 연산자들을 나란히 받아서 하나의 리스트로 합친 후, 다양한 순서 개수를 따져야 하므로 순열로 변환합니다. 2. 경우의 수마다, 하나씩 순차대로 연산을 진행 3. 진행한 값을 최소, 최대값과 비교해가며 갱신한뒤, 마지막으로 출력합니다. import itertools N = int(input()) numbers = list(map(int, input().split())) operators = list(map(int, i..