본문 바로가기

자바8

12969번 - ABC(bfs, dp) 문제: 풀이:문자열 ABC의 유효한 쌍은 'AB', 'AC', 'BC'이다.A만 입력시에는 유효한 쌍이 없고,AB까지 입력시에는 유효한 쌍이 ABABC까지 입력시에는 유효한 쌍에 AC, BC가 추가된다.위 예시를 통해 알 수 있는 것은 아래와 같다.A 입력시 고려할 것은 없다B 입력시 앞에 있는 A의 수만 고려하면 된다.C 입력시 앞에 있는 A, B의 수를 고려해야 한다.C를 문자열의 앞 부분에 추가할 때 고려해야 할 것은 없다.즉, A의 수, B의 수, C의 수, 유효한 쌍의 수 4개를 기록해 놓으면, 다음 문자를 추가할 때 계산을 편하게 할 수 있다.계산 과정은 아래와 같다.기록한 정보를 꺼내온다.유효한 쌍의 수가 K와 같다면, "C * (N - (A + B + C의 수) ) + 만들어진 문자"를 출.. 2024. 9. 13.
10942번 - 팰린드롬?(dp, br, st) 문제: 풀이:먼저, 팰린드롬이 뭔지 알아야한다.(1, 2, 1), (a, b, c, b, a), (가, 나, 다, 나, 가) 등 대칭되는 문자들의 모음을 팰린드롬이라고 한다.문제에서 알려주지않아 햇갈릴 수도 있지만, (1, 1), (1, 2, 2, 1)도 팰린드롬이며, 문자의 수가 짝수든 홀수든 상관 없다. 자 그럼 문제에서 준 보기를 이용해 문제를 풀어보자.1213121이렇게 배열이 주어졌다.먼저 보기에서 설명하듯 숫자가 1개 있을 때는 모두 팰린드롬이다. 1(1)2(2)3(1)4(3)5(1)6(2)7(1)길이: 111221133112211팰린드롬?ppppppp숫자가 두개 있을 때는 앞 뒤만 비교하고 같은 수라면 팰린드롬이다. 1(1)2(2)3(1)4(3)5(1)6(2)7(1)길이: 1112211331.. 2024. 9. 12.
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.
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.

티스토리툴바