기술면접을 위해 기초 CS에 대한 복습중이다.
공부한 내용 중 요점이나 나중에 기억해야할 부분을 정리해보려고 한다.
내가 아는 부분은 생략되어 있을 수 있고, 혹여나 틀린 부분이 있을 수도 있으니 이 글을 보고 '다른 사람'이 공부하기에는 도움이 되지 않을 수 있으니 주의!
Stack in C++
stack<int> s; // 선언
s.push(5); // 5를 push
s.top(); // 최상단 원소
s.pop(); // 5를 pop
Queue in C++
queue<int> q; // 선언
q.push(5); // 5를 push
q.front(); // 가장 먼저 들어온 원소
q.pop(); // 5를 pop
재귀함수 (Recursive)
- stack처럼 가장 나중에 호출된 recursive 함수가 가장 먼저 종료된다.
- 팩토리얼 구하는 게 가장 대표적인 recursive 함수다.
- GCD(최대공약수) 구하는 것도 재귀함수다.
- 점화식으로 구할 때 주로 이용된다.
DFS (Depth-First Search)
- Stack(혹은 recursive)을 이용해서 깊이 우선으로 탐색
- 방문처리 표시할 bool 배열과 그래프 리스트들의 배열이 필요하다.
bool visited[9]; vector<int> graph[9];
- 기본 알고리즘(Stack)
- 탐색 시작 노드를 stack에 push하고 visit 처리한다.
- stack 최상단 노드에 방문하지 않은 노드가 있으면 그 노드를 push하고, 없다면 pop한다.
- 더이상 2번을 할 수 없을 때까지 반복한다.
- 기본 알고리즘(Recursive)
- 현재 노드 x를 visit 처리한다.
- 현재 노드에 연결된 다른 노드, graph[x]를 재귀적으로 방문한다.
void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
cout << x << ' ';
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) dfs(y);
}
}
BFS (Breadth-First Search)
- 기본 알고리즘
- 탐색 시작 노드를 q.push()하고 visit 처리한다.
- q.pop()을 하고, 방금 q.front에 해당했던 노드의 인접 노드 중 방문하지 않은 노드를 모두 push하고, visit 처리한다.
- 더이상 2번을 할 수 없을 때까지 반복한다.
void bfs(int start) {
queue<int> q;
q.push(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.empty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.front();
q.pop();
cout << x << ' ';
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if(!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
문제해결 아이디어
- 연결된 그래프 관련 문제는 DFS나 BFS로 풀면 된다.
- DFS는 모든 경로를 방문해야 할 경우에 적합하다.
- 경로의 특징을 저장해야 할 때 (BFS는 경로의 특징이 없음)
- 검색 대상 그래프가 정말 클 때
- BFS는 최소비용이 중요할 때 적합하다.
- 미로 찾기, 최단 거리 구할 때
- 검색 대상 규모가 크지 않을 때
참고한 사이트
- 나동빈님 유튜브: 이코테 2021 강의
- 나동빈님 Github: 이코테 소스코드 저장소
'Study note > Coding test' 카테고리의 다른 글
DP - Dynamic Programming (0) | 2024.04.12 |
---|---|
Binary Search (0) | 2024.04.12 |
그리디 & 구현 (0) | 2024.04.12 |
코딩 테스트에서 주의할 점 (1) | 2024.04.12 |
정렬 알고리즘(Sort) (0) | 2024.04.12 |