이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.
● DFS
깊이 우선 탐색
스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다.
정해진 순서는 없다.
재귀함수를 이용하면 스택을 이용하지 않아도 된다.
인접행렬 사용시, 시간복잡도는 모든 정점 방문 & 하나 방문시 모든 정점과 연결 여부 검사
즉, O(V^2) = 모든 정점 방문(V) * V번 검사
인접 리스트로 구현시, 연결된 정점만 검사하기 때문에 차수를 모두 더한 것과 같다.
따라서 O(V+E)가 된다.
● BFS
너비 우선 탐색
큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식 (큐에 넣을 때 방문했다고 체크)
한 정점에서 갈 수 있는 정점을 다 가는 것.
큐에 넣을때마다 방문했다고 체크하고, 꺼낼 때마다 연결되어있는 정점을 체크한다.
시간복잡도는 DFB와 같은 이유로
인접행렬은 O(V^2)
인접리스트는 O(V+E)
▲ 연결요소
그래프가 하나일때, 다 연결되어있지 않을떄 즉, 나누어져 있을때, 나누어진 각각의 그래프를 연결요소라고 한다.
▲ 이분 그래프
그래프를 각각 A와 B로 나누었을 때, 각각 A와 B에 포함되어 있는 정점끼리 연결된 간선이 없을 때, 이를 이분 그래프라 한다. DFS 또는 BFS 탐색으로 이분그래프인지 아닌지 알아볼 수 있다.
문제
△ 단지번호붙이기
문제 : 정사각형 모양의 지도가 있다. 0은 집이 없는곳, 1은 집이 있는 곳 단지에 번호를 붙이려고 한다. 각 단지수를 출력하고 각 단지에 속하는 집의 수를 출력하는 문제.
방법
DFS, BFS 둘다 풀 수 있다.
BFS로 풀면, 시작점 넣어주고 (x, y) -> (nx, ny)가 된다 치면
dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]
시작점에서 인접한 4개 점 다 검사. 검사해서 1인제 방문하지 않았으면 똑같이 검사
△ 미로 탐색
문제 : (1, 1)에서 (N, M)으로 가는 가장 빠른 길을 구하는 문제
미로찾기는 BFS라 보면 된다. '최소'면 BFS.
● BFS
BFS를 이용해 해결할 수 있는 문제는 다음과 같은 조건을 만족해야 한다.
1. 최소 비용 문제
2. 간선의 가중치가 1
3. 정점과 간선의 개수가 적어야 한다. (조건에 맞춰서 문제를 해결할 수 있을 정도로)
- 간선의 가중치 = 문제에서 구하라 하는 최소 비용의 의미
문제
△ 숨바꼭질
문제 : 수빈이와 동생의 위치가 주어졌을 때, 동생을 찾는 가장 빠른 시간(=최소 시간)을 구하는 문제.
수빈이가 할 수 있는 행동
- 걷기 : X-1, X+1
- 순간이동 : 2*X
방법
큐에 시작점 push
해당 점에서 이동할 수 있는 모든 점 살펴보기 (X-1, X+1, 2*X)
방문 할 수 있는 모든 점 큐에 넣어주고 차례때로 방문 & 거리 계산
현재 -> 다음 일때, 거리+1
△ 숨바꼭질 4
같은 문제인데 이건 이동하는 방법, 즉 경로를 구하는 문제
현재 -> 다음 으로 넘어갈때 거리 계산할 때 이전 경로를 기록해 주면 된다.
△ 이모티콘
화면의 이모티콘은 1개
할 수 있는 연산은 3가지
- 화면의 이모티콘을 모두 복사해 클립보드에 저장
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
- 화면에 있는 이모티콘 중 하나를 삭제
S개의 이모티콘을 만드는데 걸리는 시간의 최소값을 구하는 문제
방법
시간의 최소값을 구하므로 BFS
ex) 화면의 이모티콘이 9개라면 될 수 있는 경우는 8개, 18개, 17개
but, 저 3개가 동시에 될 수는 없다. 왜냐하면 클립보드에 있는 이모티콘의 숫자를 모르기 때문
정수 하나를 더 사용해 클립보드를 나타내는 데에 쓰면 된다.
pair<화면, 클립보드>라 하면
① (s, c) -> (s, s)
② (s, c) -> (s+c, c)
③ (s, c) -> (s-1, c)
△ 숨바꼭질 3
다 똑같은데 순간이동의 가중치가 0이다.
거리가 증가하지 않으면 앞에 넣고, 증가하면 뒤에 넣는다.
△ 알고스팟
문제 : (1, 1)에서 (N, M)으로 가는 경로 중에 벽을 부술 수 있다. 벽을 최소몇개를 부술 수 있는가?
벽을 부수는 횟수의 최소값 : BFS
빈칸으로 이동하는 경우 와 벽을 부수냐 여부
● 트리
그래프인데 사이클이 없는 연결그래프
정점이 V개면 간선이 V-1개다
그럼 만약 정점이 V개, 간선이 V-1개면 트리일까? 아니다. 사이클이 없어야 한다.
○루트가 있는 트리
트리에 루트가 있으면 부모 자식 간의 관계를 같는다.
루트부터 아래로 방향을 가질 수 있다.
부모, 자식,
자식이 없는 노드 : Leaf Node, Terminal Node
깊이 : 루트에서부터 거리
높이 : 깊이 중 가장 큰 값
조상 : 위로 가면서 만날 수 있는 모든 노드
자손 : 아래로 가면서 만날 수 있는 모든 노드
★ 이진트리
자식을 최대 2개만 가지고 있는 트리
- 포화 이진트리 : 리프 노드를 제외한 노드의 자식 수가 2
- 완전이진트리 : 포화 이진트리에서 마지막 레벨의 노드가 몇개 없을 수도 있음
§ 트리의 표현
1. 인접리스트에 트리의 부모만 저장하는 방식으로 표현★★
2. 완전이진트리의 경우에 배열로 표현 가능
- 부모가 x면 왼쪽 자식은 2x, 오른쪽 자식은 2x+1
- 부모와 자식 둘다 구할 수 있다.
- 왼쪽 자식, 오른쪽 자식 각각 짝수 홀수
- 부모는 자식을 2로 나누면 된다.
단점 : 완전이진트리의 경우에만 쓸 수 있다.
§ 트리의 순회
프리오더 : 노드 -> L자식 -> R자식 (부모가 의미를 가지면)
인오더 : L자식 -> 노드 -> R자식 (사용할 일 거의 없음. BST에서 삭제 구현할 때)
포스트오더 : L자식 -> R자식->노드 (자식이 의미를 가지면)
§ 트리의 탐색
DFS/BFS 알고리즘을 이용해 탐색할 수 있다.
트리는 사이클이 없는 그래프이기 때문에 임의의 두 정점 사이의 경로는 1개다.
§ 트리의 지름
트리의 모든 경로 중에서 가장 긴 것의 길이를 트리의 지름이라 한다.
구하는 방법
1. 한 정점 s에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼거리를 u라고 한다.
2. u에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼거리인 정점 v를 구한다.
d(u, v)를 u와 v 사이의 거리라 했을 때, s(u, v)가 트리의 지름이다.
BFS(연습) 문제
△ 연구소
문제 : NxM 크기의 직사각형 지도가 있고, 1x1 크기의 칸으로 나누어져 있다. (3≤N, M≤8)
일부 빈칸에는 바이러스가 있고, 인접한 빈칸으로 계속해서 퍼져 나간다.
브루트포스+BFS 문제
벽을 3개 세우는 시간 (NM)^3, N*M개의 칸에서 3개를 골라야 하므로.
BFS/DFS하는 시간. 최악의 경우 모든 칸을 다 둘러봐야 하므로 (NM)
시간복잡도는 O(NM)^4) = (64)^4=16777216. 시간내로 풀 수 있다.
'공부 > 백준 2020년 1~2월 알고리즘' 카테고리의 다른 글
7번째 수업 (0) | 2020.01.29 |
---|---|
6번째 수업 (0) | 2020.01.23 |
4번째 수업 (0) | 2020.01.19 |
3번째 수업 (0) | 2020.01.15 |
2번째 수업 (0) | 2020.01.11 |