본문 바로가기

BOJ67

[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.
[BOJ] 백준 17367번: 공교육 도박 https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 � www.acmicpc.net 주사위를 N번을 던져서 나온 최근 3개의 값으로 상금의 기대값을 구하는 문제입니다. 앞에서 몇번을 던져서 뭐가 나오든 신경을 쓸 필요없이 최근 3개의 눈을 기반으로 던질 수 있는 경우를 고려하면 쉽게 풀 수 있습니다. 만약 최근 3개가 5 3 4의 눈이 나왔다면, 현재 상금과 한번 더 던졌을때 다음에 올 눈 1~6에서의 기대값을 계속 구해가면서 더이상 던질 수 없을때 까지 반복하면 됩니다. #in.. 2020. 7. 23.

티스토리툴바