본문 바로가기

HWK블로그132

11049번 - 행렬곱셈순서(dp) 문제: 풀이:행렬곱셈부터 소개하자면 5x3 행렬과 3x2 행렬이 곱해지려면 5x3x2의 연산이 필요하며, 그 결과 5x2행렬이 만들어진다.같은 원리로 3x2행렬과 2x6 행렬이 곱해지려면 3x2x6의 연산이 필요하며, 그 결과 3x6행렬이 만들어진다. (5 3) (3 2) (2 6) (6 1) (1 4)의 행렬이 주어졌다고 예시를 들고 그 연산과 결과에 대해 설명하겠다.바로 옆에 붙은 행렬끼리의 연산 횟수부터 구해보겠다.행렬이 2개일때 최소 연산 횟수5 33 22 66 11 4연산 횟수5 x 3 x 23 x 2 x 62 x 6 x 16 x 1 x 4만들어진 행렬5 23 62 16 4기본적인 행렬 곱셈 방법의 결과 연산 횟수와 새로운 행렬이 나왔다. 이제 위 행렬을 이용해보자행렬이 3개일때 최소 연산 횟수.. 2024. 8. 29.
12869번 - 뮤탈리스크(bfs) 문제: 풀이:scv의 체력이 주어져 있고, 뮤탈의 공격 방식도 정해져있다.그렇다면, 모든 scv의 체력이 다 닳을때까지 뮤탈이 여러 방식으로 공격해보면 될 것이다.자, 가능한 모든 경우의 수로 한대씩 때려보자.위와 같은 결과가 나올 것이다.만약 그 다음에도 한번씩 때려보면 6 x 6의 경우의 수가 나올 것이고, scv가 모두 죽는 경우의 수에 도달할 것이다.위 그림을 보면, bfs를 사용하고 있다는 것을 알아볼 수 있을 것이다.중복이 일어나지 않도록 visited 배열을 만들어 코드를 작성하면 쉽게 풀 수 있을 것이다. 뮤탈의 공격 순번을 미리 저장해 놓는다.bfs를 위한 visited 배열은 3차원 배열로 저장해 놓을 것이다.int[][] attack = {{9, 3, 1}, {9, 1, 3}, .. 2024. 8. 27.
10422번- 괄호(dp, 카탈랑 수) 문제:'(' , ')'문자로만 이뤄진 문자열이 있다.길이가 L인 올바른 괄호 문자열을 구하여라.첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000) 각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오. 풀이:카탈란 수라는 개념을 코드로 작성하는 문제이다. 아래 블로그에 잘 설명이 되어있다.[알고리즘] 카탈란 수(Catalan number) (tistory.com)괄호를 직접 그리며 설명을 해보겠다.괄호의 수가능한 괄호 문자열0 2( )4( ) ( )(())6( ) ( ) ( ) (()) ( )( ) .. 2024. 8. 21.
2616번 - 소형기관차(dp) 문제: 풀이:각 소형 기관차가 끌 수 있는 객차 수를 3칸이라고 하자.객차의 수는 12개로 각 객차에 타있는 손님 수는 35, 40, 50, 10, 30, 45, 60, 20, 10, 50, 40, 70 이다.그렇다면 아래와 같은 전제를 도출할 수 있을 것이다.각 소형 기관차가 끌 수 있는 최대 인원은 연속되는 객차 3개의 인원의 합이다.고로 1~3번째 객차, 2~4번째 객차....10~12번째 객차만 고려하면 된다.두 소형 기관차가 끌 수 있는 최대 인원은 객차 6개의 인원의 합이다.고로 1~6번째 객차, 2~7번째 객차....7~12번째 객차만 고려하면 된다. 모든 소형 기관차가 끌 수 있는 최대 인원은 객차 9개의 합이다.고로 1~9번째 객차, 2~10번째 객차....4~12번째 객차만 고려하면 된.. 2024. 8. 19.

티스토리툴바