📂 해시테이블 정렬알고리즘에 비해 탐색알고리즘은 수시로 탐색이 진행된다(ex. 데이터베이스에서 원하는 데이터를 찾을 때) 따라서 탐색 알고리즘에서 탐색에 소요되는 시간을 단축시키는 것은 굉장히 중요한 이슈이다. 원소가 저장될 자리가 원소의 값에 의해 바로 결정되는 자료구조 → O(1) 시간으로 매우 빠른 응답을 요구할 때 사용되는 기법 cf. 탐색 트리의 경우 원소의 값에 의해 위치가 결정되지만 트리를 탐색해 내려가는 시간이 소요됨 최소값, 특정값 바로 전/후의 값 등을 찾아낼 수 없으며 그냥 특정값의 위치를 찾아내기만 하는 '탐색'의 기능만 함 해시테이블에서는 해시함수 h(x) = (ax + b) mod p 를 이용해 원소가 저장될 위치를 결정함 h(x) = x mod 11 값을 균등하게 배분할수록 좋..
🧨 백준 9370번 - 미확인 도착지 문제 난이도 : 골드2 (어렵다 어려워) 문제 링크 : www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 #include #include #include #include #include using namespace std; struct edge { int to, length; }; int dijkstra(const vector& graph, int source, int target) ..
🧨 백준 10282번 - 해킹 문제 난이도 : 골드4 문제 링크 : www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 #include #include #include #include #include using namespace std; struct edge { int to, length; }; int cnt = 0; int dijkstra(const vector& graph, int source, int target) { vect..
📁 최단거리문제 보통 시작노드부터 도착노드까지의 최단경로를 구하는 형식의 문제이다. MST에서 알 수 있듯이 최단경로는 절대 사이클을 포함하지 않는다. 최단거리 문제는 가중치 유무에 따라, 가중치가 있을 경우엔 가중치의 음양에 따라 알맞은 알고리즘을 사용한다. 양의 가중치만 있을 때 : 다익스트라 알고리즘(Dijkstra's Algorithm) 음의 가중치만 있을 때 : 벨만포드 알고리즘(Bellman-Ford Algorithm) n 대 n의 최단거리를 모두 구하고 싶을 때 : 플로이드와샬 알고리즘(Floyd-Warshall Algorithm) 📁 다익스트라 알고리즘 Dijkstra's Algorithm 에지의 가중치가 양수일 때 사용한다. 음수 가중치를 고려하지 않으므로 가중치의 합이 최단거리를 좌우한..
📂 최소신장트리 (Minimum Spanning Tree) 신장트리 : 그래프 G의 노드 V를 모두 포함하는 E에 속하는 에지를 사용해 만든 트리 최소신장트리 : 가중그래프 G의 신장트리 중에서 트리에 속한 가중치의 합을 최소로 하는 신장 트리 최소신장트리를 만드는 2가지 방법 : Prim's Algorithm, Kruskal's Algorithm 최소신장트리의 간선 개수는 (정점의 수 - 1) 이다. (N-1개의 간선으로 연결되어 있으면 필연적으로 모든 노드가 연결된다) 간선들의 가중치 합이 최소인 경우 서로 다른 최소신장트리가 하나 이상 있을 수 있다. 📂 크루스칼 알고리즘 (Kruskal's Algorithm) 가중치가 가장 작은 간선부터 차례대로 간선을 선택해 나가는 방법으로, 탐욕적(greedy..
🧨 백준 1707번 - 이분 그래프 문제 난이도 : 골드4 (낮은 정답률에는 이유가 있다) 문제 링크 : www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 🧨 알고리즘 선택 및 C++ 코드 메모리초과, 런타임에러(Segfault, OutofBounds)에 틀렸습..
🧨 백준 10026번 적록색약 문제 난이도 : 골드5 문제 링크 : www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 유기농배추 문제와 크게 다를 거 없고, 대신 0과 1의 이분법이 아니라 0, R, G, B를 구분해야 하는 정도가 조금 더 난이도 있다고 볼 수 있다. 여태까지 그래프 관련 문제들 계속 BFS로 구현했어서 이번에는 재귀를 사용한 DFS로 구현했다. 조금 어렵다고 생각했는데 막상 짜보니 별거 아닌 거 같다..
🧨 백준 1012번 - 유기농 배추 문제 난이도 : 실버2 문제 링크 : www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 2178번 미로탐색 문제와 비슷하게 2차원 좌표를 이용해 위치 이동을 해야하므로 상하좌우 dx, dy 배열을 사용했다. 재귀를 사용하는 DFS는 뭔가 거부감이 있어서 일단 BFS로 구현했다. (DFS로 짜도 상관없는 거 같다) 처음에 대체 어디에 배추가 있는지 알아야 지렁이를 놓든 말든 할거 아닌가 싶어서 이를 표시해..
🧨 백준 2178번 미로탐색 문제 난이도 : 실버1 문제 링크 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 처음 문제를 봤을 땐 좀 낯설었다. 뭔가 너비우선탐색을 사용하는 거 같은데 어떻게 사용할지 한참 고민했다. 미로에서 칸 이동을 해야 하므로 어쩔 수 없이 상하좌우 대소비교가 들어가야했다. 그래프 탐색을 이용한 문제는 대부분 원하는 값만을 구하려고 하면 어렵게 느껴진다. 갈 수 있는 모든 칸에 대해 지나야 하는 최소 칸 수를 계산해야 (N, M)..
🧨 백준 2644번 - 촌수계산 문제 난이도 : 실버2 문제 링크 : www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 DFS를 쓰는 줄 알았는데 코드에 감이 안 잡혀서 더 생각해봤더니 BFS를 활용한 문제였다. 너비우선탐색으로 깊이를 카운팅했다. 정점(첫 노드)에서 내가 원하는 사람까지 가는 깊이만 카운팅하려 했는데 조건문 쓰는 게 더 복잡해서 그냥 다 계산했다. 입력받은 start 사람에서 모든 사람들까지의 ..
