Algorithm (14) 썸네일형 리스트형 [백준] 1043번 거짓말 1. Approach (1) 재귀 + Union Find 알고리즘 으로 접근한다. 2. DP[N][M] : n 명의 사람이 m개의 파티를 참가할 때 지민이가 최대한 과장되게 이야기를 할 수 있는 파티 개수의 최댓값. ( 이 문제에서 시간이 충분해서 DP는 큰 의미가 없다 ) -> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용 (3) 풀이 방법 해결 방법 : #UnionFind 알고리즘을 사용한다. ( #서로소집합 ) (1) 진실을 알고있는 사람들과 같은 파티에 참가한 사람들을 모두 그래프로 잇는다. (2) 그래프가 이어진 사람들에게는 지민이가 과장된 이야기 ( 거짓말 )를 할 수가 없다. (3) 그래프가 이어진 사람들을 알고있는 사람들이라고 전부 생각하고 조건을 .. [백준] 2662번 기업투자 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 1만원 단위로 최대 N ( = 300 )까지의 액수를 최대 M ( = 20) 개의 회사를 선택해야기 때문이다. 300.C.20 -> 시간 초과 (2) DP 배열 정의 -> DP[N][M] : M 기업에 N 금액의 투자를 했을 경우 얻을 수 있는 최대 이익금 (3) 풀이 방법 -> investment[현재 보유하고 있는 금액][투자금액]으로 해결할 수 있다. 최대 이익금을 얻었을 때 각 기업에 얼마룰 투자했을 때 얻을 수 있는지 그 상태를 출력해야하는 부분을 신경써야한다. 자세한 내용은 아래 소스 코드 주석을 참고하자. 2. Source Code #include #include #include #include #define MAXC.. [백준] 1563번 개근상 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 브루트포스로 문제 풀이를 생각해보면 시간 초과가 나기 때문에 메모이제이션을 이용해서 풀이해보도록 한다. N이 1000이고 지각 2번, 결석 3번에 대한 모든 조합을 생각해보면 서로 다른 알파벳 3개 중에 1번은 1000개 중복, 2번은 2개 중복, 3번은 3개 중복이므로 #중복조합 은 n.H.r={n+r-1).C.r -> 이가 된다. ( '.' 콤마는 순열, 조합 기호 표시를 가시적으로 잘 보여주기 위해 임의로 삽입 ) 서로 다른 (n + r - 1)개의 수 중, r개를 뽑는 경우의 수 )로 1002.C.2 가 되고 1000000 연산이 필요한데 n이 1 ~ 1000 에 따른 모든 수를 구하기 위해서는 시간 초과가 나게 됩니다.. [백준] 4883번 삼각 그래프 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 (100,00, 3) 의 그래프를 1초 ( 약, 1억번의 연산 ) 내에 전부 탐색하려면 메모이제이션이 반드시 필요하다. (2) DP 배열 정의 -> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용 (3) 풀이 방법 -> 아래 그래프와 같이 정점 -> 정점으로 가는 방향은 (아래, 오른쪽, 오른쪽 아래, 왼쪽 아래) 이므로 4가지 방향에 대해서 탐색을 한다. 그래프 범위 내에 있는 경우만 탐색하면된다. (4) 함정 -> 마지막으로 입력받는 0이 처음에 입력받는 수열 길이 N을 말하는 것 ( 무한루프 사용으로 해결 ) 2. Source Code #include #include #include #de.. [백준] 2565번 전깃줄 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 전봇대 A와 연결되어 있는 전깃줄에 대해서 정렬하고 LIS를 수행한다. (2) 풀이 방법 -> (1)번에서 설명한 방식대로 접근하면 쉽게 해결 가능하다. 2. Source Code #include #include #include using namespace std; int n; vector a;// first : A // second : B int dp[101]; int main() { int x, y;// x -> y cin >> n; for (int i = 1; i > x >> y; a.push_back(make_pair(x, y)); } // 정렬 수행 sort(a.begin(), a.end()); // LIS 수행 for (int.. [백준] 11053번 가장 긴 증가하는 부분 수열 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다. (2) DP 배열 정의 -> dp[i] 는 i 번째 인덱스 까지의 배열 중 가장 긴 부분수열의 길이. (3) 풀이 방법 -> 내부 for문을 1부터 j - 1 까지 돌리면서 a[j] dp[i] ( 현재 i 인덱스의 가장 긴 부분수열의 길이 보다 큰 경우에) 2. Source Code #include #include using namespace std; int n; int a[1001]; int dp[1001]; int main() { cin >> n; for (int i =.. [백준] 4963번 섬의 개수 문제 위치 : https://www.acmicpc.net/problem/4963 1. Approach (1) BFS 탐색으로 접근한다. -> 플러드필 알고리즘을 응용한다면 풀 수 있다. 그래프 이론, 영상 처리에서 많이 사용하는 알고리즘이기 때문에 짚고 넘어가는 것을 권장한다. - 아이디어는 시작 좌표부터 끝 좌표까지 조건에 충족하는 좌표에서 부터 BFS를 실행한다. - 방문한 곳들은 전부 check한다. - BFS를 한 번 실행시킬 때 마다 섬의 개수를 1 증가시킨다. 2. Source Code #include #include #include #define MAX 51 using namespace std; int map[MAX][MAX]; bool check[MAX][MAX]; int dx[] = { .. [백준] 2306번 유전자 문제 위치 : https://www.acmicpc.net/problem/2306 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다. (2) DP 배열 정의 -> DP[s][e] : start 부터 end 까지 KOI의 최대 길이 (3) 후기 1. 문자열의 특정 패턴, 조건 등으로 길이를 구할 때 사용할 수 있다. 2. Source Code #include #include #include #include #define MAX 500 #define START0 'a' #define END0 't' #define START1 'g' #define END1 'c' using namespace std; /* .. 이전 1 2 다음
