본문 바로가기

자료구조 & 알고리즘9

[C++] 백준 1012 유기농 배추 #include using namespace std; const int dy[4]={-1, 0, 1, 0}; const int dx[4]={0, 1, 0, -1}; int t, m, n, k, a[52][52], x, y; int visited[52][52], cnt, ret[3]; void dfs(int y, int x){ visited[y][x] = 1; for(int i=0; i> t; while(t--){ cnt=0; fill(&a[0][0], &a[0][0]+52*52, 0); fill(&visited[0][0], &visited[0][0]+52*52, 0); cin >> m >> n >> k; for(int i=0; i> x >> y; a[y][x] = 1; } for(int i=0; i 2023. 7. 31.
[C++] 백준 2178 미로탐색 #include using namespace std; int n, m; string s; int a[104][104]; int visited[104][104]; int y, x, c, d; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, 1, 0, -1}; void bfs(int y, int x){ visited[y][x] = 1; queue q; q.push({y, x}); while(q.size()){ tie(c, d) = q.front(); q.pop(); for(int i=0; i> n >> m; for(int i=0; i> s; for(int j=0; j 2023. 7. 30.
[C++] 백준 2606 바이러스 #include using namespace std; int n, m; vector adj[101]; int a, b; int visited[101]; int cnt; void dfs(int here){ visited[here] = 1; cnt++; for(int there : adj[here]){ if(visited[there]) continue; dfs(there); } return; } int main(){ cin >> n; cin >> m; for(int i=0; i> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1); cout 2023. 7. 29.
힙(Heap), 힙화(Heapify), 최댓값, 최솟값 구하기, 구현 ●힙(Heap) - 최댓값, 최솟값을 빠르게 검색할 수 있는 자료구조 - 완전이진트리(Complete Binary Tree) 형태로 구성 - Max Heap, Min Heap으로 구성 - Max Heap(최대 힙) 부모노드 >= 자식노드 => 루트에 최댓값이 들어있다. - Min Heap(최소 힙) 부모노드 루트에 최솟값이 들어있다. -힙 트리에서는 이진탐색트리와는 다르게 중복된 값을 허용한다. -힙화(Heapify) 무작위로 데이터가 들어간 배열 구조를 힙 구조에 맞게 변경하는 것 이런 트리구조가 있다고 해보자. 3 2 4 1 5 6 먼저 자식노드가 있는 노드들을 중심으로 생각한다. 1, 5, 6은 자식 노드가 없기 때문에 일단 제쳐놓는다. 자식중에 더 큰 노드의 값을 찾는다. 부모와 자식을 비교한 다.. 2023. 2. 25.
이진탐색트리 노드 삭제 개념, 구현 ●노드 삭제 경우 3가지 - 자식 노드가 없는 경우 - 자식 노드가 한 개인 경우 - 자식 노드가 두 개인 경우 - 자식 노드가 없는 경우 위의 트리에서 3번 노드를 없애려고 한다. 3번노드 삭제 -> 3번노드의 부모인 2번노드에 NULL을 넘겨준다. - 자식 노드가 한 개인 경우 2번노드를 없애려고 한다. 2번노드를 바로 없애버리면 1번노드의 정보가 사라진다. 그래서 temp 임시변수를 하나 만들어서 1번노드의 주소를 저장한다. 과정: temp에 1번노드 저장 -> 2번노드 삭제 -> 1번노드의 주소값을 4번노드에 넘겨준다. - 자식 노드가 두 개인 경우 루트인 8번노드를 없애려고 한다. 왼쪽 자식중 최댓값을 구해서 삭제하려는 위치로 덮어쓰기 한다. 위의 트리에서는 왼쪽 최댓값이 7이므로 원래 8자리에.. 2023. 2. 24.
이진탐색트리 최댓값, 최솟값 노드 찾기, 구현 ●이진검색트리의 특징 부모를 기준으로 부모보다 큰 데이터 오른쪽에, 작은 데이터는 왼쪽에. 따라서 루트를 중심으로 오른쪽 끝까지 찾아가면 최댓값을 찾을 수 있다. 왼쪽 끝까지 찾아가면 최솟값을 찾을 수 있다. ●최댓값, 최솟값 찾는 과정 구현 typedef struct TREE { int value; struct TREE* left; struct TREE* right; } TREE; TREE* findMax(TREE* t) { if(t) { while(t->right) t = t->right; return t; } } TREE* findMin(TREE* t) { if(t->left) t = findMin(t->left) return t; } 반복문으로 구현할 수 있으면 반복문으로 구현하는 것이 좋다. 최.. 2023. 2. 23.