삼성 코딩테스트 - 시뮬레이션

이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다.

 

 

안녕하세요. 최근 1. 알고리즘 지식보단 구현 2. 삼성 코딩테스트에 대한 글도 있으면 좋겠다 라는 두가지 의견이 있어서 삼성 코딩테스트에서 자주 사용되는 구현 스킬들에 대해서 적어보려고 합니다.

우선 삼성 코딩테스트에 어떤 유형이 나오는지 잘 모르시는 분들을 위해 간략하게 설명드릴게요. 삼성에서는 몇년동안 아래 두 유형만 출제하고 있어요.

1. 시뮬레이션
2. 완전탐색

그중 시뮬레이션은 문제에 나온 내용을 그대로 구현만 하면 되는 문제로, 특별한 알고리즘 지식 없이 문제에 나온대로 구현만 잘 하면 풀 수 있습니다. 그리고 그 구현도 사실 몇가지 틀 안에서 나오니 몇가지 자주 나오는 구현 형태를 익히면 비교적 쉽게 풀 수 있습니다.
완전탐색은 dfs, bfs만 알아도 풀 수 있는데 둘 다 사실상 공식처럼 풀리는 문제들이니 이론 익히고 코드 익히고 기출 몇개 풀어보면 시뮬레이션보다도 쉽게 풀립니다.

아무튼 그래서 오늘은 삼성 코딩테스트에서 자주 나오는 구현들을 몇가지 적어보려고 합니다. 특별한 스킬은 아니니 저 사람은 저런식으로 구현하는구나 하고 보시면 될것 같아요.


1. 배열 shift

다음과 같은 정수 배열이 있다고 할게요.

3 5 9 7 1 2

이 배열을 오른쪽으로 한칸씩 밀어보려고 합니다. 단, 가장 오른쪽에 있는 2는 가장 왼쪽으로 옮길게요.

2 3 5 9 7 1

이런건 어떻게 구현할까요?

제가 생각하는 가장 간단한 구현은, 오른쪽으로 민다 -> 오른쪽에서 당긴다로 바꿔서 구현하는겁니다.

왼쪽에서 출발해서 옮기려면 정말 힘들어집니다. 3을 두번째 위치로 옮기기 전에 5를 저장해두고 3을 옮기고, 다시 5를 세번째 위치로 옮기기 전에 9를 따로 저장해두고 5를 옮기고... 저장 공간 두개를 토글링하면서 옮겨야겠네요.

오른쪽에서 수를 당긴다는 생각으로 구현하는건 다음과 같습니다.

3 5 9 7 1 2

가장 오른쪽 2를 따로 저장해둡니다.

3 5 9 7 1 2

1을 오른쪽으로 당겨옵니다.

3 5 9 7 1 1

7을 오른쪽으로 당겨옵니다.

3 5 9 7 7 1

9를 오른쪽으로 당겨옵니다.

3 5 9 9 7 1

순서대로 5와 3도 오른쪽으로 당겨옵니다.

3 3 5 9 7 1

처음에 따로 저장해둔 2를 가장 앞에 넣습니다.

2 3 5 9 7 1

오른쪽으로 민다 -> 역순으로 오른쪽에서 왼쪽으로 이동하며 당겨온다
이런식으로 구현하면 아주 간단해집니다.

코드
temp = arr[n-1];
for(i = n-1; i>=1;i--)
arr[i] = arr[i-1];
arr[0] = temp;

이렇게 1차원에서 미는 구현도 있고, 2차원 사각형 테두리를 도는 문제도 있었는데 다 이런 방식만 생각해서 구현하면 간단합니다.


2. 배열(혹은 vector)에서 항목 하나 삭제

물고기 n마리 중 하나가 시뮬레이션 과정에서 잡아먹히거나 사냥꾼에게 잡힙니다. 혹은 자동차끼리 충돌해서 몇개의 자동차가 사라집니다.
시뮬레이션을 하다보면 자주 나오는 상황이죠. 이런 상황에 잡힌 물고기는 더이상 움직일 수 없으니 시뮬레이션 환경에서 제거해야 합니다. 물고기를 관리하는 배열에서 제거해주면 되겠죠. 이걸 해보겠습니다.

배열 arr에 물고기들이 있습니다. idx번에 있는 물고기를 지우겠습니다.

예를들어 아래와 같은 배열이 있습니다.

3 7 6 2 4

여기서 6을 제거해보겠습니다.(순서는 중요하지 않다고 하겠습니다.)

3 7 2 4(2 3 4 7도 가능합니다.)

이렇게 6이 제거된 배열을 빠르게 구하려고 합니다. 어떻게 할까요?


6을 제거하기 위해 2를 당기고 4를 당기고... 끝까지 당겨오는 방식은 시간복잡도가 O(n)이 되고, 대부분의 경우 시간초과가 나오게 됩니다. 따라서 6만 빠르게 제거해볼건데, 간단합니다.


만약 마지막 항목인 4를 지우려고 한다면 어떻게 했을까요? n만 줄이면 마지막 항목을 인식 못하게 돼서 3 7 6 2만 있다고 판단하겠죠. 마지막 항목은 빠르게 지울 수 있습니다.
그럼 우리가 지우려는 항목을 제일 뒤로 보내면 빠르게 처리할 수 있을겁니다.

3 7 6 2 4

제일 뒤에 있는 4를 6이 있는 위치에 덮어씌웁니다.

3 7 4 2 4

n을 줄입니다.

3 7 4 2

모두를 당겨올 필요 없이 중간에 있는 항목을 빠르게 제거할 수 있습니다.

코드
arr[idx] = arr[n-1];
n--;


당장 생각나는 가장 자주 나오는 구현 두가지만 살펴봤습니다.
사실 시뮬레이션은 이런 구현스킬도 중요하지만 풀이 과정, 습관이 더 중요하다고 생각하는데 이건 어찌 알려드릴 방법이 없네요.. 나중에 방법을 생각해볼게요. 문제 풀이 과정을 보여드리는게 제일 확실한데 라이브코딩을 할수도 없고 애매해요.

생각해보면 여기저기 검색해봐도 알고리즘 내용은 많은데 구현에 대한건 그리 많지 않아서 시뮬레이션 준비하는게 쉽지 않겠네요. 삼성 코딩테스트 문제 몇개 오랜만에 다시 풀어보고 조만간 자주 나오는 구현에 대해 다시 한번 적어보도록 할게요.
늘 읽어주셔서 감사합니다!