반응형 depth first search6 [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++] #2583 영역 구하기(깊이 우선 탐색) 이번 문제는 복합 문제입니다. 색종이 붙이기 문제와, 섬의 갯수 구하기 문제가 결합된 문제라고 생각하시면 편합니다. https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 색종이 붙이기 문제는 캔버스를 생성한다음, 색칠하기만을 하시면 됩니다. \(O(MNK)\) 알고리즘이긴 하지만, 조금 더 개선을 하시면, \(O(MN+K)\) 알고리즘으로도 하실 수 있습니다. https://sdev.tistory.com/1547 [C/C++] 백.. 2024. 1. 2. [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. 이전 1 다음 728x90
