코테 최빈 기출
코딩테스트에 밥먹듯이 나온다는 그 유형이다.
대부분의 문제는 이중배열 격자를 주고, 그 안을 전부 탐색하면서 답을 찾는 문제인데 이중배열이라 함은 보통 O(n^2)의 시간복잡도를 가지기때문에, 이를 잘 해결해야하는 문제이다.
대표 유형 몇가지를 살펴보도록 하겠다.
현재 유료 사이트의 문제를 보고있어서 문제를 직접 올릴 수는 없다. 나중에 백준이나 프로그래머스에서 찾으면 올려보도록 하겠다 .
특정 범위내의 1 갯수
n*n 격자에 1과 0 이 있고 특정 크기의 사각형이 움직이면서 최대로 1을 가지는 경우를 측정하는 문제유형이 있다.
이러한 문제유형은 완전탐색 과정에서 범위밖으로 나가지 않도록 확인해야한다. 이러한 확인을 수행할떄 3가지 정도의 방법이 있는데
- inRange 함수를 사용
int inRange(x, y) {
return 0 <= x && x < n && 0 <= y && y < n;
}이러한 함수를 통해 범위안에 있을때만 작동하게 하거나,
- 사각형의 크기만큼 루프를 덜 돌거나
// 에를 들어 3*3 사이즈의 정사격형이라면, x y 전부다 -3 씩만 루프를 돌아도 된다.
- 루프를 전부 돌면서 만약 범위 밖이라면 돌려주는 코드를 작성하면 된다.
2번이 시간소요는 제일 적게 되겠지만, 어차피 큰 차이는 없을거고 실수할 여지가 많긴한다.
직사각형 크기가 없다면?
만약 직사각형의 크기가 주어지지 않고 가능한 제일 큰 직사각형을 구하라는 문제가 나온다면 기존의 풀이법은 통하지 않는다. 이런 경우에는 직사각형의 양 꼭지점을 정하고, 그 안에 값들이 전부 양수인지 판단하는 방식이 필요하다.
격자안에서 밀고 당기기
격자안에서 특정 숫자가 밀려나고 다음숫자가 오고 그러한 문제이다. 이는 밀려나는 해당 줄만 따로 분리해서 실행하고 다시 배열에 넣어주는 방식으로 하면 된다.
컨베이어 벨트 문제나 Run-length 인코딩문제등이 있을 수 있다.
실수만 없다면, 종이에 그려가면서 안정적으로 풀 수 있는 문제이다.
격자안에서 터지고 중력에 의해 떨어지기
테트리스같은 문제이다. 이도 전 문제와 비슷하게 풀면 되는데 우선 터지는 구간을 dx dy로 처리해서 다 0으로 바꿔주고
왼쪽 1열부터 아래에서 위로 올라가면서 아래가 0이면 숫자를 아래로 떨어트리고 해당자리를 0으로 바꿔주면서 중력을 구현하면 된다.
이 문제는 이중배열을 하나 더 만들어서 그쪽에 답을 써내려가면서 푸는것이 맞는 풀이법이라 할 수 있다.
폭탄의 위치가 없는 경우
이 경우 최적의 폭탄을 찾으려면 완전탐색을 해야한다.
각 좌표마다 하나의 케이스라고 생각하고 한번씩 돌려가면서 터트리고 이를 기록한다음 다음번에 또 터트리기전에 초기화 해야한다.
격자안에서 단일 객체의 이동
격자안에서 조건(숫자가 가장 크거나, 동서남북 순서로 가장 크거나)에 따라 계속 이동하면서 풀어야하는 문제이다.
dxdy 테크닉을 이용해서 이동을 하면 되는 문제이다.
여려워 보이지만 사실 그렇게 어렵지는 않으나, 초기조건 dx dy 설정을 잘 해야 오류없이 깔끔하게 풀 수 있다.
격자안에서 여려 객체의 이동
위의 문제와 유사한데, 이번에는 여러객체가 동시에 이동하고, 조건에 따라 서로 겹치면 합쳐지거나 사라지는 그런 문제이다.
이 문제는 빈 배열을 만들고 이동한 객체의 정보를 해당 배열에 기록해야한다. 그리고 그 배열을 검사해서 조건에 맞는 처리를 한다 (지우거나 합치거나). 그 후 배열을 초기화 하고 다시 이를 반복하는 문제이다.
배열을 초기화하지 않으면 이전의 값들이 남아서 오류가 발생할 수있다.
여러 구슬의 이동문제
무게정보, 순서등이 기록되어 있어서 기존의 방식대로는 풀기 어려운 문제이다.
접근방법으로는
- 이중배열을 만들어서 그 안에 구슬의 정보를 저장하고 이동을 구현하면서 조건에 맞춰서 푸는 방법
파이썬의 경우 이렇게 푸는게 쉬운것같다.
- 빈 이중배열을 만들고, 구슬위치의 이중배열안에 해당 구슬의 정보를 저장하고 계속 갱신하는 방법
총 두가지 방법이 있다.
시뮬레이션
이러한 완전탐색 시뮬레이션은 문제를 내기가 좋아서 그런지, 자주 나온다고 하니 유형을 몇가지 암가히고 푸는것도 좋다고 생각된다.
