본문 바로가기

알고리즘44

[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.
[UCPC] A번 전단지 돌리기, 백준 19542 https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net UCPC 본선 등록을 하지 못해서 본선이 끝난 뒤 공개된 문제를 풀어봤습니다. 트리를 탐색하면서 현재 노드에서 리프노드까지의 거리가 D이상인 자식노드로만 탐색하여 거리를 1씩 늘려 나가며, 왕복거리이기 때문에 거리에 2배를 해주시면 됩니다. #include #include #include #include #include #include #include using namespace std; typede.. 2020. 8. 6.

티스토리툴바