알고리즘/백준 & swacademy108 BOJ 1948 - 임계경로 (위상정렬) https://www.acmicpc.net/problem/1948 작업 https://suuntree.tistory.com/119문제의 응용 DAG(무사이클방향그래프)임이 보장됨. 시작점 ~ 도착점까지 최장거리를 구하고, 그 경로를 모두 칠했을 때 칠해진 간선의 수를 구하는 문제. 최장거리를 구하고 d배열 초기화 하는 것은 '작업' 문제와 동일함. 경로를 칠하는 것은 역방향 으로 정점을 순회하면서 d[next] = d[curr]+ weight(curr~next) 인 경우만 dfs로 따라가 주면 된다. 위 그림은 예제를 그대로 그린 것이다. 최장 경로는 12이므로, (7,2) 간선은 포함되지 않는다. 유의할 점은 이미 방문된 정점을 재 방문 하는 경우가 생긴다는 것이다. 위 예제에서 (7,2) 간선도 유효.. 2020. 1. 4. BOJ 2056 - 작업 (위상정렬) https://www.acmicpc.net/problem/2056 오랜만에 그래프문제 최대 10000개 작업들의 순서와 각 작업을 수행하는 데 걸리는 시간이 주어질 때 모든 작업이 끝나는데 걸리는 시간을 구해라. 예제의 상황을 그래프로 그리면 다음과 같다. 5번 작업을 수행하기 위해선 2번과 4번 작업이 모두 끝나야 한다. 1. i번까지 작업을 완료하는데 걸리는 시간을 d[i]라고 하고, 처음에 0으로 초기화 한다. 2. ind[i] == 0 인 정점들만 작업하는데 걸리는 시간으로 d를 초기화 한다. 3. 위상정렬된 순서대로 정점들을 방문하면서 d[next] = max(d[next], d[curr]+work[next])로 초기화해준다. 4. 위상정렬 후 d[i]중 최대값을 출력한다. #include #i.. 2020. 1. 4. BOJ 2228 - 구간나누기 (dp) https://www.acmicpc.net/problem/2228 최대 100자의 숫자배열을 입력 받았을 때 연속된 수열을 총 m개 뽑을 때 그 뽑힌 숫자들의 최대값을 구하는 문제. **dp값을 처음 초기화 할 때 특정 값으로 초기화 하기가 애매하다. 숫자가 음수일 수 있기 때문. 따라서 bool타입 c[101][51]을 사용해서 지금 상태가 이미 메모된 상태인지 기록해둔다. (psum 사용하므로 1-base ) f(i, j) : 1 ~ i 번째 숫자를 사용하여 j개의 연속된 수열을 뽑을 때 뽑힌 숫자들의 최댓값 f(i, j) = max(i번째 숫자를 뽑지 않을 때, i번째 숫자를 뽑을 때) 1. i번째 숫자를 뽑지 않는 경우 f(i,j) = f(i-1, j) 2. k번째 ~ i번째 숫자를 뽑는 경우 f.. 2019. 12. 29. BOJ 11049 - 행렬 곱셈 순서 (dp) https://www.acmicpc.net/problem/11049 파일 합치기와 매우 유사함 최대 500개의 행렬 정보가 n*m 형태로 입력될 때, 이들은 순서대로 곱할 수 있음이 보장된다. 모든 행렬을 곱할 때 곱셈 연산의 최소횟수를 구하는 문제. f(i, j) : i~j번째 행렬을 곱할 때 곱셈 연산의 최소 횟수 f(i, j) = f(i,k) + f(k+1,j) + a[i].f * a[k+1].f * a[j].s ( i > a[i].first >> a[i].second; memset(dp, -1, sizeof(dp)); cout 2019. 12. 29. 이전 1 ··· 13 14 15 16 17 18 19 ··· 27 다음
