SW 역량 테스트 준비 - 기초

2 분 소요

문제 목록 : https://code.plus/course/32
풀지 않았던 문제들만 풀어보며 기록했습니다.

그래프와 BFS

BOJ 13023: ABCDE

Link : https://www.acmicpc.net/problem/13023

solution

문제 설명만 읽고 예제로 뛰어들었는데 예제 1번 말고는 이해가 잘 안갔던 문제.
모든 노드가 옆의 노드와 이웃되있는지 확인하면 되는줄 알았는데, 이 조건이면 예제를 통과하지 못한다.
각 간선을 돌면서 연결된 노드가 새로운 노드인지 카운트해야 한다. 5가 되는 순간 답을 만족한다. (ABCDE)
간편하게 돌기 위해 DFS를 이용한다.

BOJ 11724: 연결 요소의 개수

Link : https://www.acmicpc.net/problem/11724

solution

서로 연결되있는 노드를 하나로 묶었을 때, 묶음 개수를 출력하는 문제다.
무방향 그래프이기 때문에 먼저 각 노드에 간선을 추가해준다.
DFS를 통해 연결되있는 노드를 모두 방문하고 이미 방문한 노드는 chk[]를 이용해 방문하지 않도록 한다.
DFS가 실행되는 횟수가 답이 된다.

BOJ 1707: 이분 그래프

Link : https://www.acmicpc.net/problem/1707

solution

기준이 되는 노드가 있을 때 이 노드의 색깔을 0이라 하자.
그럼 이 노드와 인접한 노드들의 색깔은 1이어야 이분 그래프 조건을 만족한다.
여기서 인접했다는 말은 두 노드를 연결하는 간선이 존재함을 의미한다.
1~N번의 노드가 모두 연결돼 있는줄 알고 dfs()를 한 번만 돌렸는데, 주의해야한다.
dfs()를 한 번 돌리면 그 노드로부터 이동할 수 있는 모든 점에 대해 색을 업데이트 할 수 있지만
이동할 수 없는 점이라면 업데이트가 되질 않는다. 그래서 업데이트 안 된 모든 점은 dfs()를 돌려줘야 한다.
이 문제는 DFS, BFS로 풀 수 있다. 개인적으로 BFS가 더 직관적이라 생각한다.

BOJ 13549: 숨바꼭질 3

Link : https://www.acmicpc.net/problem/13549

solution

BFS로 풀 수 있다.
목적지 k까지 가는데 드는 최소 시간을 구해야 하는데, +1, -1은 1초가 걸리지만 2배 이동할 때는 0초가 걸린다.
따라서 2배 이동할 때를 우선 순위로 두어야 한다. BFS는 목적지에 도달하면 바로 중단하기 때문이다.
우선순위를 고려하지 않고 연산을 하고 싶다면 갱신되는 값이 현재 값보다 작을 때 push를 하도록 조건을 추가하자.
예) \(a[cur - 1] > a[cur] + 1\)

BOJ 1261: 알고스팟

Link : https://www.acmicpc.net/problem/1261

solution

BFS, 다익스트라 등의 방법으로 풀 수 있다.
코드 플러스에서 BFS로 분류 돼있어 BFS로 풀었는데 그냥 큐를 사용하고 풀지를 못하겠어서 우선순위 큐를 이용했다.
이동하려는 위치에 벽이 있으면 cost가 1씩 증가하고 없다면 증가하지 않는대로 큐에 넣었으며
당연히 cost가 가장 작은 것부터 처리할 수 있도록 기준을 잡았다.
우선순위 큐를 이용한다면 전체적인 코드는 거의 변하지 않는다.

BOJ 3055: 탈출

Link : https://www.acmicpc.net/problem/3055

solution

BOJ 4179: 불!과 거의 유사한 문제다.
주의할 점은 물이 여러개일 수 있고 같은 시간에 물이 이동하는 자리에는 고슴도치가 이동하지 못한다는 점이다.
때문에 물을 먼저 큐에 넣어주고 시작하면 편하게 처리할 수 있다.
그리고 비버의 굴은 물로 막히지 않는다. 예외 처리를 해줘야 한다.

다이나믹 프로그래밍

BOJ 11726: 2×n 타일링

Link : https://www.acmicpc.net/problem/11726

solution

DP 기본 유형.
블럭이 2x1, 1x2만 있으므로 다음의 점화식을 만족한다.
\(f(k) = f(k-1) + f(k-2)\)

BOJ 15988: 1, 2, 3 더하기 3

Link : https://www.acmicpc.net/problem/15988

solution

BOJ 9095: 1, 2, 3 더하기에서 범위가 늘어난 버전이다.
답이 매우 커질 수 있으므로 모듈러 연산을 하도록 되어있는데..
곳곳에 모듈러를 걸어줘도 int형에서는 오버플로우가 나서 long long으로 바꿔줬다.
점화식은 여전히 똑같고 간단하다.
\(f(k) = f(k-3)+f(k-2)+f(k-1)\)

BOJ 16194: 카드 구매하기 2

Link : https://www.acmicpc.net/problem/16194