티스토리 뷰

백준(C++)/STL

코딩테스트 문제 유형 정리

devhater 2023. 8. 13. 16:03

코딩테스트를 준비하면서, 알고리즘 유형을 정리해놓은 글이다. 계속해서 공부하면서 업데이트할 예정이다.

대부분, 바킹독님의 알고리즘 강의를 참고하였다.

1. BFS

중요도 : ★★★★★

사용한 STL : pair, tuple, queue, max

BFS 유형은 크게 다섯가지가 있다. 

1. Flood fill

영역의 넓이를 구하는 유형이다. DFS로도 구현 가능하지만, BFS가 훨씬 더 유용하므로 굳이 DFS로 구현할 필요는 없다.

https://www.acmicpc.net/problem/1926

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

2. 미로찾기

도착점까지의 최단거리를 구하는 것이다. DFS로는 구현 불가하다. dist배열을 만들어서, BFS가 방문한 점은 최단 거리임을 이용하는 문제이다.

https://www.acmicpc.net/problem/1926

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

3. 시작점이 여러개

1번,2번은 시작점이 한 개인 경우이다. 하지만 BFS는 시작점이 여러개여도 문제없이 작동한다. 이 점이 굉장히 유용하므로, 꼭 알고 넘어가도록 하자.

https://www.acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

4. 시작점이 여러개, 그러나 다른 하나가 일방적으로 영향을 미치는 경우

시작점이 여러개이지만, 다른 하나가 일방적으로 진로를 방해하는 경우이다. 서로 진로를 방해하는 경우도 있겠지만, 아직 문제를 접해본 경험이 없다.

https://www.acmicpc.net/problem/4179

 

4179번: 불!

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자

www.acmicpc.net

5. 1차원일 때의 BFS

보통 BFS는 2차원이라고 생각하겠지만, 1차원일때도 유효하다. 만약 1차원인데, 시간복잡도가 엄격한 문제일 경우, BFS방법을 떠올리는 것도 나쁘지 않다.

https://www.acmicpc.net/problem/1697

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

저작자표시 (새창열림)

'백준(C++) > STL' 카테고리의 다른 글

[C++ STL] List  (0) 2023.07.14
[VS2022] #include<bits/stdc++.h> 사용하기  (0) 2023.07.13