Outgoing Introvert

○ 다이나믹 프로그래밍, 누적 합 Silver1 백준 11660번 구간 합 구하기 5 시간은 한시간 넘게 걸린거같은데 한번만에 통과함 ㅎㅎ 어떻게 계산해야될지 방법을 찾기만 하면 구현이 어렵진 않았음. 생각해내는건 쉽지않았음 ㅎㅎ (뻔한 말인가,,?) 누적 합과 DP의 경계가 살짝 모호하지만 행렬을 사용하니깐 공간에 값을 저장해나가는 게 누적합을 사용한 DP에 좀 더 가까운 것 같다는 느낌? //85696KB 584ms let nm = readLine()!.split(separator: " ").compactMap { Int($0) } let n = nm[0] let m = nm[1] var matrix: [[Int]] = [Array(repeating: 0, count: n+1)] for _ in 0..

DP가 왜 필요? DP의 장점? DP 문제 어떻게 알아보고 접근할지 1. 다이나믹 프로그래밍의 목적 DP 는 완전 탐색, DFS, BFS 와 같이 수많은 경우의 수를 전부 따져봐야 하는데, 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고 수행시간을 단축하고자 만들어진 알고리즘. DP가 없던 시절에는 최단 경로를 찾거나, 최고 점수를 만들거나 하는 문제를 풀기 위해 모든 조합을 다 만들어 보는 수밖에 없었음. DP 알고리즘이 만들어진 후에는 수행시간을 현저하게 줄일 수 있었다. 예시) 프로그래머스 - 정수 삼각형 (Swift는 지원 안됌..ㅠ) => 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여 수행 속도를 개선한다. 메모리를 사용한다 : 배열 혹은 자료구조를 만든다. 중복 연산을 줄인..