궤도

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이 문제의 응용 문제이다. 교차하지 않는다는 의미가 무엇을까? A의 원소 i, j가 있다고 하고 이 i, j가 향하는 B의 위치를 A[i], A[j]라고 하자. A의 모든 전깃줄에 대해 교차하지 않으려면 A에서 i> tot_line; for (int i = 1; i > elecs[i].source >> elecs[i].dest; sort(elecs..

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이 문제를 응용한 문제이다. 11053번이 왼쪽->오른쪽으로 탐색하며 수열의 길이를 구했다면 이번에는 i에 대해 왼쪽->오른쪽으로도 탐색하고 오른쪽->왼쪽으로도 탐색해야 한다. 소스코드 #include using namespace std; struct bi_arr { //l은 왼쪽부터 오름차순, r은 오른쪽부터 오름차순 int value, l_po..

문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수열의 길이도 3이라고 할 수 있겠다. 이때, 15가 들어오는 경우와 50이 들어오는 경우를 살펴보자. 15가 들어오는 경우 가장 오른쪽의 숫자인 30부터 비교를 시작한다. 왜 왼쪽부터가 아니라 오른쪽부터 비교하냐면 우리의 목적은 제일 긴 수열을 찾는 것이고, 가장 큰 수가 오른쪽에 저장됐을 것이다. 새로 들어오는 수가 이 수보다 크다면, 한 번에 수열의 길이를 하나 늘릴 수 있는 것이다. 아무튼 30과 비교하니 1530이란 것을 발견한다. 그렇다면 가장 긴 수열의 길이를 하나 늘릴 수 ..

문제 풀이 myunji.tistory.com/210?category=1154147 [백준] 2579번 : 계단 오르기 문제 풀이 동적계획법의 대표적인 문제 중 하나이다. 생각해보니 동적계획법은 대표하는 문제가 많은 것 같다...아무튼 이전까지의 문제들은 초기값을 받은 배열을 그대로 갱신하면서 값을 구 myunji.tistory.com 이 문제와 유사한 문제이다. 차이가 있다면 계단 오르기 문제에선 마지막 계단을 꼭 밟아야 했지만 여기선 마지막 포도주를 마실 필요가 없단 것이다. 위의 두 경우는 i번째 포도주를 마신 경우이고 마지막 경우는 i번째 포도주를 마시지 않은 경우이다. i번째 포도주를 마신 경우 1. i-1번째 포도주를 마시고 i-2번째 포도주는 마시지 않음. i-3번째 포도주에 대한 최댓값 2...

문제 풀이 n자리의 자연수가 있다고 하자. 우리는 왼쪽부터 오른쪽으로 값을 채워나가고 있고 i번째 자리의 값을 채우려 한다. i번째가 첫번째 자리, 그니까 가장 왼쪽에 위치한 자리만 아니라면 0~9까지 모든 수가 들어올 수 있다. i번째 자리에 0이 들어간다면 i-1번째 자리의 수는 1일 것이다. i번째 자리에 9가 들어간다면 i-1번째 자리의 수는 8일 것이다. i번째 자리에 k(1

문제 풀이 2와 3 모두로 나눌 수 있는 정수 i가 있을 때 이 정수 i를 1로 만드는 방법은 다음과 같다. 1. (정수 i/2를 1로 만드는 방법의 횟수) +1 2. (정수 i/3을 1로 만드는 방법의 횟수) +1 3. (정수 i-1을 1로 만드는 방법의 횟수) +1 이 중에서 가장 작은 값을 취하면 된다. 2또는 3으로 나누어 떨어지지 않는 수들은 조건을 적절히 빼주면 될 것이다. 소스코드 #include #include using namespace std; int min_arr[1000001] = { 0, }; int making_one(int num) { for (int i = 1; i N; cout

문제 풀이 동적계획법의 대표적인 문제 중 하나이다. 생각해보니 동적계획법은 대표하는 문제가 많은 것 같다...아무튼 이전까지의 문제들은 초기값을 받은 배열을 그대로 갱신하면서 값을 구했다. 하지만 이 문제는 그러면 안된다. i번째 계단을 밟는다고 생각하자. i번째 계단을 밟기 위해선 어떤 경로로 계단을 밟아야 했을까? i-3번째 계단을 밟고 i-1번째 계단을 밟은 뒤 i번째 계단을 밟거나(3번연속 계단을 밟을 수 없기 때문) i-2번째 계단을 밟고 i-1번째 계단을 건너뛰고 i번째 계단을 밟을 수 있을 것이다. 배열을 1개만 사용하면 안되는 이유가 이것이다. i번째의 계산을 할 때 i-1번째만 연속적으로 참조하던 지난 문제들과 달리 이건 불연속적으로? 지난 값들을 참고하기 때문에 초기 입력을 저장할 배열..

문제 풀이 이 문제도 동적계획법의 대표적인 문제 중 하나이다. 대표적인 풀이법에는 위에서 아래로 내려가는 방법과 아래에서 위로 올라가는 방법이 있는데, 후자가 훨씬 코드를 간단하게 짤 수 있다. i번째 줄을 계산한다고 하자. i번째 줄의 0번째(지금은 3)를 갱신하려면 i+1번째 줄의 0번째(7)와 더하거나 i+1번째 줄의 1번째(6)와 더하거나 이다. 둘 중 더 큰 값을 취하면 된다. 일반화하면 i번째 줄의 j번째 값을 갱신하려면 i+1번째 줄의 j번째 값과 i+1번째 줄의 j+1번째 값을 비교해 더 큰 값과 더하면 되는 것이다. 이를 n-1번째줄부터 1번째 줄까지 반복한 뒤 1번째 줄의 1번째 값을 리턴하면 된다. 소스코드 #include #include using namespace std; int ..