Algorithms13 C++/ Knapsack 알고리즘 냅색 알고리즘이란? 더보기 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 한정 조건을 가지고, 다수의 조합이 가능할 때 모든 조합을 고려해서 최적의 해를 구하는 문제의 해결법. 냅색 문제를 풀 때는 Top-down 방식과 Bottom-up 방식 적용이 가능하다. Top-down 방식에서는 DFS를 이용하는 것이 일반적이며 메모이제이션을 추가하는 것이 효율성을 증대시킨다. #include #include #include using namespace std; //top-down int arr[21][21], dy[21.. 2021. 3. 18. C++/ BFS 활용문제 - 섬나라 아일랜드, 미로의 최단거리 통로 Queue를 이용해 최단 거리를 사용하는 문제 => BFS 그것 까진 알겠는데, 내부 논리를 짜 놓고 외부 탐색 루프를 짜는 게 자꾸 헷갈린다 ,,ㅠ ㅠ 안에서 부터 짜야하는지 큰 골격을 생각하고 내부를 짜야하는지 모르겠다 아마 문제를 많이 풀어봐야 개선되겠지!?!? 섬나라 아일랜드 (출처 - 인프런 강의) 1이 연결되어 있는 뭉텅이를 찾아 총 섬의 개수를 세는 문제이다 DFS, BFS 모두 가능하지만 인프런 강의에서는 bfs를 사용했기 때문에 bfs 먼저 보려고 한다. 내가 짠 코드 자료구조 - 격자 판은 vector 형을 사용했음. - 좌표는 pair 사용 - queue 로 저장함 루프 이중 while 문을 이용함. 격자를 매번 처음부터 끝까지 탐색하게 하고 싶지 않아서 좌표 (point) 변수에 제.. 2021. 3. 1. C++/ 다익스트라 알고리즘 (가중치 방향 그래프), 신호 라우팅 문제 다익스트라 알고리즘 최단경로 문제란 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제이다. 가중치가 없는 그래프의 최단 경로는 bfs를 이용해 찾을 수 있다. 최단 경로 문제에서 먼저 유의해야 할 점은 음수 가중치 간선의 존재 유무이다. 그래프에 음수 가중치를 갖는 간선이 존재하면 전체 경로의 길이가 짧아지게 된다. 다익스트라 알고리즘은 음수 가중치 간선이 없다는 가정 하에 동작하게 된다. 다익스트라 알고리즘은 bfs와 유사한 형태를 가진 알고리즘으로, 시작점에서 가까운 순서대로 정점을 발견해가는 방식이다. dfs에서는 큐의 정점의 번호를 넣었지만, 다익스트라에서는 정점의 번호와 함께 해당 정점까지의 최단 거리를 쌍으로 Min-heap 우선순위 큐에 저장하게 된다. 단, b.. 2021. 2. 19. C++/ 최소 스패닝 트리, Kruskal & Prim algorithm Spanning Tree (신장 트리) 란 그래프 내의 모든 정점을 포함하는 트리이며, 사이클을 포함해서는 안되는 트리이다. 사이클을 포함하지 않기 때문에 n개의 정점이 존재하면 간선의 개수는 n-1개이다. Minimum Spanning Tree (최소 신장 트리, MST) Spanning Tree 중에서 간선의 가중치 합이 최소인 트리를 일컫는다. -> 네트워크에 있는 모든 정점들을 가장 적은 수, 최소 비용의 간선으로 연결하는 트리를 말한다. 이런 MST를 구현하는데에 잘 알려진 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. Kruskal MST Algorithm 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식의 알고리즘. (단순히 추.. 2021. 2. 16. C++/ 우선순위 큐 + 구조체를 이용한 벡터 정렬 (3개 이상의 값) 더보기 인프런 73,74 강의 1. 우선순위 큐 앞서 bfs에서 많이 활용한 큐 자료구조는 First in First out 구조로, rear로 데이터가 삽입되고 front로 삭제되는 구조였다. 우선순위 큐란 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조이다. 우선순위 큐는 최대 힙, 최소 힙을 구현하고자 할 때 쓰이는 자료구조이다. 더보기 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. 여기서 최대 힙은 내림차순으로 정렬된 이진 트리라고 생각하면 되기 때문에, root에 가장 큰 원소가 .. 2021. 2. 6. C++/ DFS 완전탐색 -이중배열, STL vector pair 인프런 dfs 강의 58번~68번까지 들은 후에 정리하는 글 "완전 탐색"을 가능하게 하는 dfs 함수로 경로탐색, 미로탐색, 최소비용 문제를 풀어보았다. 문제를 풀면서 무방향 그래프, 방향 그래프 모두 이차원 배열로 구현해 본 후에 vector pair 자료구조를 이용해서 더 효율성 있는 코드 작성법을 배웠다. 1. void DFS(int vertex) 문제를 풀면서 쓰인 dfs 함수의 구조는 거의 동일했다. if 문을 이용해 재귀함수를 빠져나올 조건을 걸고, else 문에서 다음 경로로 가는 코드를 짠다. void dfs(int v){ int i; if(v==n){ cnt++; } else{ for(i=1;i 2021. 1. 30. 이전 1 2 3 다음 반응형
