Doby's Lab

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이번 문제는 계속 시간 초과가 나서 계속 뜯어고칠수록 코드를 점진적으로 진화시키는 기분이 들었다. 이번 문제의 키워드는 '사이클의 유무 판단'이다. 첫 시도 첫 시도에서는 각 노드마다 for문을 통해 '이 노드는 사이클을 형성하는가?'의 여부를 따졌었다. 그 여부는 백트래킹을 통해 두 개의 인자를 받아들여 코드를 짰다. 하지만, 노드의 최대 개수 100,000개가 주어지고, 100,000개 전체가 하나..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음 문제를 봤을 때는 행과 열이 둘 다 100,001인 bool 2차원 배열을 선언해서 두 노드가 주어지면 간선을 1로 바꿔주어서 각 행을 DFS를 돌리면 될 거라고 생각했다. 하지만, 이럴 경우 배열의 크기가 너무 커서 오류가 나게 된다. 여기서 알아냈던 게 vector의 2차원 동적 기능(?)이었다. 기존 1차원 vector배열에서 push_back을 이용하는 것은 늘 사용했지만 2차원에서 사용할 방법은 생각도 못 해봤다. 각 행에 push가 가능하다는 ..

이번 문제는 꽤나 어려웠다. 어려웠던 포인트들을 정리해보면 1. DFS로 풀어야 할지 BFS로 풀어야 할지를 아직 헷갈린다. 2. DFS로 풀어야 할 땐 동작원리를 알고 있어도 어떠한 논리로 접근해야 하는지 모르겠다. 이번 문제는 BFS로 첫 시도를 했었다. 높이가 낮아지다가 다시 높아지는 시점을 두고 이를 경계선이라고 생각하며 구역을 나누어 각 구역을 산봉우리로 취급하려 했었다. 하지만, 이를 표현하는 데에 있어서 산 중턱에서 BFS가 돼버리면 구하려는 구역 이상의 수가 도출되기 때문에 다음 코드로는 답을 도출해낼 수 없었다. 그래서, flag 변수나 min값을 도입해 봤지만 풀리지 않았다. #include #include #include using namespace std; int n, m; int ..

이번 문제는 BFS로 풀려고 했다. [당시 썼던 BFS 코드] void bfs(int row, int col) { queue q; q.push(make_pair(row, col)); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int i = 0; i = 1 && dy = 1 && dx > 앞 길에 'A'가 있는데 1, 1에서 출발한 길에선 아직 'A'가 나오지 않아서 가야 하지만 다른 길에서 이미 'A'가 나와서 가지 못하는 것으로 판단하는 것을 말한다. [DFS를 사용한 이유] ..