*이 글은 2022년 1월~2월 노션으로 진행한 알고리즘 스터디를 옮긴 글입니다. 나동빈 저자 이것이 취업을 위한 코딩테스트다를 사용해 학습했습니다.
220208 자료구조(스택/큐) 복습
- 삽입(push): 데이터 삽입 / 삭제(pop): 데이터 삭제
- 언더플로/오버플로 고려해야 함(배열의 경우 특히)
- 스택
-
후입선출(LIFO)
-
stack stl 사용
#include<stack> #include<iostream> using namespace std; int main() { stack<int>a; a.push(5); a.push(2); a.push(3); a.push(7); a.pop(); a.push(1); a.push(4); a.pop(); cout << "size: " << a.size() << endl; while (!a.empty()) { cout << a.top() << endl; a.pop(); } return 0; }출력결과 size: 4 1 3 2 5
-
- 큐
-
선입선출(FIFO)
-
deque stl 사용
#include<iostream> #include<deque> using namespace std; int main() { deque<int>a; a.push_back(5); a.push_back(2); a.push_back(3); a.push_back(7); a.pop_front(); a.push_back(1); a.push_back(4); a.pop_front(); for (int i = 0; i < a.size(); i++) { cout << a[i] << endl; } return 0; }출력결과 3 7 1 4
-
220208 재귀함수
- 종료 조건을 꼭 명시해야 함 (무한 호출 방지)
- 컴퓨터 내부에서 재귀 함수 수행은 스택을 이용
- 그런 이유로 스택 이용해야 하는 알고리즘은 대부분 재귀함수 사용하여 간편하게 구현 가능(DFS)
220209 BFS/DFS 내용정리
- 인접리스트 사용해서 구현함
- DFS(depth first search)
-
깊이우선탐색
-
스택 사용하므로 재귀함수 사용하여 간단히 구현 가능
공백 //5 //4 //6 //7 //8 //3 //2 //1 #include<iostream> #include<vector> using namespace std; bool visited[9]; vector<int>graph[9]; void dfs(int x) { //현재 방문한 노드를 true로 visited[x] = true; cout << x << " "; //그래프x의 인접노드가 순회 전이라면 재귀함수 for (int i = 0; i < graph[x].size(); i++) { int y = graph[x][i]; if (!visited[y])dfs(y); } } int main() { graph[1].push_back(2); graph[1].push_back(3); graph[1].push_back(8); graph[2].push_back(1); graph[2].push_back(7); graph[3].push_back(1); graph[3].push_back(4); graph[3].push_back(5); graph[4].push_back(3); graph[4].push_back(5); graph[5].push_back(3); graph[5].push_back(4); graph[6].push_back(7); graph[7].push_back(2); graph[7].push_back(6); graph[7].push_back(8); graph[8].push_back(1); graph[8].push_back(7); dfs(1); }출력결과 1 2 7 6 8 3 4 5
-
- BFS(breadth first search)
- 너비우선탐색
- 큐 사용함. 큐 버퍼 있으면 간단히 설명가능공백 //6 //5 //4 //7 //8 //3 //2 //1 ```cpp #include<iostream> #include<vector> #include<deque> using namespace std; bool visited2[9]; vector<int>graph[9]; void bfs(int x) { deque<int>que; que.push_back(x); visited2[x] = true; while (!que.empty()) { int a = que.front(); que.pop_front(); cout << a << " "; for (int i = 0; i < graph[a].size(); i++) { int y = graph[a][i]; if (!visited2[y]) { que.push_back(y); visited2[y] = true; } } } } int main() { graph[1].push_back(2); graph[1].push_back(3); graph[1].push_back(8); graph[2].push_back(1); graph[2].push_back(7); graph[3].push_back(1); graph[3].push_back(4); graph[3].push_back(5); graph[4].push_back(3); graph[4].push_back(5); graph[5].push_back(3); graph[5].push_back(4); graph[6].push_back(7); graph[7].push_back(2); graph[7].push_back(6); graph[7].push_back(8); graph[8].push_back(1); graph[8].push_back(7); bfs(1); } ``` ```cpp 출력결과 1 2 3 8 7 4 5 6 ```
220209 음료수 얼려 먹기
- 풀이
-
첫번째 노드 선택해서 인접노드 탐색함. 노드가 0인데 만약에 인접노드가 없다? answer에 1더함.
-
인접노드가 있는 경우 순회 통해 어떤 범위까지가 연결됐는지 확인함. (더는 인접노드가 없을 때까지). 이때 탐색된 노드들은 그냥 1로 바꿔버림(이후에 탐색되지 못하게)
-
처리된 노드를 제외한 노드들을 탐색함 1~2의 과정을 반복함
-
이해는 되는데 구현 어떻게 하지?→,,,강의영상 참고함
//1 //1 1 1 //1 //1 //1 //1 1 1 1 1 1 1 1 //1 0 0 0 0
-
- 코드
#include<iostream> using namespace std; int a, b, d; int c[1000][1000]; bool dfs(int i, int j) { if (i <= -1 || i >= a || j <= -1 || j >= b) { return false; } if (c[i][j] == 0) { c[i][j] = 1; //상하좌우 인접한 노드들도 0이면 다 1로 처리해버림 dfs(i - 1, j); dfs(i , j - 1); dfs(i + 1, j); dfs(i , j + 1); return true; } return false; } int main() { cin >> a >> b; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { cin >> d; c[i][j]=d; } } int answer = 0; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { if (dfs(i, j)) { answer += 1; } } } cout << answer; return 0; }
220209 미로 탈출
- 풀이 -_-...
- 역시 세상은 넓고 어려운 문제는 많다.
겉촉속촉