ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • SW 역량테스트 기출 문제집 분석
    알고리즘/acmicpc 2017. 4. 21. 20:12

    백준 온라인 저지에서 삼성 SW 역량테스트 기출 문제집을 발견 했다. 분명히 시험시간에 감독관이 외부에 유출하지 말라고(말아달라고) 했을 텐데 싸트 문제처럼 이것도 외부 유출은 막을 수 없나 보다. 재미 삼아 여기 있는 문제들을 한 번 풀어 봤는데 문제들이 공통적으로 뚜렷한 경향이 있었다. 이번 포스트에서는 (문제집에 올라온 기출 문제들이 모두 사실이라는 전제 하에) 기출 문제를 분석하고 취준생 입장에서 어떻게 준비하는 것이 좋을 지를 정리 해봤다.


    기출 문제 분석


    1. 시뮬레이션 문제가 대부분


    대부분의 문제들이 고급 알고리즘 없이도 풀 수 있다. 여기서 고급 알고리즘은 다익스트라나 최소 스패닝 트리 같이 대학교 알고리즘 강의에서 배우는 내용들을 말한다. 물론 기출로 나온 문제들을 고급 알고리즘을 적용한다면 좀 더 빠르게 풀 수도 있을 것이다. 하지만 문제의 조건으로 주어지는 N값이 작기 때문에(대부분의 문제가 100 이하로 주어진다) 적용한 알고리즘이 O(N^2)이든 O(N^3)이든 중요치 않다. 모든 경우에 대해서 탐색 할 수 있도록 코드를 작성 할 수 있으면 시간 초과 없이 맞출 수 있는 문제다.


    2. 구현이 까다롭다.


    그러나 실수하기 딱 좋은 조건들만 문제에 나왔다. 알고리즘 문제를 많이 풀어본 사람들도 지도 유형의 문제를 까다로워 하는데 여기 서는 거기에 한 술 더 떠서 지도를 회전시키고 기울이기까지한다. 싸트를 생략하는 대신 여기서 공간 능력을 테스트 해보려는 의도인지 모르겠으나 단순 구현이라고 하기엔 머리가 좀 아프다. 문제 자체는 이해하기 쉽고 풀이법도 빠르게 떠오르는데 막상 손을 대려면 소소한 조건들을 구현하는 것이 난감하고 어찌어찌 구현을 해내면 예상치 못한 예외 케이스들이 나와 디버깅 하는데 시간을 다 쓰게 된다. 실제로 13460 문제를 집에서 한 번 풀어봤는데 세로/가로 크기가 10이하인 것을 캐치해 모든 경우에 대해서 시뮬레이션 하는 것으로 방향을 잘 잡았으나 '빨간공/파란공이 인접했을 때 움직임을 어떻게 구현 할 것인가'를 놓고 꽤 고민했고 또 예상치 못한 케이스를 해결하는데 시간을 오래 썼다. 만약 시험장에서 긴장과 압박감 속에서 풀어야 했다면 결코 쉽지 않았을 것 같다.



    어떻게 준비하는 것이 좋을까?


    기출 문제들로만 미루어 봤을 때 여기선 '똑똑하지 않아도 구현은 제대로 할 줄 아는 프로그래머'를 원하는 것 같다. 구현하기 까다로운 문제들을 실수 없이 빠르게 구현해내기 위해선 자신만의 코딩 스타일을 가지는 것이 중요하다. 시험장에서 배열의 인덱스를 0에서부터 시작 할 지, 1에서부터 시작할지나 지도상의 동서남북 탐색 방법을 구현하는 것을 어떤 식으로 구현할 지 고민하면 너무 늦다. 문제의 다양한 조건들을 어떻게 대처 할 것인지 미리 훈련이 되어 있어야 되도록 실수 없이 한 번에 구현 할 수 있어야 한다.


    1. 나만의 코딩 스타일을 가지기


    글쓴이는 로봇 청소기 문제에서 회전 방법과 각 방향 별로 전진, 후퇴를 아래 코드로 구현 했다.


     
    int dir_r[4] = { -1, 0, 1, 0 };
    int dir_c[4] = { 0, 1, 0, -1 };
    int process(int r, int c, int dir) {
    
    	int cnt = 0;
    	int befo_r = -1, befo_c = -1;
    	int ret = 0;
    
    	while (1) {
    
    		....
    
    		int turn_dir = (dir - 1 + 4) % 4;
    
    		// turn left,,,
    		if (r + dir_r[turn_dir] >= 0 && r + dir_r[turn_dir] < R &&
    			c + dir_c[turn_dir] >= 0 && c + dir_c[turn_dir] < C) {
    
    			int exist = 0;
    
    			if (map[r + dir_r[turn_dir]][c + dir_c[turn_dir]] == 0)
    				exist = 1;
    
    			if (exist) {
    				dir = turn_dir;
    				r += dir_r[turn_dir];
    				c += dir_c[turn_dir];
    				continue;
    			}
    			else
    				dir = turn_dir;
    		}
    		else
    			dir = turn_dir;
    
    	}
    
    	return -1;
    }
    


    dir_r, dir_c 변수는 북,동,남,서 방향 별로 전진 할 시 변경해야 하는 행과 열의 변화 값을 갖고 있다. 현재 방향만 알면 앞으로 이동하게 되는 위치 값을 쉽게 표현 할 수 있게 된다(물론 뒤로 후퇴하는 것까지 가능!). 그리고 북,동,남,서의 순서는 각각 오른쪽으로 회전하는 순서다. 이는 곧 순서를 반대로만 하면 왼쪽으로 회전 하는 것까지 쉽게 표현 할 수 있다. turn_dir 변수에 왼쪽으로 회전하는 경우의 방향 값을 저장 해뒀다.


    물론 위 방법이 최선이라고 할 수는 없다. 다만 나는 위 방식으로 구현할 때 가장 빠르고 실수도 없다. 각자 자신에게 익숙한 방식으로 구현 할 때 실수를 줄일 수 있다.


    물론 실무에서는 자신만의 코드 스타일로 코드를 짤 경우 리뷰 받을 때는 상당히 피곤한 코멘트를 받게 되겠지만... 일단 합격을 해야 리뷰를 받을 수 있으니 자신이 최대한 실수 하지 않도록 훈련을 해두자.


    2. 척박한 디버깅 환경에서 연습하기


    코드 스타일을 만드는 것 뿐만 아니라 평소에 좋은 디버깅 툴을 되도록 사용하지 않는 훈련을 하는 것도 중요하다. 시험 볼 때는 비주얼 스튜디오를 사용하고 거기에 있는 모든 디버깅 기능들을 사용 할 수 있다고 하니 사용 방법만 알아두고 평소에는 되도록 사용하지 말자. 육상선수가 모래주머니를 달고 훈련 하는 것과 비슷하다고 할까, 되도록 원하는 코드를 한번에 구현 하는 연습을 해보는 것이 좋고 예상한 결과 값이 나오지 않더라도 자신의 코드에서 논리적으로 유추해서 파악하는 것이 중요하다. 처음에는 힘들지만 계속 해보면 자신이 어느 부분에서 반복적으로 실수하는 지 알 수 있고 고칠 수 있다. 글쓴이는 알고리즘 문제 풀 때는 되도록 우분투 Vim 에디터에서 문제를 푼다. 이런 훈련은 알고리즘 문제 뿐만 아니라 디버깅 환경이 척박한 실무에서도 도움이 된다.



    (필자가 Vim에디터로 문제를 푸는 모습. 뱀 문제는 왜 틀렸는지 아직도 모르겠다)


    '알고리즘 > acmicpc' 카테고리의 다른 글

    10422  (0) 2017.04.05
    1937  (0) 2016.09.06
    4095  (0) 2016.08.15
    11437  (0) 2016.07.30
    2253  (0) 2016.07.24

    댓글

Designed by Tistory.