Devlog_by_0giru

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2차원 다이나믹 프로그래밍을 활용하는 대표적인 문제다. 원래는 '안녕_1535' 문제를 풀기 위해 먼저 풀어본 문제인데, 백트래킹을 이용한 재귀함수 호출로 풀려고 시도해봤지만 시간 초과로 통과하지 못했다. pypy3로도 안되더라. 처음 내가 시도했던 방법을 그림으로 그렸다. 물건이 A B C D 네 가지가 있다고 가정한 후 각 물건을 넣느냐, 마..

www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N( result: result = cur_joy return # 현재 사람을 선택할 경우 Recursion(idx+1, cur_joy+joys[idx], cur_life-costs[idx]) # 현재 사람을 선택하지 않을 경우 Recursion(idx+1, cur_joy, cur_life) Recursion(0, 0, life) print(result) 2차원 다이나믹 프로그래밍을 이용한 풀이 (체력을 깎아가는 방식이 아닌 0에서 채우는 방식으로 풀었다.) """ 2차원 DP를 이용한 풀이 """ n = int(input()) costs = [0] joys = [0] cost = list(map(int, inpu..

가장 긴 증가하는 부분 수열1 에 이은 시리즈 문제다. 처음에는 11053번처럼 dp로 접근하려고 했지만 입력 데이터의 수가 너무 많아 dp로 해결할 수 없는 문제임을 깨달았다. dp를 이용하려면 전체 리스트(배열)에서 i번째와 i-1번째까지의 데이터를 중복해서 탐색해 O(N^2)의 시간 복잡도를 가지게 된다. 11053번의 경우 입력 데이터의 개수가 1000개 까지라 시간 초과에 걸리지 않지만 12015번의 경우 입력 데이터가 훨씬 많아 O(N^2)의 시간복잡도를 가진 알고리즘을 사용할 경우 시간 초과가 발생한다. 따라서 O(NlogN)의 시간 복잡도로 해결해야 하고 이를 위해 i-1번째까지의 데이터를 이진탐색을 통해 시간을 단축해줘야 했다. 사실 위 부분까지는 이해가 되는 부분이나, 아래 부터 나오게..

처음 이 문제를 봤을 때에는 dfs를 이용해 해결하려고 했으나, 최솟값을 구해주기 위해선 백트래킹 알고리즘을 생각해줘야 했는데 이 부분이 어려워 bfs를 이용해 해결했다. bfs는 큐를 이용해 문제를 해결하는데, 기초적인 이론으로 bfs를 설명하면 보통 그래프를 이용해 설명한다.(bfs알고리즘 포스팅 링크 첨부 예정) 이 문제는 x, y좌표를 이용한 이중 배열(리스트)를 이용하여 해결하는 문제였기 때문에 bfs 알고리즘을 실제로 코드에 녹여내기가 조금 어려웠다. 이런 문제처럼 x, y좌표를 통해 이중 배열(리스트)로 나타내는 모양을 이용하는 문제 유형이 대표적이니 반드시 익숙해져야 겠다고 느꼈다. 백준 예제 2번을 이용해 설명하겠다. 처음에 주어진 그래프가 있고 빈 큐를 선언했다. 처음 시작 부분의 좌표..

최장 공통 부분 수열이라고 부르는 알고리즘이다. 영어로 LCS(Longest Common Subsequence) 라고 하는데, 최장 공통 부분 문자열도 LCS라고 부르는 모양이다. 둘의 차이점은 공통 부분이 연속하느냐, 마느냐인 것 같다. 이 부분에 대해서는 나중에 후자인 LCS를 공부할 때 다시 수정할 계획이다. 백준 9252번을 풀기 위해 필요한 알고리즘인데, 아주 클래식한 알고리즘이기도 하니 필수적으로 알고 있어야 한다. https://www.acmicpc.net/problem/9252 LCS 알고리즘을 풀기 위해서는 검사할 두 문자열의 앞에 공백 문자열(혹은 더미 문자열)을 하나씩 붙여주어야 한다. 검사할 문자열이 ACAYKP, CAPCAK라고 하자. (백준 9252번의 테스트 케이스이다.) 위 ..

# 퇴사 https://www.acmicpc.net/problem/14501 time_cost = list() price_earn = list() max_val = 0 N = int(input()) dp = [0 for i in range(N+1)] for _ in range(N): T, P = map(int, input().split()) time_cost.append(T) price_earn.append(P) # dp[i] = i일부터 마지막까지 상담 시 얻을 수 있는 최대 이득 # dp[i] = p[i] + dp[i+t[i]] # N일부터 1일까지 거꾸로 계산 for i in range(N-1, -1, -1): temp = i + time_cost[i] if temp

N = int(input()) array = list(map(int, input().split())) dp = [1 for i in range(N)] temp_list = list() for i in range(N): for j in range(i): if array[i] > array[j]: temp_list.append(dp[j]+1) temp = max(temp_list) dp[i] = temp temp_list.clear() print(max(dp)) for i in range(N): for j in range(i): if array[i] > array[j] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 print(max(dp)) 두 코드 모두 맞는 코드이고 동일하게 아..

from itertools import combinations N, M = map(int, input().split()) graph = list() distance_list = list() result_list = list() result = list() min_val = 0 temp_list = list() for _ in range(N): graph.append(list(map(int, input().split()))) # 치킨집 좌표 구하기 chk_list = list() for i in range(N): for j in range(N): if graph[i][j] == 2: chk_list.append((i, j)) # 치킨집 좌표 M개 조합 구하기 cPositions = list(combinat..