728x90 [알고리즘 개념정리] 4. 그리디 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 그리디 알고리즘 : 부분적인 최적 전략을 반복적으로 취하는 알고리즘 당장 보이는 이득을 좇아가는 것도 이 알고리즘의 일부! ★ 그리디 문제 판별법 부분적인 최적 전략을 반복적으로 취해서 답을 구할 수 있는 문제 부분 문제에 대해 구한 최적해들이 모두 전체 문제의 최적해의 일부인 문제 ★ 그리디 문제 접근법 문제의 상황이 그리디 알고리즘에 적합한지 살펴본다. 어떤 기준으로 순서를 세워, 그 순서대로 처리하면 이득이 되는지 생각해본다. 직관 혹은 증명을 통해 어떤 기준이 확실하다면 구현한다. -> 만약, 그 기준이 보이지 않는다면 DP 등 다른 풀이를 생각해보자. 그리디 문제 유형은 크게 다음과 같이 나누어.. 2022. 1. 22. [백준/C++] 9251번: LCS(G5) 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 사용한 알고리즘 2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP) 풀이 두 문자열을 각각 s1, s2라고 하자. dp[i][j] 에는 s1의 i까지, s2의 j까지 문자들의 LCS길이를 담았다. dp A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C .. 2022. 1. 21. [백준/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. 이전 1 ··· 7 8 9 10 11 12 13 다음 728x90
