개발 독학 일기

접근 방법 대표적인 배낭 문제로 물품을 하나씩 선택하여 각 무게별로 어떤게 최고의 선택인지 갱신한다풀이 이차원 배열을 선언하여 arr[선택한 물품][총 물품의 무게]로 만든다물품1부터 하나씩 선택하며 각각의 무게가 최대일때1. 이전물품까지의 가치를 그대로 가져올지2. 이전물품까지에서 현재 물품의 무게를 뺀 가치에 현재 물품의 가치를 더한 값둘중에 더 큰값을 저장하면 된다 따라서 점화식은 아래가 된다w = arr[i][0]v = arr[i][1]bag[i][j] = max(bag[i-1][j], bag[i-1][j-w] + v)정답 코드import sysinput = sys.stdin.readlinen, k = map(int, input().split())arr = []arr.append((0, 0))fo..

접근 방법 1. 잎 노드를 구한다2. 하나의 잎 노드에서 다른 잎 노드들까지의 길이를 dfs로 계산하여 최대값을 갱신시킨다풀이 잎 노드들을 구하는 과정은 루트 노트가 항상 1이므로1부터 bfs로 더이상 연결된 노드가 없는 노드를 잎 노드로 하여 찾았다. 이후 각 잎 노드들에 대해 dfs반복을 하여다른 잎 노드를 만났을때마다 최대 길이를 비교하여 갱신한다정답 코드import sysinput = sys.stdin.readlinen = int(input())graph = [[] for _ in range(n)]for i in range(n - 1): a, b, v = map(int, input().split()) graph[a - 1].append((b - 1, v)) graph[b - 1].append..

접근방법 N에서 K로 가는 최단 시간을 구하기 위해서는 N부터 n*2, n-1, n+1에 해당하는 모든점을 계속 접근해가며시간을 구해야한다고 생각했다.따라서 BFS를 이용했다풀이 크기가 200001인 배열을 만들고 N을 0으로 하여 점을 이동하면서 시간을 계속 갱신하였고모든 점을 돌았을때 K에 해당하는 시간을 출력하였다.BFS안에서 시간소요가 없는 x*2와 x-1, x+1은 분기하여 처리하였다계산한 시간이 더 빨라 값이 갱신되는 경우만 큐에 넣었다정답 코드import sysinput = sys.stdin.readlinen, k = map(int, input().split())INF = 200001line = [INF] * 200001def bfs(): q = [] q.append(n) line[n]..

접근 방법 이문제의 유형은 다이나믹 프로그래밍으로 어떤 작은 문제로 풀 수 있을지 찾아야한다두 문자열에 대한 선후관계는 없고 겹치는 문자를 찾는 것이 아닌, 길이만 출력하면 된다길이가 짧을 때의 LCS를 구하고, 길이가 길어질 때 전의 결과를 그대로 가져오거나 +1하면 된다풀이 두 문자열을 동등하게 비교하기 위해 이차원 배열을 만들고문자열을 앞에서부터 하나씩 비교한다문자가 다르면 arr[i-1][j]와 arr[i][j-1]중에 큰 값을 가져오고문자가 같으면 arr[i-1][j-1]+1을 하면된다정답 코드import sysinput = sys.stdin.readlinet1 = input().strip()t2 = input().strip()arr = [[0] * (len(t2) + 1) for _ in ra..

접근 방법플로이드 워셜 알고리즘을 몰랐기 때문에 다익스트라를 n번 사용하는 것으로 해결했다. 풀이보통 다익스트라 문제를 풀때는 dis나 visited 배열을 전역으로 선언하는데이번에는 n번 반복하면서 초기화 시켜야하기 때문에 함수안에서 선언하였다정답 코드import sysinput = sys.stdin.readlineINF = 10000000000n = int(input())m = int(input())line = [[] for j in range(n)]for i in range(m): p1, p2, t = map(int, input().split()) line[p1 - 1].append((p2 - 1, t))ans = []def min_dis(dis, visited): min = INF min_..

접근 방법 하나의 점에서 각 정점까지의 최단경로를 모두 구해야하기 때문에 다익스트라 알고리즘을 사용하였다.처음에는 모든 점까지의 거리를 최대로 설정해놓고, 하나씩 방문해가며 거리를 좁혀갔다.풀이 간선의 정보를 길이 v의 리스트를 만들어 각각의 u, v, w에 대해 아래와 같이 저장하였다.line = [[] for j in range(n)]for i in range(m): u, v, w = map(int, input().split()) line[u - 1].append((v - 1, w)) 각 정점을 방문 할때마다 가장 가까운 점을 알아내야 하므로 이부분을 따로 함수로 만들었다. 정답 코드import sysinput = sys.stdin.readlineINF = 100000000n, m = map(in..

접근 방법 단순히 숫자들을 이차원 배열로 받아 입력 케이스마다 합을 구하는 것은 시간이 많이 소요될 것이라 생각했고누적합을 이용하기로 했다.배열을 행을 기준으로 누적합으로 만들어놓고 케이스에 따라 뺄셈만 하여 합을 구한다풀이 행을 기준으로 x행은 원래 x행의 수와 x-1행의 수를 더해갔다 이후 각 케이스에 따라 각 열마다처음 시작 행이 1일 경우와 1이 아닌, 중간부터 합을 구하는 경우로 나누어 계산했다.if x1 == 1: sum += arr[x2 - 1][j]else: sum += arr[x2 - 1][j] - arr[x1 - 2][j]정답 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())arr = [[0 for i in..

접근 방법15654번과 유사한 문제지만 중복될 수 있다는 것만 다르다.따라서 15654번의 코드를 가져와 변형하였다.중복을 잡기 위해서는 답을 찾을 때마다 출력을 했던 이전 문제와는 다르게답을 모아놓고 중복을 거르는 작업이 필요하다고 생각했다.풀이set에 답을 모아놓고 오름차순 정렬을 위해 다시 리스트로 바꾸는 과정을 거쳤다.set에는 변경불가능한 형태만 원소로 가지므로 결국 리스트 -> 튜플 -> set -> 리스트 -> sort 순으로 해결했다.여기서 문제의 해인 ans를 단순히 set인 x에 넣기위해x.add(tuple(ans))이렇게 작성한다면 얕은복사 때문에 값이 계속 변경되어 엉망이 된다.따라서 깊은 복사를 위해 copy.deepcopy()를 사용하였다.정답 코드import sysimport ..

접근 방법퀸을 놓는 문제로 백트래킹의 대표적인 문제라고 한다.따라서 재귀적으로 각각의 칸에 접근하면서 퀸을 놓을 수 없으면 바로 빠져나오면 된다. 2차원적인 문제이므로 처음에는 visited 리스트를 2차원으로 만들어야하나 싶었는데길이N의 1차원 배열을 열로 생각하고 퀸을 놓는 자리의 행을 숫자로 입력하는 방식으로 풀이한다풀이기본적인 백트래킹 방식과의 차이는 직관적으로 이차원 배열을 만들지않는 것과퀸을 놓을 수 있는 위치인지 판별하는 함수이다.백트래킹의 조건이 단순하지 않기 때문에 따로 함수로 작성하여 true, false를 반환하도록 했다퀸은 아래와 같이 1)같은열에 있는지, 2)같은 행에 있거나, 대각선에 있는지 판단해야한다.#1)if row[x] == row[i]: return False#2) ..

접근 방법처음에 방법이 안 떠올라 알고리즘 분류를 봤고, 백트래킹이라는 것을 알았다.처음 들어보는 알고리즘에 검색을 해보았다백트래킹 : DFS를 사용하여 가능한 모든 경우를 탐색하는 과정순열이나 퍼즐 문제에 사용됨재귀 방식이나 반복문+스택으로 풀이이제 함수를 이용해 DFS방식으로 풀면 될 것 같다는 생각을 하게되었다.풀이처음 수들을 오름차순으로 정렬하고 앞에서 부터 하나씩 방문하여 깊이, 즉 수의 개수가 M과 같아지면 출력을 한다.재귀로 숫자를 하나씩 넣을때마다 깊이를 하나씩 증가시킨다.정답 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())arr = list(map(int, input().split()))arr.sort()ans..