MY MEMO

이문제는 혼자 못풀었다...정말 어려웠다..DFS로 풀면 되겠지 했는데..대체 어디서 visit를 풀어줘야되고 어디서 안풀어줘야되고를 몰랐다 근데 이게 웬걸.. http://blog.eairship.kr/268 깔끔하게 정리해놓은 DFS의 이론 아래에 이것과 비슷한 문제가 있었다단지 이 사이트의 문제는 시작과 끝점이 정해져있고 minimum을 찾는것이고 그리고 문제해결기법의 문제는 시작점만 있고 maximum을 찾는 것이다. 그렇다면!!! 그 두개의 조건만을 변경해주면 되는 것이다. 아 잡힐듯 말듯해서 풀지 못했는데 이렇게 쉽게 풀리다니이제 정신 똑디 잡고 문제 풀어야겠다 이 문제의 내가 헷갈린 가장 큰 visit라는 부분은map을 변경하여 간단하게 해결되었다 어짜피 1인 부분은 visited로 설정해줬..

#include #include #include #include #include #include using namespace std; int number_count; string number; vector big; int DP(int rest, int index) { if (number_count > for_count; while (for_count--) { fcin >> number_count >> number >> difference; DP(difference, 0); for (int j = 0; j < number_count; j++) fcout

#include #include #include using namespace std; int sum_sub; vectormain_cache = vector(10001, vector(10001, 0)); //cache : x => 그룹을 지을 노드의 수, y => 나눠야하는 그룹의 개수 //group_count : 나눠야하는 그룹의 개수 //pre_node_count : 그룹을 지을 노드의 수 //pre_group : 현재 나눈 그룹의 수 int main_tree(int group_count, int pre_node_count, int pre_group) { // 현재 노드가 0이고 모든 그룹을 짝지었다면 (모든 그룹을 짝지은후 한번더 DP를 돌림) 현재 그룹이 모든 그룹의 수보다 크다 // 그렇다면 1개..

정답 코드 이 문제는 최소 스패닝 트리로 푸는 문제이다.최소 스패닝 트리를 간단히 설명하자면1. 최소 거리를 순서대로 저장해 놓는다2. 만약 그 거리를 연결했을 때 사이클이 돈다면 설정하지 않는다3. 사이클이 돌지 않는다면 연결시키고 결과 값에 더해준다. #include #include #include #include #include using namespace std; #define PAIR pair vector parent; int find(int index) { if (index == parent[index]) return index; else return parent[index] = find(parent[index]); } int Union(int start, int end) { start = f..

start_end 배열은 prodo가 있는 곳부터 시작해서 종료 까지 막대 경로를 저장해 놓은 것이다end_start 배열은 ring이 있는 곳부터 시작해서 종료까지 가는 막대 경로를 저장해 놓은 것이다. 경로는 어떻게 찾냐면 한 막대에 갈수 있는 방향은 오른쪽과 왼쪽이다그렇다면 자신의 막대에 -1을 한 곳에 막대가 있다면 왼쪽으로 이동즉 자신의 막대 -1자신의 막대에 +1을 한 곳에 막대가 있다면 오른쪽으로 이동즉 자신의 막대 +1 만약 start_end의 레벨이 n이라면 end_start배열의 레벨이 n+1일때두개의 차이가 1이면 가능하다 (단 하나의 stick만 놓아서 되야 하므로) #include #include #include using namespace std; int main() { int ..

풀이방법은... 결국 카드가 움직이는 곳은 규칙이 있게 된다. 먼저 그 규칙을 모두 저장하고 돌리면 매우 느려지니 구하면서 저장하고 반복된다면 저장한 것으로 돌린다. board를 sorting하여 binary search를 이용하였고 시간을 줄일 수 있었다. #include #include #include #include #include #include using namespace std; #define PAIR pair vector A_card, B_card; vector A_multiple_card, B_multiple_card, board; int binary_search(int front, int rear, int result) { while (front + 1 < rear) { int mid =..

#include #include #include #include #include #include using namespace std; #define MAKE_INDEX(num1,num2) num2 > person_count ? num1 = 1 : num1 = num2 ofstream fcout; vector person_card; int person_count; /* 이 문제의 관건은 1) 게임을 코드로 구현하는 것과 2) 처음 입력할때 같은 수가 들어오면 삭제해주고 시작한다는 것이다 아니면 탁구처럼 계속 돈다. -> 무한루프발생 */ int play_game() { int before_index = 1, present_index = 1, delete_index; while (1) { //b의 카드를 a..

DP를 이용하면 된다!! -> 동적 계획법 보통 동적계획법을 사용할 때에는 모든 경우의 수를 다 돌아야할 때이다. 동적 계획법을 사용시 시간을 줄이려면 cache를 이용하여 결과값을 저장하여 놓는 것이 좋다. 이미 돌았던 경우의 수라면 반복해서 경우의 수를 구할 필요없이, 바로 값을 return해주면 된다. 따라서 보통 이중배열을 사용하여 cache를 만들고 저장한다. 이 문제는 나에게 매우 어려웠던 문제이다. 각 숫자마다 가지고 있는 카드의 수도 제한되어 있고, 모든 경우의 수도 돌아야하기 때문이다. 무엇보다 무엇을 이중배열의 두개의 변수를 무엇으로 정해야할지 몰라서 많은 고민을 했다. http://yejin0730.tistory.com/ 이 친구의 도움을 받았다!!! 알고리즘이 복잡하기에 길게 설명해..

프로그램의 시작 시간과 끝시간을 준다. (시간&분으로 주지 않고 분으로 합쳐서 준다) 중간에 광고가 있을 수도 있고 없을 수도 있다. ("전 프로그램의 끝시간과 이후 프로그램의 시작시간이 똑같지 않아도 된다"는 의미이다.) 최대 끝시간은 1000분이다. (0 만약 시작시간이 이전에 끝났던 시간보다 앞선다면 스케쥴표에 넣을 수 없다. while (!time_list.empty()) { int start_time = time_list.top().second, end_time = time_list.top().first; //queue에 남아있는 끝나는 시간 스케쥴중 가장 빠른걸 가지고 나온다. time_list.pop(); if (before_end_time > start_time) continue; //만약..

algospot ORDERING : https://algospot.com/judge/problem/read/ORDERING priority_queue로 풀었어야 했는데 queue로 풀어서30분도 안걸려 풀 문제를 1시간에 걸쳐 돌아왔다코드는 매우 간단하다 #include #include #include #include #include #include using namespace std; vector graph; vector indegree; priority_queue memory; void main_function() { for (int j = 0; j < indegree.size(); j++) { if (indegree[j] == 0) memory.push(j); } while (!memory.empt..