알고리즘/백준 썸네일형 리스트형 [1010]다리 놓기(C++)/DP 1. 문제 2. 접근 방식 1) DP 1) 항상 n개의 다리를 만들어야 한다. 1번째 다리의 동쪽 사이트 번호는 1이상 (M - N + 1 )이하 n번째 다리의 동쪽 사이트 번호는 N이상 M이하 i번째 다리의 동쪽 사이트 번호는 i 이상 (M - N + i ) 이하 2) (i번째 다리의 동쪽 사이트 번호) > (i-1번째 다리의 동쪽 사이트 번호) 3) 1과 2를 합쳐보면 i번째 다리를 만들 때 고려해야 하는 것 :"i-1번째 다리를 만들 때 몇 번 사이트를 선택했는가"임을 알 수 있다. 직전에 몇 번 사이트를 선택했는지를 알면 내가 현재 선택할 수 있는 다리의 개수를 알 수 있기 때문이다. 따라서 "현재 나는 몇 개의 다리 중 하나를 고를 수 있는가" = "직전에 몇 번 사이트를 선택했는가" 로 이해할.. 더보기 [1932] 정수 삼각형(C++)/DP 1. 문제 2. 접근 방식 1) nth level에는 n개의 노드가 있다. 2) n level의 i번째노드는 n+1 level의 i번째 노드와 i+1번째 노드만 접근할 수 있다. 3) dp[n][n]구현 : dp[i][j]: i번째 레벨의 j번째 노드를 선택했을 때 얻을 수 있는 최대 비용 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + (i level의 j번째 노드의 값) 4) dp 함수 구현 4-1) bottom-up 방식 : 이중 for문으로 dp[1][1]부터 구하기 시작해서 dp[n][n]까지 구함. 리턴 값은 dp[n][1]~dp[n][n]값들 중 max값 4-2) top-down 방식: 재귀 함수로 구현. 종료 조건( n==0일 때, 이미 dp배열에 값이 이미 저.. 더보기 [백준] 정렬 > 1. sort(begin,end) 1) array 정렬 : sort(a,a+n);//a[0] ~a[n-1]까지 정렬 2) vector 정렬: sort(a.begin(),a.end()); 2. compare함수 1) sort함수의 3번째 인자로 함수 이름을 넘김 2) const, & 붙일 것 3.stable sorting(안정 정렬) 1) 같은 것이 있는 경우, 정렬하기 전 순서가 유지되는 정렬 알고리즘 2) merge sort(NlogN),bubble sort(N^2) 혹은 stable_sort STL 으로 구현 가능 3) 예제(나이순 정렬) -가입자들의 나이와 이름이 가입한 순서대로 주어질 때, 나이 순으로 정렬(나이가 같으면 먼저 가입한 사람이 오게 정렬) -유의: 가입한 순서는 입력으로 들어오지.. 더보기 이전 1 2 3 다음
