분류 전체보기 (33) 썸네일형 리스트형 [백준] 1103번 게임 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 무식하게(?) 4개의 방향으로 최대 250개의 좌표를 전부 방문하게 된다면, 재귀함수로 풀었을 경우에는 4250 이라는 천문학적 계산을 하게될 수가 있다. 300.C.20 -> 시간 초과 (2) DP 배열 정의 -> dp[x][y] : x, y 좌표부터 이동할 수 있는 최댓값을 메모이제이션 한다. 3. 제약 조건 (1) 범위 밖을 나가는 경우 (2) H에 빠지는 경우 4. 어려운 부분 (1) 헷갈릴 수 있는 곳으로 띄어쓰기가 안되어있는 숫자들과 char형을 받아서 처리하는 부분 -> string 배열로 받아서 처리 (2) 사이클이 발생하는 경우 무한 반복이 가능하므로 check을 해나가는 부분 -> 보통 예외 처리에서 .. [백준] 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.. [백준] 2342번 Dance Dance Revolution 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 전봇대 A와 연결되어 있는 전깃줄에 대해서 정렬하고 LIS를 수행한다. (2) DP 배열 정의 -> DP[idx][left][right] : idx 까지 발이 left, right 위치에 있는 경우 들어가는 비용의 최솟값 (3) 풀이 방법 -> 이동 조건에 따른 힘을 계산해주는 함수를 정의, 구현한다. 조건을 천천히 따라가면 충분히 쉽게 구현 가능하다. 조건이 충족하는 경우, 기저 사례를 구분해준다. 2. Source Code #include #include #include #include #define MAX 100001 using namespace std; int order[MAX]; // idx 까지 left, right의 발 위치.. [백준] 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 =.. 이전 1 2 3 4 5 다음
