본문 바로가기

백준61

[BOJ] 백준 10217번: KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net M원 이하로 1번 도시에서 N번 도시까지 갈 수 있는 경로 중 최단시간을 요구하는 문제입니다. 두가지 방법이 있는데 저는 동적계획법으로 해결했습니다. DP[i][j] 배열을 i 도시에서 j원으로 출발할 때 n 도시까지 걸리는 최단 시간으로 정의했습니다. 주의할 점은 입력 중 출발공항과 도착공항이 같은 여러개의 티켓 정보가 들어올 수 있다는 점입니다. (이걸.. 2020. 8. 9.
[BOJ] 백준 1700번: 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 요즘 그리디에 너무 약해서 그리디 문제를 풀던 중 골머리를 앓았던 문제에 대하여 포스팅합니다. 이 문제는 각 전기용품의 사용 순서가 k개 주어지고 멀티탭이 n개 구멍이 있을때 주어진 전기용품을 순서대로 사용하면서 플러그를 뽑는 최소횟수 구해야 합니다. 가장 처음에 든 생각은 멀티탭을 모두 사용하고 있으며 다음 전기용품이 멀티탭에 꼽혀있지 않은 경우, 즉 플러그를 하나 뽑아야되는 시점에서, 꼽혀있는.. 2020. 8. 7.
[BOJ] 백준 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 행렬 곱셈 순서에 따라 연산량이 적어지는데 잘 생각해보면 (a b) (b c) 차원인 두 행렬을 곱할 때 a * b * c 의 연산횟수가 필요하다. 즉 가운데 b가 큰 순서대로 먼저 곱하는것이 횟수를 줄일 수 있다. 하지만 당장 b가 큰것을 줄이는 순서가 최종적으로 최적의 방법이 아닐 수 있기 때문에 구간 s~e 에서 모든 연산을 수행해봐야 한다. DP[s][e]를 s 번째 행렬과 .. 2020. 8. 6.
최장 공통 부분 수열 (LCS, Longest Common Subsequence) 과 역추적 최장 공통 부분 수열 (LCS, Longest Common Subsequence)문제는 잘알려진 Well-Known 알고리즘으로 간단한 규칙을 통해 구할 수 있습니다. A와 B 문장에서 LCS를 구하기 위한 배열 DP[i][j]는 A의 i번째 문자열과 B의 j번째 문자열까지 최대 LCS 길이라고 정의를 하고 DP 배열을 아래와 같이 초기화 합니다. 이제 2중 포문으로 A[i]와 B[j] 하나씩 비교하면서 DP 배열을 채워줘야합니다. 만약 A[i]와 B[j]가 같은 경우 DP[i][j]를 일단 LCS 길이를 1 늘려줍니다. 만약 A[i]와 B[j]가 다르다면 LCS 길이는 이전에 구한 LCS중 가장 큰 길이로 채워집니다. 만약 TSET의 첫 T와 TEST의 마지막 T가 만나는 경우를 살펴보겠습니다. 이 경.. 2020. 8. 6.

티스토리툴바