[강의]백준 알고리즘 3회차
문제
큐빙(5373, 시뮬레이션)
- 늦어서 제대로 수업을 못들었다 ^_ㅠ,,,
- 삼전 기출, 풀어볼 것
- 연습만이 살길이다? ㅎ;
인구이동 (16234,DFS, BFS)
- N*N 배열(N<=50)
- 국경선이 열리는 조건(L<=국경을 공유하는 인구의 차이<=R)
- (1<=L<=R<=100)
- 가능한 국경선을 모두 연 뒤 인구이동을 진행하고 그 횟수를 구하는 문제
문제1. 어떤 나라들 간에 국경선이 열리는가
BFS에서 이동할 수 있으면 사실 국경선이 열린 것으로 볼 수 있다. 이후 연합의 인구수를 구한다.
즉, L이상 R이하의 차이를 유지한 상태로 최대한 멀리가는 방법을 구하는 문제로 생각하면 된다. 최소를 구하는 것이 아니므로 DFS/BFS 아무거나 만들어도 된다.
TIP: 인구인동을 완료한 뒤 방문했던 나라들의 인구를 변경해줘야 하므로 stack 등의 자료구조(그냥 2차원배열 써도 돼)를 이용하여 방문했던 나라를 저장해 놓는게 좋다.
나무 재테크(16235, 시뮬레이션)
- N*N 배열, (N<=10, M<=N^2)
- M개의 나무가 있으며 각자 나이가 있다.
- 한 칸에 여러그루의 나무가 존재할 수 있다.
- 한 칸에 양분이 5있다.
- 1년 동안 아래의 행위가 반복되며 K년이 지난 후 살아있는 나무의 문제를 구한다.
-
봄: 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다. 하나의 칸에 여러 나무가 있다면 어린 나무부터 양분을 먹는다. 양분이 부족한 나무는 즉시 죽는다.
-
여름: 봄에 죽은 나무가 양분으로 변한다. (추가 양분 = 나이/2)
-
가을: 나이가 5의 배수인 나무가 번식하고 인접한 8칸에 나이가 1인 나무가 생긴다.
-
겨울: 땅에 양분이 추가된다(R,C)에 추가되는 양분은 INPUT으로 주어진다.
풀이1. 문제를 천천히 쪼개서 푼다고 생각한다.
- 각 칸에 들어있는 나무를 소팅한다.
- 죽은 나무를 처리하기 어려우므로 temp배열을 하나 이용했다.
- 나중에 생길 나무를 저장하기 위한 p배열도 따로 하나 있다. (문제를 풀다보면 부딪힐 문제들)
TIP: 시뮬레이션 문제를 풀다보면 동시에 처리해야 하는 일이 많은데 코드는 동시에 처리하지 못해서 temp를 써야하는 경우가 빈번하다. 톱니바퀴(https://www.acmicpc.net/problem/14891) 같은 문제가 포함된다.
아기상어(16236, 시뮬레이션, BFS)
- N*N 공간에 물고기 M마리, 아기상어 1마리가 있다 (N<20)
- 한 칸에는 물고기가 최대 1마리 존재한다.
- 상어와 물고기는 크기를 가진다.
등등… 조건을 이용해 지나야 하는 칸의 개수의 최소값을 구해야 한다.
- 정답, 상어의 크기, 지금까지 먹은 물고기의 수 등을 저장해야한다.
- 거리가 가장 가까운 물고기를 알아야 하므로 BFS를 돌려 소팅해 놓는다.
삼성꿀팁
위 네 문제는 2018년 삼성 기출문제이다. 요즘은 난이도가 좀 오른듯. 시뮬레이션/BFS가 아니라 어려운 시뮬레이션/시뮬레이션 + BFS 형태이다.
13460, 12100, 3190, 13458 (요즘스타일 X) 15685, 5373 (어려운 시뮬레이션, 드래곤커브는 재귀이용)
TIP: test_case 형태의 문제는 초기화를 신경써줘야 한다. 그러나 초기화도 시간이 걸린다. bool이 아닌 int형태의 배열을 사용하여 test_case값을 활용하면 안해도 될 수도 있음.(최후의 수단)
숨바꼭질 5(17071, DFS)
- 수빈 위치(N), 동생 위치(K)
- 0 <= N,K <= 500,000
- 수빈이가 동생을 찾는 최소시간은?
- 수빈이의 행동(X -> 2X, X+1, X-1)
- 동생의 이동 K->K+1->K+1+2->…
BFS는 방문했던 정점은 다시 가면 안된다. 그러나 이 문제는 같은 칸을 여러번 반복해서 방문할 수도 있어서 DFS를 사용해야 한다…?
풀이1. 그러나, 동생의 위치는 정해져 있으니 동생이 이동할 때마다 BFS를 사용하면 가능은하다. (TIMEOVER, 불가능)
풀이2. BFS를 이용하는데, 어떤 정점에 홀수 시간에 도착한 경우, 짝수 시간에 도착한 경우로 나누어서 최소 시간을 구해야 한다
핵심아이디어! 이미 동생이 x에 올 수 있다는 것을 알 수 있고 내가 x를 지나왔다면 2초 단위로 +1, -1을 반복해서 x에서 만날 수 있다. (대신 홀수, 짝수로 나누어야함)
파이프 옮기기1 (17070, 브루트포스)
- 파이프가 2칸을 차지하는데 한 칸만 차지한다고 생각해서 문제를 단순화시킬 수 있다…. (잘이해안됨)
- 이를 위해 재귀함수에서는 앞의 위치(x,y), 방향(dir) 세 가지 정보를 필요로 한다.
- 가능한 방법의 수가 1,000,000 이하이므로 브루트포스가 가능하다.
파이프 옮기기2 (17069)
- 브루트포스 방법이 불가능한 문제이다.
- 이동방법 = 2^2N-2 정도 나온다. 2^20을 넘어서므로 Timeout 날 걸?
- 그러나 파이프 옮기기1를 조금만 수정하면 풀 수 있다.
풀이1. DP(Dynamic Programming)
- 파이프 옮기기1의 DFS 함수는 (x,y) -> (n-1, n-1)로 가는 방법의 수를 구하는 함수였다.
- (0,1) -> …(x,y)…. ->(n-1, n-1) 이라고 보자.
- 메모이제이션을 이용 (앞에서 어떤 일이 벌어졌든간에 답이 같기 때문에 답을 저장해 둔 뒤 다시 이용한다.)
- 한 번(x,y,dir) 함수를 실행했으면 배열에 답을 저장해 둔 뒤 재이용
괄호 추가하기(16637)
- 길이가 N인 수식(N<=19, 홀수)
- 정수 0~9, +, -, x만 이용 (연산자 우선순위는 모두 같다)
- 단, 괄호가 추가되면 괄호 안의 연산이 우선이다.
- 괄호 안에는 연산자가 하나만 있어야한다.
- 괄호는 중첩이 불가능하다.
- 괄호를 적절히 추가해서 만들 수 있는 결과의 최대값은?
괄호 추가하기2(16638)
- 길이가 N인 수식(N<=19, 홀수)
- 정수 0~9, +, -, x만 이용 (연산자 우선순위는 곱하기가 높다)
- 단, 괄호가 추가되면 괄호 안의 연산이 우선이다.
16985, 16986
A형 문제수준(1)
http://www.secmem.org/blog/2019/03/07/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%ED%8A%B9%EA%B0%95/
16987, 16988
A형 문제수준(2)
http://www.secmem.org/blog/2019/03/07/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%ED%8A%B9%EA%B0%95/
댓글남기기