본문 바로가기
728x90
[백준/C++] 9177번: 단어 섞기(G4) 문제 https://www.acmicpc.net/problem/9177 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 www.acmicpc.net 사용한 알고리즘 2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP) 풀이 세 개의 단어를 각각 A, B, C라고 하자. dp[i][j] 에는 A의 i-1까지, B의 j-1까지 사용해서 C의 i+j-1까지 만들 수 있다면 1, 없다면 0을 담았다. 기저조건은 dp[0][0]=1이다. A="cat", B="tree", C="tcraete"인 경우를 생각.. 2022. 1. 21.
[백준/C++] 11049번: 행렬 곱셈 순서(G3) 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 사용한 알고리즘 2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP) 문제 이해 크기가 N×M인 행렬, 크기가 M×K인 행렬을 곱하면 크기가 N×K인 행렬이 되고 총 N×M×K번의 곱셈 연산이 필요하다. 행렬 여러 개를 곱할 때 필요한 곱셈 연산의 횟수는 행렬을 곱하는 순서에 따라 달라진다. 행렬의 곱 ABC를 구하는 경우를 생각해보자.. 2022. 1. 20.
[백준/C++] 11055번: 가장 큰 증가하는 부분 수열(S2) 문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 이 문제랑 굉장히 유사함 2022.01.19 - [PS/Baekjoon] - [백준/C++] 11053번: 가장 긴 증가하는 부분 수열(S2) 사용한 알고리즘 2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP) 풀이 배열 arr에는 수열 A를 저장하고, dp[i]에는 dp[i]로 끝나는 .. 2022. 1. 19.
[백준/C++] 11053번: 가장 긴 증가하는 부분 수열(S2) 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가하는 부분 수열을 Longest Increasing Sequence (LIS)라고 부른다. LIS문제를 DP로 풀면 O(N^2), lower_bound로 풀면 O(NlogN), segment tree로 풀면 O(NlogN) 이다. 이 문제는 1 ≤ N ≤ 1,000 이므로 DP를 이용해 풀어보려한다. .. 2022. 1. 19.
[백준/C++] 1932번: 정수 삼각형(S1) 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 사용한 알고리즘 2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP) 풀이 1. 크기 n*(n+1)/2인 num배열과 dp배열을 만들어준다. 2. num[idx]에는 각 수를 담고 dp[idx]에는 해당 위치까지 오는 경로 중 선택된 수의 합의 최댓값을 담을 것이다. 3. i(=level)과 j로 이중 for문을 돌면서 idx++을 해주어 원소 하나하나 접근한다. 4. i=1(맨 위)일 때는 dp[idx]=num[idx.. 2022. 1. 19.
[백준/C++] 10840번: 구간 성분(G1) 문제 https://www.acmicpc.net/problem/10840 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 1 ≤ N, M ≤ 1,500 이다. www.acmicpc.net 사용한 알고리즘 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash) -> Polynomial Rolling hash 이분 탐색 -> 참고 자료 : https://royhelen.tistory.com/36 풀이 X[26]배열에 27의 거듭제곱 수를 미리 담아둔다. (X[0]=1, X[1]=27, ... , X[2.. 2022. 1. 18.
728x90

티스토리툴바