궤도

문제 풀이 할게 많아보이는데 그렇게 많진 않다. 1. 두 선거구로 나눈다. 2. 두 선거구의 인구 차이를 구한다. 3. 두 선거구를 올바르게 나눴다면 인구 차이의 최솟값을 갱신한다. 2번과 3번의 순서가 바뀌어야 하지 않나?라고 생각할 수도 있다. 근데 인구 차이를 먼저 구하고 그 값이 현재의 최솟값보다 크거나 같다면 3번을 실행하지 않을 것이다. 그럼 불필요한 연산을 하지 않으니 시간이 좀 줄어들 것이다. 두 선거구를 나누는 조합 연산은 비트마스킹으로 했다. 소스코드 #include #include using namespace std; vector split, visited; vector population; vector graph; int calcDiff() { //두 선거구의 인구 차이 int bl..

문제 풀이 처음에는 각 사람들의 연결관계를 그래프로 만들어서 dfs했는데 생각해보니 정답을 맞고 보니 유니온 파인드로도 풀 수 있단걸 깨달아서 유니온 파인드로도 풀었다. 두 풀이 모두 중요한 부분은 모든 파티 정보를 고려해서 연결되어 있는 사람들을 전부 찾아야 한다는 것이다. 소스코드 - dfs #include #include using namespace std; vector isLie; //이 사람에게 거짓말을 할 수 있나? vector party_info; //파티 정보 vector graph; //연결 정보 void dfs(int cur) { //거짓말을 할 수 없는 사람을 체크 isLie[cur] = false; for (int i = 0; i < graph[cur].size(); i++) { i..

문제 풀이 루트노드를 직접 찾아야 한다는 것을 몰라서 많이 헤맸다. 그것만 아니었어도 30분은 아꼈을텐데... 이 문제를 보자마자 제일 먼저 한 생각은 레벨 순회를 해야겠다는 것이었다. dfs에 속한다고 볼 수 있는 preorder, inorder, postorder와 달리 level traversal은 bfs에 속한다. 아무튼 이걸 사용해서 각 레벨별 정점을 정리해야겠다고 생각했다. level1 - 1 level2 - 2, 3 level3 - 4, 5, 6, 7 이런식으로 저장될테니 나중에 레벨마다의 너비를 구할때도 각 레벨의 첫번째 값과 마지막 값의 길이만 구하면 된다. 근데 문제는 각 정점의 열을 구하는 것이었다... 처음에는 분할정복으로 각 정점의 열을 구했는데 이것도 문제는 없는 코드였다. 굳이..

문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제에서처럼 dfs를 사용해 각 섬을 구분지을 것이다. 그리고 가장자리에 위치한 모든 땅들에 대해 bfs로 최단거리를 구하는데 만약 이전의 bfs로 구해놓은 최단거리가 4 였다면 거리가 4보다 커질 때 bfs 탐색을 종료해 시간을 아낀다. 소스코드 #include #include..

문제 풀이 굉장히 비효율적인 방법으로 풀었는데 시간초과가 나지 않았다. 문제를 풀고나서 효율적으로 작성한 코드를 몇개 봤지만 도통 이해가 되지 않아서...강해져서 돌아와야겠다. 아무튼 내가 한 비효율적인 방법은 정점의 개수만큼 dfs를 실행한 것이다. 최대 입력이 3,000이라 시간초과가 발생할 것이라고 생각했는데 그렇지 않았다. 사실 다른 효율적인 방법을 나름 시도해봤지만 영 제대로 풀리지가 않았다. myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 그..

문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 방법을 배웠다. 이번에도 똑같은 방법으로 dfs를 하면서 사이클을 찾으면 된다. 그냥 사이클 여부만 확인하면 되는거라 간단한 문제다. 소스코드 #include #include #include #include using namespace std; vector board; //문자, 방문여부 int N, M; bool isCycle; pair dir[4] = {{-1, 0}, //상 ..

문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근데 dfs를 많이 사용해봤다면 이런 생각이 들 수 있다. dfs는 가능한 정점을 찾을 때 visited를 체크하는데 그럼 2가 이미 visited 였을테니 4->2가 될리 없지 않나? 그래서 연결된 정점을 찾고 dfs를 실행할 때는 visited를 체크하지 않는다. 근데 이러면 또 이런 생각이 들 수 있다. 그럼 1->2를 가고도 2->1이 탐색 가능해지는거고 이럼 무한루프가 되는거 아닐까? 그렇기 때문에 dfs의 현재 정점과 더불어 이 정점이 어떤 정점에서 이어져온 것인지 직전 정점도 저장한다. 소스코드 #include..

문제 풀이 그림에 답이 있다. 오른쪽 그림의 회색 점들 중에서 아무거나 하나를 찍어보자. 그리고 그 회색점에서 가장 멀리있는 점을 찾아보자. 어떤 회색점을 골라도 두 개의 파란점 중 하나가 선택될 것이다. 그렇다면 아무 점이나 하나 고르고, 그 점과 가장 먼 점을 고르면 그건 지름을 구성하는 2개의 점 중 하나인 것이다. 그러면 이렇게 구한 점 하나에 대해 또 가장 멀리 있는 점을 고르면 그 점은 지름을 구성하는 또다른 점인 것이다. 그 둘 사이의 거리가 지름이다. 이걸 구현하기 위해 dfs를 2번 사용할 것이다. 첫번째 dfs로 지름을 구성하는 점 중 하나를 찾고, 두번째 dfs로 트리의 지름을 찾는다. 거리를 dfs로 구해도 되는지 걱정될 수도 있다. 근데 트리의 특징 중 하나는 특정 정점 2개를 연..