APS를 위한 코딩 스타일

사실 APS(Algorithm Problem Solving)라고 해서 일반적인 애플리케이션 작성과 다른 특별한 코딩 방법이 있을리는 없다. 흔히 APS를 위한 코드는 속도만을 중시 하기 때문에 몇몇 알고리즘 기법을 이용해서 직선으로 내달리는 코드만을 작성한다고 생각하기 쉬운데 보기 좋은 떡이 먹기 좋은 것은 일반 애플리케이션이나  APS에서나 동일하다.

하지만 그럼에도 불구하고 짧은 시험 시간동안 깔끔한 설계를 통해서 문제를 풀기란 쉽지 않다. 그래서 객체지향적인 개념에는 부합하지 않더라도 살짝 양보하는게 좋거나, APS과정에서 유용한 코딩 방식에 대해서 알아보자.

아 먼저 필자는 Java언어를 이용하기 때문에 아래 내용들은 자바를 기준으로 작성되어있다.

 

static member 활용

 

 

instance member 보다는 static member 사용

일반적으로 Java와 같은 객체지향 언어에서는 객체를 만들고 이들을 통해 프로그램이 진행된다. 하지만 객체 지향에서는 이 과정은 약간 사치다. 따라서 member 변수나 메서드는 모두 static으로 사용한다. 어차피 여러 개의 클래스를 만들지 않고 main 메서드에서 동작하는 간단한 애플리케이션을 만들기 때문에 static을 이용하는 것으로도 충분하다.

 

private static int N, R, C;
private static int[][] map;
private static int answer;
private static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

private static boolean isIn(int r, int c) {
    return 0 <= r && 0 <= c && r < R && c < C;
}

 

 

변수의 초기화 문제

static 변수를 사용하다보면 편한데 깜빡 실수하는 경우가 많은데 바로 하나의 문제에서 여러 개의 테스트케이스를 처리하야할 경우이다. SWEA의 경우가 대표적인 케이스이다.

 특히 static 변수로 입력받지 않은 값(대표적으로 정답 처럼 연산되어야 하는 값)을 사용할 때에는 테스트케이스마다 초기화 해주는 과정을 잊지 말아야 한다.

public class Test {
    static int T, A;

    public static void main(String[] args) throws IOException {
        // 테스트 케이스 개수
        T = 10;

        for (int t = 1; t <= T; t++) {
            // 정답 A에 대한 초기화 필요
            A = 0;

            // 문제 풀이

            // 초기화 되지 않으면 오염된 값 사용 가능
            if (A == 0) {
                System.out.println("정답이 없습니다.");
            } else {
                System.out.println(A);
            }
        }
    }
}

 

 

메서드 활용

 

메서드를 이용한 코드의 재사용

프로그래머라면 메서드의 작성을 통해 코드를 모듈화하고 재사용하는것이 얼마나 중요한지 잘 알 것이다. 메서드를 사용하면 메서드 호출 비용이 조금 발생할 수도 있지만 코드의 재사용으로 중복 코드가 없어지므로 디버깅이 용이해지며 코드의 가독성도 향상된다.

 

예를들어 r과 c가 각각 0~R, 0~C의 범위 내에 있어야 한다고 생각했츨 때 아래와 같이 코드를 작성할 수 있다.

if(0<=r && r<R && 0<=c && c<C) {
    // do something
}

하지만 만약 범위체크가 여러 곳에서 반복된다면 그 부분을 메서드로 만들어 모듈화해서 사용하는 것이 좋다.

private static boolean isIn(int r, int c) {
    return 0 <= r && 0 <= c && r < R && c < C;
}

if(isIn(r, c)) {
    // do something
}

 

 

비지니스 로직과 데이터 분리하기

메서드를 사용하라고 해서 메서드 사용에 중독되지는 말자. 비지니스 로직이 개입되는 경우 메서드를 사용하는 것이 좋지만 고정된 값을 가져올 때는 배열 활용 등 다른 수단을 고려하는 것이 좋다.

예를 들어 숫자 기반으로 해당하는 요일을 가져와야 한다고 할때 아래와 같이 메서드를 이용해볼 수 있다.

private static String getWeek(int i) {
    if(i==0) {
        return "SUN";
    }else if(i==1) {
        return "MON";
    }
    . . .    
    }else {
        return "SAT";
    }
}

하지만 이런 경우는 아래와 같이 배열을 이용하는 것이 훨씬 직관적이다.

private static String [] weeks = {"SUN","MON","TUE","WED","THU", "FRI", "SAT"};

이 내용은 비지니스 로직과는 무관한 데이터이기 때문이다.

 

 

 

naming rule

 

identifier의 이름

한글로 작성된 글을 읽을 때 중간중간에 모르는 단어가 나오면 그 뜻을 파악하느라 전체적인 독서의 흐름이 방해된다. 우리가 작성하는 프로그래밍 코드도 엄연히 언어로 작성된 문서이다. 따라서 코드를 읽다가 (컴파일 되는게 아니라 순수하게 코드를 읽는것) 뜻을 한번 더 생각해야 한다면 당연히 전체 코드의 이해를 어렵게 만든다.

 

예를 들어 아래의 코드에서 i는 무엇이고 j는 무엇일까? method라는 메서드는 어떤 일을 하는걸까? 코드는 잘 동작하겠고 습관적으로 이차원 배열의 행/렬이라고 생각할 수도 있겠지만 그 의도를 파악하기 위해 한번 생각하게 했다는것이 아쉽다.

private static void method() {
    for (int i = 0; i < I; i++) {
        for (int j = 0; j < J; j++) {
            map[i][j] = Integer.parseInt(tokens.nextToken());
        }
    }
}

아래처럼 만들어주면 정말 쉽게 이해할 것 같다.

private static void 맵구성하기() {
    for (int 행 = 0; 행 < 행_최대값; 행++) {
        for (int 열 = 0; 열 < 열_최대값; 열++) {
            배열[행][열] = Integer.parseInt(tokens.nextToken());
        }
    }
}

메서드가 어떤 기능을 하는지, 변수는 어떤 의미인지 별도로 생각하지 않아도 의도가 정확히 전달되므로 코드의 이해도 훨씬 쉬워진다. 물론 웬지 한글로 프로그래밍하기는 좀 어색하기 때문에 영어로 쓰는게 일반적일 것이다.

private static void makeMap() {
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            map[r][c] = Integer.parseInt(tokens.nextToken());
        }
    }
}

 

 

범위 설정

 

가급적 0부터 시작하는 반 열림 구간(0<=n<N) 사용

숫자 범위를 반복도는 경우 가급적이면 0부터 시작하는 반 열림구간을 사용하는 것을 권장한다. 괜히 0<=n<=N-1이나 -1<n <N 처럼 여러 상황을 섞어서 사용하면 실수하기 쉽다.

위 문제와 같은 경우 N을 입력 받을 때 그대로 처리한다면 for(int n=1; n<=N; n++)형태로 닫히 구간 형태로 작성할 수도 있지만 애초에 1을 증가시켜서 반열림구간을 구성할 수도 있다.

static int N;
static int[] nums = null;

public static void main(String[] args) throws NumberFormatException, IOException {
    N = Integer.parseInt(input.readLine()) + 1;
    nums = new int[N];
    tokens = new StringTokenizer(input.readLine());
    for (int n = 1; n < N; n++) {
        nums[n] = Integer.parseInt(tokens.nextToken());
    }
}

 

 

dummy 값의 활용

특히 1부터 범위를 사용하는 문제가 있다면 0번째에는 dummy 값을 넣고 1번 부터 실제 값으로 사용하는 것도 괜찮다. 무리하게 인덱스를 당겨서 사용할 필요는 없다. 

 

예를 들어 아래와 같은 지문이 있을 때 1번부터 4번까지의 자료를 관리하기 위해 크기가 4인 배열이 필요하다. 하지만 그런 경우 인덱스의 불일치가 발생할 수 있다.

 

이런 경우 아래처럼 그냥 다섯개 짜리 배열을 만들고 1번부터 사용하는 것이 코딩상 훨씬 유리하다.

private static List<Integer>[] gears = new List[5];

for (int i = 1; i < gears.length; i++) {
    gears[i] = new LinkedList<>();
    ...
}

 

 

 

Off-By-One 오류

off-by-one 오류는 경계검사에서 하나의 오차가 있을 때 발생하는 오류이다. 전체적인 알고리즘은 맞지만 경계지점에서 하나가 많거나 작아서 틀리는 경우가 왕왕 발생하는데 정말 허탈하다.

가장 쉬운 예로 100미터 거리에 10미터마다 울타리를 새울 경우 기둥의 개수를 묻는다면 얼른 생각하면 10개지만 0미터 지점에 기둥이 세워질 수 있다면 총 11개의 기둥이 새워지게 된다.

 

이런 경우는 테스트케이스의 최대값과 최소값을 입력해서 확인해보는 것이 좋다.

 

 

나만의 스타일 가져가기

 

익숙하지 않은 코드는 틀리기 마련!

일상의 대화에서 동일한 의미를 전달하는데 여러가지 표현이 존재하듯 프로그래밍에서도 여러 표현으로 작성이 가능하다. 간단하게는 반복문을 돌리면서 불필요한 상황을 처리할 때 if~else로 처리하기도 하고 continue 문장으로 처리하기도 한다.

for (int i = 0; i < 10; i++) {
    if (i % 2 == 0) {
        System.out.print(i * 2);
    } else {
        System.out.print(i += 2);
    }
}

for (int i = 0; i < 10; i++) {
    if (i % 2 == 0) {
        System.out.print(i * 2);
        continue;
    }
    System.out.print(i += 2);
}

 

입력을 받을 때 Scanner를 사용할 수도 있고 BufferedReader를 사용하기도 한다. 그래프를 만들 때 인접 행렬을 쓰기도 하고 인접 리스트를 쓰기도 한다. MST를 구할 때 Prim을 쓰거나 Kruskal을 사용할 수도 있다.

 

문제는 APS는 시간에 쪼들리기 마련이라는 점이다. 시간이 주는 압박감은 익숙치 않은 코드를 더욱 위태롭게 만들게 된다.  따라서 특별한 목적이 없다면 비슷한 동작을 처리하기 위해서 여러 스타일로 연습할 필요는 없다.한 두가지 본인의 코딩 습관을 유지한다면 실수를 방지하는데 도움이 된다.

 

물론 상황에 따라 유리한 기법들이 있기는 하다. 인접행렬은 쓰기 편하지만 느슨한 그래프에서는 메모리 낭비가 심하고 인접리스트는 메모리를 효율적으로 사용할 수 있지만 코드가 조금 복잡하다.

 

내 스타일로 만들기

필자의 경우 알고리즘 문제를 풀다가 2시간 이상의 시간이 걸렸는데도 아직 못푸는 상황이라면 못푸는 거라고 단정한다. 그 상태에서 "깨끗히 포기하라"는것은 아니고 다른 사람의 솔루션을 보고 공부하기를 권한다. ㅎ

이때 다른 사람의 솔루션에서 아이디어를 공부하라는 것이지 코드를 그대로 공부하라는 이야기는 아니다. 즉 자신의 생각에서 부족했던 부분을 깨우치는것이 중요하다. 그것을 깨우쳤다면 자신만의 스타일로 다시 코드를 작성해보아야 한다. 계속해서 다른 사람의 코드를 그대로 답습하다 보면 습관이 누더기가 되어서 정작 필요할 때 써먹기 쉽지 않다.

 

 

습관을 벗어나야 한다.!!

이건 앞서 이야기 했던 부분과 반대되는 이야기일 수 있다. 습관을 가지라고 했다가 버리라고 했다가.

사악한 알고리즘 문제 출제자들은 어떻게하면 사람들이 함정에 빠지는지 잘 안다. 따라서 습관처럼만 코딩하다보면 출제자가 파놓은 이 함정에 쉽게 빠져들고 만다.

예를 들어 BFS로 그래프를 탐색하는 과정에서 평소에 코드의 편의를 위해서 Queue에 담을 때 방문처리를 하는데 어떤 문제는 Queue에서 빼낸 후에 방문처리를 해야하는 경우도 있다. 

 

이처럼 때에 따라서는 습관을 벗어나야 적절한 솔루션을 찾을 수 있는 경우가 있는데 이를 위해서는 원리에 대한 파악이 중요하다. 한창 수학 공부를 열심히 했던 고등학교때로 돌아가보면 문제를 잘 푸는 것 보다 더 우위에 있는 것이 문제를 증명하는 것이었는데 증명을 위해서는 정확한 이해가 필수였다는 점이 같은 맥락이다.

 

 

기타

 

표준 라이브러리 사용

코딩테스트는 여러 분야에서 사용된다. 정보올림피아드 대회에서, 우리가 관심 많은 입사 테스트에서도, 회사에서 좀 더 높은 자격 취득을 위해서..

이런 각각의 시험들은 사실 물어보고 싶은 내용도 좀 다르다(라고 생각한다. ㅎ) 정보올림피아드는 순위가 있으므로 성능이 보다 강조된다. 따라서 이런 경우는 자료구조를 직접 구현하는 경우가 많고 대부분 배열로 처리한다.

하지만 입사 코테의 경우는 "지원자가 논리적인 사고가 가능한가?" 라는 쪽이 주요 관심사이다. 따라서 큐나 스택등을 직접 작성하기 보다는 제공되는 표준 라이브러리를 이용해서 논리적으로 문제를 해결할 수 있는가에 관심이 많다. 

 

어줍잖게 사용자 정의 자료구조를 흉내내기 보다는 Collection Framework 등 제공되는 표준 라이브러리의 특징과 정확한 용법을 이해하고 사용하는 것이 중요하다.

 

물론 회사에서 원하는 보다 높은 등급의 자격을 얻기 위하거나 일부 코테에서는 특정 라이브러리의 사용이 금지된 경우도 있으니 이런 경우는 구현하는 능력이 필요하다. 하지만 이런 시험을 대비할 정도라면 충분히 훈련되지 않았을까 한다. 

 

 

연산자 우선 순위의 최고봉 소괄호!

프로그래밍 과정에서는 정말 다양한 연산자가 사용되는데 연산자에는 우선순위라는 것이 존재한다. 이 우선순위를 잘 못 이해하고 사용하면 당연히 정답과는 바이바이다. 

if(a & 1<<b >0){
	// do something
}

평소 shift 연산자나 논리 연산자를 잘 사용하지 않는다면 위 식의 오류를 처리하기 어려울 수 있다. 연산자를 복합적으로 사용할 때에는 가급적 소괄호를 이용해 우선순위를 표시한다면 오류도 적게 발생하고 프로그램의 가독성도 향상시킬 수 있다.

if((a & 1<<b) >0){
    // do something
}

 

 

정수는 범위가 있다고!!

정수는 타입에 따른 범위가 있다. 대부분 문제 풀이 과정에서 int 타입의 변수를 많이 사용하는데 자바에서 int의 범위는 -2,147,483,648 <= n <=2,147,483,647로 이십억을 조금 넘는다. 따라서 입력이나 출력은 물론 연산시에 발생하는 중간 과정에서도 범위를 넘어가지 않도록 신경써야 한다. 

 

다음의 코드는 두 개의 int를 받아서 그 평균을 리턴하는 메서드이다. 너무 간단해서 디비깅도 필요 없을것 같지만 만약 a + b가 int의 경계를 넘어가는 큰 값이 된다면 대 재앙이 몰려올것이다.

public int getAvg(int a, int b) {
     return (a + b)/2;
}

 

하지만 출제자들은 사악하기 때문에 주어진 테케를 이용할 때에는 overflow가 발생하지 않게해서 우리를 속인다.

 

따라서 문제를 풀면서는 다음 두 가지 사항을 염두해 두자.

• 주어진 입력의 최대값과 최소값으로 테케를 만들어보는 습관을 갖는다.
• 자주 실수를 범한다면 애초에 int 대신 long 형을 사용하는 것도 차선책이다.

 

문제 풀이 과정에 최소 값을 구하기 위해 기본값을 Integer.MAX_VALUE로 초기화를 하기도 한다. 중간에 혹시 1이라도 더하는 코드가 있다면 역시 전혀 예상치 못한 결과를 얻게 된다.  특별한 이유가 없다면 최대값을 설정할 때 987,654,321을 이용하는 것도 괜찮을 습관이다. 매우 큰 값이면서도 *2를 해도 여전히 int의 범위에 들어있다.

 

 

실수는 정확하지 않아!!

컴퓨터에서는 실수를 2진수로 표시하기 때문에 정확한 값을 사용할 수 없어서 근사값을 사용한다. 말 그대로 근사값은 정확한 값에 가까운 값이기 때문에 이를 통한 계산도 정확할 수 없다.

 

아래처럼 2.0-1.1의 결과가 0.9가 아니다.

double d1 = 2;
double d2 = 1.1;
System.out.println(d1 - d2); // 0.8999999999999999

자바에서 정확한 실수 연산을 위해서는 BigDecimal 클래스를 사용하거나 실수의 소숫점 이하 자리를 알 경우 실수를 정수로 바꿔서 연산할 수 있다.

BigDecimal bd1 = new BigDecimal(String.valueOf(d1));
BigDecimal bd2 = new BigDecimal(d2 + "");
System.out.println(bd1.subtract(bd2)); // 0.9

int i1 = (int) (d1 * 10);
int i2 = (int) (d2 * 10);
System.out.println((i1 - i2) / 10.0);  // 0.9

아예 실수 연산을 회피할 수도 있다. 예를 들어 두 점 (x1, y1), (x2, y2)의 거리가 5인 점을 찾을때 실제 거리 계산에는 √(x2-x1)^2 + (y2-y1)^2 을 사용하는데 이 과정에서 실수가 발생한다.  이런 경우는 아예 제곱근을 구하지 않고 (x2-x1)^2 + (y2-y1)^2이 25인 지점을 찾아도 결과는 동일하다.

 

상수오타

컴파일러가 잡아주는 오류를 냈다면 정말 행복한 경우다. 아주 손쉽게 고칠 수 있기 때문이다. 하지만 문제에서 주어지는 각종 상수를 잘못 입력해서 발생하는 오류는 컴파일러가 책임지지 않는다.

또는 큰 수를 계산할 때 100000007로 나눈 나머지를 출력하는 문제들이 자주 나오는데 0을 하나 빼먹으면 디버깅하는데 아주 힘들다.

이런 실수를 방지하기 위해서는 가급적 copy/paste를 하자. 큰 숫자의 경우 100_000_007처럼 '_'를 이용해서 가독성을 높일 수도 있다.