궤도

문제 풀이 개인적인 비하인드 때문에 나혼자 140만원 문제라고 부르는 회의실 배정 문제이다. 이 문제에서 중요한 것은 시작하는 시각일까 끝나는 시각일까? 당연히 끝나는 시각이다. 0시에 시작해서 12시에 끝나는 것보다야 3시에 시작해서 4시에 끝나는게 회의실을 좀 더 효율적으로 사용할 수 있는 방법일 것이다. 그렇다면 끝나는 시각이 작은 순서로 정렬한다고 치고 같은 때에 끝나는 회의가 2개 이상 있다면 어떤 회의를 우선으로 해야할까? 끝나는 시각이 같고, 시작하는 시각이 다른 다음과 같은 회의 A, B가 있다. 회의 A를 먼저 투입했을땐, 회의 A가 끝난 뒤 회의 B를 진행할 수 있다. 회의 B를 먼저 투입했을땐, 회의 B가 끝난 뒤에 회의 A를 진행할 수 없다. 이미 4시인데 2시부터 해야했을 회의 A..

문제 풀이 거스름돈 문제는 여러가지가 있지만 이 문제처럼 특수한 경우에는 그리디 알고리즘을 적용할 수 있다. 그 특수한 경우가 무엇일까? 바로 모든 동전들의 가치가 배수관계일 때이다. 만약 가치가 1, 7, 10원인 동전 3개가 있고 14원을 거슬러 줘야 한다고 하자. 그리디 알고리즘을 적용하면 10원 1개, 1원 4개 총 5개의 동전을 사용하지만 최적해는 7원 2개 총 2개의 동전을 사용하는 것이다. 아무튼 이 문제는 모든 동전들의 가치가 배수관계이니 맘편하게 그리디 알고리즘을 적용하자. 가장 가치가 큰 동전부터 가치가 작은 동전 순서로 거스름돈과 비교하면 된다. 소스코드 #include using namespace std; int coin[11]; int greedyCoin(int N, int K) ..

문제 풀이 여러가지 풀이방법으로 풀 수 있는 냅색 문제이다. 이번엔 동적계획법으로 풀어야 한다. 특정 물건 i가 있다고 하자. 이 i에 대해 할 수 있는 것은 2가지이다. 배낭에 넣거나, 배낭에 넣지 않거나. 무조건 넣을 수 있는 것도 아니다. 버틸 수 있는 무게가 5인데 6짜리 물건은 넣을 수 없다. 그럼 어차피 못넣는 경우는 빼고, 넣을 수 있는 경우 이 물건을 넣어야 할까 말아야 할까? 1~N까지의 물건(i)과 1~K까지의 무게(j)가 있다고 하고 이걸 dp[i][j]라는 배열에 저장한다고 하자. 그니까 dp[2][4]라면 나에게 2개의 물건이 있고 4만큼의 무게를 들 수 있는 상황이라는 것이다. dp[i][j]에 대해 물건을 넣지 않을 경우 dp[i][j] = dp[i-1][j]이다. 물건을 넣지..

문제 풀이 이것도 유명한 동적계획법 문제인데... 그냥 뭐 간단하게 생각해서 이런 수열이 있다고 하자 5, -8, 9, -1, ... 당연히 처음은 0으로 시작할 것이다. 0+5를 해서 5가 나왔고 다음 숫자를 보니 -8이다. 5+(-8) = -3인데, 우리가 0으로 시작했다는 걸 생각하면 굳이 이 -3을 안고갈 이유는 없다. 그래서 여기서 연결을 끊고 다시 0부터 시작한다. 0+9를 해서 9가 나왔고, 그 다음이 -1이지만 9에서 -1을 더해도 8이고, 뭐 그 뒤에 10이 나올 수도 있는거니까 연결을 끊지않고 계속 이어나간다. 간단히 말하자면 연속합이 음수가 되는순간 연결을 끊고 다시 시작하는 것이다. 다만 모든 입력이 음수인 경우가 있을 수 있다. 코드를 작성할 때 이 부분을 잊지 말아야 한다. 소스..

문제 풀이 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...