본문 바로가기

Algorithm8

다이나믹 프로그래밍으로 최적화 하는 DFS, 백준 2253번 점프 백준 2253번 점프 문제는 N이 최대 10000까지 가능한 문제였습니다. 그냥 DFS를 활용해 모든 경우의 수로 점프를 하기에는, 돌담마다 JUMP += -1,0,1 의 세가지 경우가 주어지므로 모든 경우의 수를 찾기에는 지수승의 형태 뜁니다. 일반적인 BFS로 풀기에는 현재 도착한 돌담이, 최단의 점프로 도착했다는 보장은 되지만, 앞으로도 현재 돌담에서 가지고 있는 JUMP의 크기를 가지고 출발한것이 최단으로 목적지같이 도착한다는 보장이 없습니다. 그렇다면 BFS로 visit을 잡을 변수로는 JUMP크기와 돌담 위치를 함께 잡아 주어야합니다. 즉 JUMP크기를 1로 돌담3에 온 경우와 JUMP크기 3으로 돌담3에 온 경우는 구분해 주어야 합니다. 이번 문제는 약간의 변형으로 쉽게 BFS로 풀 수 있습.. 2020. 3. 28.
백준 1525번 퍼즐 BFS 최단,최소 문제. DFS는 힘든이유.. 퍼즐 문제는 메모리가 매우 적게 제한된 문제이다. 보통 최단문제의 경우 BFS로 접근하는게 일반적이지만, BFS의 경우 매 단계마다 가능한 경우의 수를 모두 queue에 저장해야되므로 상태를 저장해야되는 맵정보를 처음에 vector로한 결과 메모리가 초과되는 문제가 있었다. 그래서, 한번에 최대깊이까지만,,, 최대 메모리를 사용하고, 그 이상으로 메모리를 사용하지 않는 DFS로 접근을 시도했다. DFS의 경우, map정보를 전역 혹은, 매개변수를 포인터로 넘겨주고, return시에 다시 맵을 원상복귀 시켜주기만 한다면, DFS의 깊이와 상관없이 map 한개의 메모리양만 사용하게 설계할 수 있다. 하지만 이 문제는 기본적으로 DFS로 접근이 힘들다. 1. DFS특성상 최단문제에 적합하지 않다. 그 이유로는.. 2020. 3. 22.
c++ 표준입출력 가속 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 코드는 c++에서 cin, cout 객체의 표준 입출력을 가속합니다. 하지만 thread의 싱크가 unsafe 해지므로 예상하지 못한 순서의 입출력이 나올 수 있습니다. thread가 여러개인 환경에서는 위험하므로, 만약 현업에서 속도를 위해 사용한다면 printf, scanf,getchar등 c의 표준입출력 함수를 사용하길 바랍니다. 알고리즘 문제의 경우 싱글 스레드를 사용하기 때문에 위 코드를 그냥 써도 문제가 발생하지 않지만 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 코드 작성후 cin,cout 객체와 print.. 2020. 3. 19.
백준 16719번 ZOAC로 풀어보는 Brute force DFS 알고리즘 백준 16719번 문제가 만족하기 위해서는 문자열에 문자가 하나씩 추가될때, 최대한 가장 빠른문자가 나오고 그 다음 나오는 문자는 선행되어 나왔던 문자보다는 분명 느린 문자이므로, 최대한 뒤쪽에 나오는 것이 사전순으로 유리합니다. 이 과정을 brute force 무식하게 푸는 방법.. 순서대로 가능한 수를 나열하며 푸는 방식으로 풉니다. 이때 DFS가 활용되는 경우가 많은데 이번 문제에 꽤나 적합했다고 생각합니다. #include #include #include #include #include using namespace std; bool visit[100]; // 사전순으로 출력 // 조건1. 사전순으로 가장 빠른 문자가 먼저 출력되어야 한다. // 조건2. 선행된 dfs에서 출력된 문자가 나보다 사전.. 2020. 3. 18.

티스토리툴바