분류 전체보기52 BFS, DFS 탐색 알고리즘 그래프, 트리 등의 자료구조에서 탐색하는 알고리즘이다. BFS : 너비 우선 탐색 그래프/트리의 가까운 노드부터 방문하여 검색한다. Queue 자료구조를 이용하며 다음과 같이 동작한다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 두 번째 과정을 더 이상 수행할 수 없을 때 까지 반복한다. BFS 구현 탐색시간은 O(N)의 소요된다. DFS보다 수행시간이 좋은 편이다. #include queue q; void BFS(graph, start, visited) { q.push_back(start); visited[start] = true; while(!q.empty()) { int v = q.. 2024. 3. 18. 2217. 로프 그리디 문제이다. 1. 문제 풀이 2. Solution 1. 문제 풀이 필자는 로프 문제를 그리디로 해결했다. 필자가 생각해 낸 로프 문제의 탐욕법은 "정렬을 통해 k를 계산 + 각 로프당 들 수 있는 최소 중량을 이용하자" 이다. 예제 문제를 보면, 2개의 로프에 대해 각각 20, 25의 중량을 들 수 있다. -1개의 로프를 포함하는 경우: 최대 25 중량 가능 -2개의 로프를 포함하는 경우: 최대 40 중량 가능 단, 각 로프당 들 수 있는 최소 중량 = w/k (40중량/2개 = 20중량)을 만족해야 한다. 그렇기 때문에, 필자는 로프 문제를 해결하기 위해 1) 우선 로프가 들 수 있는 무게를 정렬 (오름차순 정렬) * 이때, 정렬을 안 하면, rope[i] MAX) ? w : MAX; } retu.. 2023. 1. 29. 11399. ATM 그리디 문제이다. 1. 문제 풀이 2. Solution 3. 알아야 할 개념 1. 문제 풀이 필자는 ATM 문제를 그리디 문제로 해결했다. ATM 문제에서 탐욕법은 "시간이 적게 걸리는 사람부터 ATM 사용하기" 이다. ATM 문제에서는 1번으로 ATM을 사용하는 사람이 N번 사용시간이 더해지고, 2번 사람은 N-1번 사용시간이 더해지고,,,, N번 사람은 1번 더해지기 때문이다. 2. Solution // 백준 11399 ATM #include #include #include using namespace std; int minTime(int N, vector& person) { // 시간이 적게 걸리는 사람이 앞으로 오도록 정렬 sort(person.begin(), person.end()); // 총 .. 2023. 1. 29. 2839. 설탕 배달 1. 올바른 풀이 2. 깔끔한 Solution 3. 나의 Solution 그리디 문제이다. (선택의 순간마다 당장의 눈 앞에 보이는 최적의 선택을 함) 1. 올바른 풀이 최소의 설탕봉지를 선택해야 한다. 필자는 이 문제를 해결하기 위해 "모든 경우의 수를 탐색해야 한다"에만 초점을 맞추어 잘못된 문제 풀이를 했다. 필자가 생각하는 올바른 문제 풀이는 "탐욕적으로 선택하기"이다. 그렇다면, 설탕봉지 문제에서 탐욕적인 선택은 "5kg 설탕봉지부터 가지기"이다. 예시로 30Kg 설탕봉지는 5kg 만으로 가져가면 6개의 설탕봉지를 배달하고, 3kg 만으로 가져가면 10개의 설탕봉지를 배달한다. 2. 깔끔한 Solution 알고리즘 문제를 풀 때, 깔끔한 코드를 보며 배우는 것은 중요하다고 생각한다. 아래의 코드.. 2023. 1. 29. 이전 1 2 3 4 ··· 13 다음
