깊이우선탐색7 [C/C++] 백준 #2673 교차하지 않는 원의 현들의 최대집합(깊이우선탐색) 일단 이 문제는 추천하는 알고리즘은 동적 계획법(Dynamic Programming)입니다.저는 깊이우선탐색(Depth First Search)를 이용해서 문제를 풀었고, 경과시간은 4ms를 얻었네요. 아마 동적 계획법을 이용해서 풀면 더 나은 결과가 있었을 것이라고 생각은 합니다. https://www.acmicpc.net/problem/2673 제가 한 방법은 다음과 같습니다.1) 모든 현들과 서로 교차하지 않는 현들을 구해서 그 결과를 비트 플래그로 저장 \(O(N^2)\)2) 1번 현부터 시작해서 모든 현에 대해서 2-1) 교차하지 않는 현들을 방문하여 최대 길이를 구한다. 이 프로그램은 원 위에 주어진 여러 개의 현(chord) 중에서 서로 교차하지 않는 최대 개수의 현을 찾는 문제를 해결.. 2024. 7. 8. [C/C++] 백준 #2667 단지번호붙이기(깊이우선탐색) 제가 회사에서 개발자를 뽑을 때, 코테를 실시해서 그 결과를 가지고 1차에서 거르고 면접을 보게 되는데, 이 문제와 같은 유형은 단골 메뉴로 들어가 있습니다. 보통은 섬의 갯수 구하기 문제입니다. 이 문제도 거의 같지만, 섬의 크기, 여기서는 단지의 크기를 정렬하고, 그 결과를 출력하는 것만 다릅니다. 이런 문제는 너비우선탐색을 이용해서 풀어도 되겠지만, 프로그램의 복잡도상 깊이 우선탐색이 보다 편리합니다. 그리고 방문 기록을 지도에 바로 활용하면 추가적으로 필요한 저장 공간 \(O(N^2)\)을 잡지 않아도 됩니다. https://www.acmicpc.net/problem/2667 ### 주요 변수- `q`: 각 노드가 가리키는 다음 노드를 저장하는 배열.- `v`: 각 노드의 방문 상태를 저장.. 2024. 6. 3. [C/C++] 백준 #2636 치즈(깊이우선탐색) 이번 문제는 그래프 탐색 문제인데, 너비우선탐색을 사용해도 되고 깊이우선탐색을 사용해도 됩니다. 제 경우에는 깊이우선탐색(Depth First Search)을 이용해서 풀었습니다. https://www.acmicpc.net/problem/2636 문제에서 핵심은 공기가 있는 곳이라는 것을 확신할 수 있는 공간부터 시작을 하는 것입니다. 이 문제는 치즈의 공간에서 탐색을 하는 것이 아니고 공기 공간에서 탐색을 해서, 공기와 닿는 치즈를 다음번에 녹는다라고 표시하시면 됩니다. 제가 작성한 코드에서는 별도로 방문 표시를 배열을 잡아서 처리하지 않고, 그래프의 자료가 되는 맵에서 처리했습니다. 단지 탐색할 공간의 값을 매번 다르게 지정함으로써, 방문 배열을 초기화할 필요도 없고, 바로 처리할 수 있습니다.. 2024. 5. 14. [C/C++] 백준 #2573 빙산(깊이 우선 탐색) 이번 문제는 보다 좋은 알고리즘을 택하기 보다는 구현을 위주로 하였습니다. 깊이 우선 탐색은 섬의 개수가 몇개인지 판단하기 위해서 사용을 하였습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제는 빙하가 같은 높이만큼 녹을 때, 한덩어리의 빙하가 두덩어리 이상이 되는 최소 녹는 높이를 구하는 것입니다. 구현 자체는 간단합니다. 빙하가 녹는 높이에 따라서 빙하가 두개가 될 때의 높이를 출력하게 하였습니다. 제가 구.. 2023. 7. 30. [C/C++] 백준 #2367 파티(포드-폴커슨 알고리즘) 이번 문제는 파티에서 음식을 준비할 때, 음식의 종류와 할 수 있는 음식 종류, 그리고 가져올 수 있는 음식의 개수가 제한되어 있을 때, 최대한의 음식을 준비하는 것을 목표로 하는 내용입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2367 2367번: 파티 첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개 www.acmicpc.net 이 문제를 풀기 위해서는 최대 유량 알고리즘을 알아야 합니다. 최대 유량은 제한 조건이 있을 때, 그 조건을 지키는 한도 내에서 최대의 결과를 얻을 때 사용됩니다. 최대유량과 관련되어.. 2023. 4. 28. [C/C++] 백준 #2146 다리 만들기(DFS, BFS) 이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다. 문제는 아래의 링크입니다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다. 일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다. 다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다. 이 .. 2023. 4. 10. 이전 1 2 다음
