본문 바로가기

백준

백준 1963 소수 경로 BFS 문제중에 좀 특이하게 맵 탐색이 아닌 다른 공간을 탐색하는 문제이다. 어떤 4자리 소수에서 각 자리수를 바꿔가며 다른 소수로 이동하면서 탐색을 하게 된다. 따라서 일단 소수를 찾아놓고, 각 자리수를 바꾼 숫자가 소수인지 확인해야 한다. 소수를 찾아놓을 땐, 에라토스테네스의 체를 이용해 정해진 범위(10000)까지의 소수를 찾는다. memset(filter, 1, sizeof(filter)); filter[0] = 0; filter[1] = 0; for (int i = 2; i < 10000; i++) { if (filter[i]) { for (int j = 2*i; j < 10000; j+=i) filter[j] = 0; } } 그리고, 탐색을 하는 과정에서 각 자리수를 바꿔야 하므로 조금 더 편.. 더보기
백준 2206 벽 부수고 이동하기 BFS를 사용해 맵을 탐색하는 문제이다. 단순히 출발지에서 도착지까지 탐색하는것에 더해, 우리의 플레이어는 원래는 가지 못하는 벽을 한번 부수고 통과할 수 있다.(이하 슈퍼파워) 이 부분에 있어서 살짝 꼬여진 문제라고 볼 수 있다. 일반 BFS 탐색 코드와 달라지는 점은, visited 배열이 달라진다는것과 큐에 넣을때 두 가지 조건(벽을 부수는 경우, 아닌 경우)을 따져야 한다는 점이다. visited[0 or 1][N][M] 배열은, N*M 크기 맵에서 해당 픽셀을 벽을 부수고 나서 도달하였는가(1), 벽을 부수지 않고 도달하였는가(0)을 의미한다. 해당 visited 배열을 보고, 큐에 넣을 때의 조건을 따진다. 다음 방문 픽셀이 벽이고, 벽을 부술 수 있으며, 벽을 부수고 방문하지 않은 경우 ->.. 더보기
백준 1626 두 번째로 작은 스패닝 트리 LCA - 최소 공통 조상을 사용하는 문제이다. 두 번째로 작은 스패닝 트리를 구할 때, MST에 포함되어있지 않은 에지를 골라서 그 에지가 잇는 두 노드의 경로 중 최대값 에지를 빼는 과정이 필요하다. 두 노드의 최단 경로를 찾을 때 LCA 알고리즘을 사용한다. 여기에, "두 번째로 작은" 이라는 조건이 붙으므로, 추가된 에지 비용과 경로 중 최대값 에지의 비용이 같으면 안된다. 그 다음으로 큰 에지를 골라야 한다. 여기까지 생각해보면, LCA에서 사용한 parents[K][V] 배열은 그대로 있어야 하고, path[K][V]를 만들어서 V에서 2^K 조상까지의 경로를 벡터형식으로 저장을 하면 좋을 것 같다. 나중에 두 노드에서 LCA까지 경로를 전부 아니까 거기서 MST 비용보다 큰 노드를 찾기만 하.. 더보기
백준 15481 그래프와 MST 역시 LCA를 활용하는 문제이다. 저번 정점들의 거리 문제에서 MST의 개념을 살짝 붙이기만 하면 방법을 찾을 수 있다. 에지를 입력받을 때, 인접 행렬을 직접 만드는 것이 아니라, 에지만 저장하는 벡터/배열을 선언하고 나중에 그 에지들을 순회하며 MST를 찾을 수 있게 한다. std::vector adj[N]; std::priority_queue pq; std::vector vEdgeList; 일단 에지를 입력받고 난 다음, 그 에지들을 사용해 MST를 계산한다. MST를 계산하면서 adj(인접행렬)을 채워 이 트리를 사용해 LCA를 구하게 된다. for (int i = 0; i > s >> e >> c; s--; e--;.. 더보기
백준 1761 정점들의 거리 LCA를 활용하는 문제이다. LCA 분류 문제만 풀다보니 거의 같은 코드에 조금만 바꾸는 느낌이 계속 든다. 근데 LCA 알고리즘은 진짜 신기한것 같다. 관련 포스팅을 몇개 연속해서 써도 얘가 돌아가는 매커니즘이 계속 신기하다. 2진수 사고방식을 쉽게 머리속에서 굴릴 수 있는 사람이 처음 만든 것 같은데, 어쩜 저런 생각을 했는지... 각설하고. 이번 문제는 이전에 있었던 도로 네트워크 와 거의 유사하다. 중간중간 코드 몇줄만 바꿀정도. LCA에 대한 개념부터 보고싶다면 LCA 설명 글도 있다. 도로 네트워크에서는 parents[] 배열 이외에 pathMax[K][V], pathMin[K][V] 배열이 존재해 각각 2^K 번째 노드까지 경로 중 cost가 최소인 것과 최대인 것을 저장했었다. 이 문제에서.. 더보기
백준 3176 도로 네트워크 LCA를 활용하는 문제이다. 두 도시를 연결하는 경로는 LCA를 통해 구할 수 있다. 두 노드 u, v에서 LCA까지 이르는 경로를 합치면 두 도시를 있는 최소 경로가 된다. LCA 2 에서는 parents[] 배열에 2^K 번째 부모 노드들을 저장했었는데, 이것을 응용해 2^K 번째 부모 노드까지의 경로에서 에지의 최소값을 저장하는 배열과 최대값을 저장하는 배열을 만들기만 하면 문제를 해결할 수 있다. LCA 2에서 달라질것은, pathMax[] 배열과 pathMin[] 배열을 새로 만든것과, Parents[] 배열을 초기화하거나 갱신할때 새로 만든 두 배열도 값을 넣어준다는 것, 두 노드의 높이를 맞춰주거나 맞춘 후 위로 탐색할때 u와 v가 움직이는것에 맞춰 탐색되는 경로 상 최대/최소값을 찾아준다는.. 더보기
백준 11438 LCA 2 트리를 입력받은 뒤, 공통 조상 중 가장 가까운(높이가 낮은) 노드를 찾는 문제이다. LCA 1이 있고 LCA 2가 있는데, LCA 1은 나이브하게 공통 조상을 밑에서부터 같이 찾아 올라가도 정답 처리가 되지 않을까 싶다. 그 문제는 골드3이고 이 문제는 플레 5이므로 난이도 차이가 꽤 난다. 문제의 접근은 DP-Like 하다. DP도 제대로 본건 아니지만, 연산 과정을 배열에 저장한다는 관점에선 비슷하다고 볼 수 있지 않을까? DP를 좀 더 많이 해보고 차이점을 더 잘 알게 된다면 이 글을 수정해야겠다. 그럼 여기서 DP-Like 하게 연산과정을 저장한다고 했는데, 무엇을 저장하는가? 바로 어떤 노드의 2^K번째 조상을 저장한다. 100000개의 노드가 있을 때, Worst Case일 경우 높이는 10.. 더보기
백준 2042 구간 합 구하기 진짜 제곧내 문제 이다. 입력받은 N개의 수에서 두 인덱스 사이의 부분합을 구하거나, 특정 인덱스의 수를 변경하는 두 가지의 연산을 하면 된다. 엄청 나이브하게 접근해서 작동만 하는것을 짰을때는 진짜 말그대로 배열에서 하나씩 탐색하며 부분합을 더했고, 변경도 배열에서 직접 변경하도록 했다. 시간초과인걸로 기억한다. 이런 구간 합 문제에서 투 포인터 알고리즘을 사용할 수도 있었다. 하지만 검색을 해보니 세그먼트 트리로 접근해야 한다고 해서 관련된 내용을 찾아보고 작성했다. 세그먼트 트리에 대한 내용은 따로 작성한 포스팅이 있다. 세그먼트 트리는 각 노드가 자신이 포함하고 있는 노드들의 합을 저장하는 트리라고 할 수 있다. 코드 전에 각 함수의 로직을 간략히 보면, init() leaf node나오기 전까지.. 더보기

티스토리툴바