목록개발/알고리즘 (35)
그냥 MST문제인가 생각하고크루스칼 알고리즘을 적용해 보았다. 아래 코드는 실패한 코드이다.#include #include #include #include #include using namespace std; vector table;int find(int root){ if (table[root] != root) { table[root] = find(table[root]); } return table[root];}int find_union(int a, int b){ int root_a = find(a); int root_b = find(b); if (root_a > n; vector> route(n, { 0, 0, 0 }); priority_qu..
과거 kmp알고리즘을 공부한 적이 있는데 이를 이용하는 문제이다.문자열을 비교할 때 건너뛰면서 비교하는 기법이다. #include #include #include using namespace std;vector make_pi(string pattern){ vector pi(pattern.size(), 0); int i = 0; for (int j = 1; j 0 and pattern[i] != pattern[j]) i = pi[i - 1]; if (pattern[i] == pattern[j]) { i++; pi[j] = i; } } return pi;}int main(){ string text; string pattern; getline(cin, text); getline(cin, pa..
다음과 같은 예시가 있다고 가정하면L=3 1 5 2 3 6 2 3 7 3 5 2 6idx = 0 1idx = 1 1 5idx = 2 1 5 2idx = 3 5 2 3idx = 4 2 3 6idx = 5 3 6 2idx = 6 6 2 3idx = 7 2 3 7idx = 8 3 7 3idx = 9 7 3 5idx = 10 3 5 2idx = 11 5 2 6 각 구간마다 최솟값을 출력하는 게 목표이다. 실패한 첫번째 시도#include #include #include #include using namespace std;int sub_main(){ int n, l; cin..
스택을 이용하여 풀었다.로직을 설명하자면 가로길이만큼 반복문 진행하는데스택의 top값과 비교해서 더 큰 값이 나오면 stack에 계속 담는다.top보다 작은 값이 나오면 더 작은 값이 나올 때까지 pop 한다.pop 하는 과정에서 넓이를 계산한다. [idx = 0] 비어있으니 스택에 삽입stack : (0, 1) [idx = 1] 스택 top보다 idx 1이 더 크기가 커서 스택에 삽입stack :(1, 2)(0, 1) [idx = 2]stack : (2, 3)(1, 2)(0, 1) [idx = 3]stack :(3, 4)(2, 3)(1, 2)(0, 1) 작은 값이 나와서 pop 진행[idx = 4]stack : (2, 3)(1, 2)(0, 1)pop data = (3, 4)넓이 : 4 * 1..
https://www.acmicpc.net/problem/14500 골드4티어 문제이다. 한 점에서 4칸까지 움직일 동안 DFS로 탐색을 진행하면T모양을 제외한 모든 모양을 만들 수 있다.최댓값을 구해주고 나중에 T모양을 따로 탐색을 진행해 준다.T 같은 경우는 십자가 모양을 전부 더해서 최솟값을 빼준다. #include #include #include using namespace std;vector> graph;vector> visited;int n, m;int dy[4] = {0, 1, -1, 0};int dx[4] = { 1, 0, 0, -1 };int answer = -1;void dfs(int cnt, int total, int y, int x){ if (cnt == 4) { answe..
골드5 간단한 문제를 풀었다. 계속 양옆의 큰값을 비교해 작은 값을 자기 자신과 빼준다.자기 자신이 더 크거나 값이 같으면 그냥 넘어간다. #include #include #include using namespace std;int main(){ int H, W; cin >> H >> W; vector data; int answer = 0; for (int i = 0; i > temp; data.push_back(temp); } for (int i = 1; i
새로운 알고리즘이다.최소 공통 조상을 찾아주어야 한다. 해당 트리를 예시로 든다.1은 루트 노드이다. 10과 15노드의 최소 공통 조상은 2이다.루트노드로 계속 거슬러 올라가며 공통으로 도달하는 노드이다. 10과 15의 레벨을 확인해준다.루트노드가 레벨이 1부터 시작하면10은 4이고 15는 5이다. 레벨이 같아질 때까지 노드를 이동해 준 다음동시에 한 레벨씩 올라가면 LCA를 찾을 수 있다. //11437 LCA#include #include using namespace std;vector> adj;vector level;vector parent;int n;int lca(int a, int b) { if (level[a] > n; adj.assign(n + 1, {}); level.assign(..
BFS 완전탐색 문제이다.간단한 골드5 문제이다. #include #include #include #include using namespace std;//보물상자int dx[4] = { 1, 0, -1, 0 };int dy[4] = { 0, 1, 0, -1 };typedef pair p;int BFS(vector> &temp_graph, int start_y, int start_x) { queue qq; qq.push(p(start_y, start_x)); int size_y = temp_graph.size(); int size_x = temp_graph[0].size(); temp_graph[start_y][start_x] = -1; int max_data = 0; while (!qq.empty()) ..