구현

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다.

우리가 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다.

고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있나?

그렇지 않다.

생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다.

이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

실제 ACM-ICPC, Google Code Jam 등의 대회에 자주 참가하는 사람들이 구현 유형의 문제를 보면 '알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는게 좋다'라고 설명한다.

흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도가 빠른 사람보고 피지컬이 좋다 이야기 하는데, 구현 유형의 문제는 그런 의미에서 피지컬을 요구하는 문제라고도 할 수 있다.

알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱해야 하는) 문제 등이 까다로운 구현 유형의 문제라 할 수 있다.

대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.

물론 경험이 많은 프로그래머에게는 쉬울 수 있으나 초보자 입장에서는 프로그래밍 언어의 문법부터 익숙하지 않기에 더 어렵게 느껴질 수 밖에 없다.

그렇기에 실제로 코딩 테스트에서 구현 문제를 만나면 당황할 수 있다.

어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문이다.

또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다.

완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶는다.

완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행해야 하는 문제 유형을 의미한다.

둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 두 유형을 모두 묶어서 구현 장에서 다루고 있다.

코딩 테스트에서는 어떤 환경에서 문제를 풀어야하는지 알고, 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하므로, 먼저 코딩 테스트 채점 시스템의 제약에 대해 설명한다.

---

구현시 고려해야할 메모리 제약 사항

전통적으로 프로그래밍 언어에서 정수형을 표현할 때는 int 자료형을 주로 사용하며, 이 자료형의 크기는 4 바이트이다.

기본 int 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,438,647인데 이 말은 int 자료형으로 처리하면 2,147,438,647보다 더 큰수를 처리할 수 없다는 의미이다.

더 큰수를 처리하려면 8바이트인 long 과 같은 자료형을 사용해야 한다.

이보다 더 큰수를 처리하면 BigInteger 클래스를 구현하거나 이용해야 한다.

자바의 경우 BigInteger를 표준 라이브러리로 지원한다.

메모리 제한을 염두에 두고 코딩해야 한다.

---

채점 환경

문제에서 요구하는 메모리 제한과 실행 시간 제한은 코딩 테스트를 출제하는 기관마다, 문제마다 조금씩 다르다.

출제가가 매우 빠르게 동작하는 프로그램을 원한다면 시간 제한은 더욱 짧을 것이다.

시간 제한이 1초이고, 데이터의 개수가 100만 개의 문제가 있다면 일반적으로 시간 복잡도 O(N log N) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

따라서 알고리즘 문제를 풀 때 시간제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

---

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴편이다.

문제의 길이를 보고 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다.

카카오 공채에서는 API 개발 문제가 출제된다.

이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다.

이는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다.

---

상하좌우

package CodeTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Implement0401 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); //사각형의 크기 N x N
		StringTokenizer st = new StringTokenizer(br.readLine()); // 이동방향 입력
		// L : 왼쪽, R : 오른쪽, U : 위, D : 아래

		int x = 1;
		int y = 1;
		
		System.out.println(st.countTokens());
		
		String[] arr = new String[st.countTokens()];
		
		for(int i=0; i<arr.length; i++){
			arr[i] = st.nextToken();
		}
		
		for(int i=0; i<arr.length; i++){
			if(arr[i].equals("L")){
				if(y == 1){
					continue;
				}
				y--;
			}else if(arr[i].equals("R")){
				if(y == N){
					continue;
				}
				y++;
			}else if(arr[i].equals("U")){
				if(x == 1){
					continue;
				}
				x--;
			}else if(arr[i].equals("D")){
				if(x == N){
					continue;
				}
				x++;
			}
		}
		System.out.println(x + " " + y);
	}

}

---

시각

package CodeTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Implement0402 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); //시간 입력 N
		
		int cnt = 0;
		
		for(int h=0; h<=N; h++){
			for(int m = 0; m<60; m++){	
				for(int s = 0; s<60; s++){
					if(check(h,m,s)){
						cnt ++;
					}
				}
			}
		}
		System.out.println(cnt);
		
	}
	
	public static boolean check(int h, int m, int s){
		if(h%10 == 3 || m/10 == 3 || m%10 == 3 || s/10 ==3 || s%10 == 3){
			return true;
		}
		return false;
	}

}

데이터가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.

완전탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있다.

---

왕실의 나이트

package CodeTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Implement0403 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int row = str.charAt(1) - '0';
		int column = str.charAt(0) - 'a' + 1;
		
		//나이트가 이동할 수 있는 8가지 방향 
		int[] dx = {-2, -2, -1, 1, -1, 1, 2, 2};
		int[] dy = {-1, 1, -2, -2, 2, 2, 1, -1};
		
		//8가지 방향으로 이동 가능한지 확인
		int result = 0;
		for(int i=0; i<8; i++){
			int nextRow = row + dx[i];
			int nextColumn = column + dy[i];
			//해당 위치로 이동가능한지 체크
			if(nextRow >= 1 && nextRow <= 8 && nextColumn >=1 && nextColumn <=8){
				result ++;
			}
		}
		System.out.println(result);

	}

}

---

게임 개발

package CodeTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Implement0404 {
	
	public static int N, M, x, y, direction;
	//방문한 위치를 저장하기 위한 맵 
	public static int[][] d = new int[50][50];
	// 전체 맵 정보
	public static int[][] arr = new int[50][50];
	
	//북, 동, 남, 서 방향 정의
	public static int dx[] = {-1, 0, 1, 0};
	public static int dy[] = {0, 1, 0, -1};
	
	//왼쪽으로 회전
	public static void turn_left(){
		direction -= 1;
		if (direction == -1) direction = 3;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		N = Integer.parseInt(st.nextToken()); // 맵의 세로 크기 N
		M = Integer.parseInt(st.nextToken()); // 맵의 가로 크기 M
		
		st = new StringTokenizer(br.readLine());
		x = Integer.parseInt(st.nextToken()); //현재 캐릭터 좌표 x
		y = Integer.parseInt(st.nextToken()); //현재 캐릭터 좌표 y
		// 0 : 북 , 1 : 동, 2 : 남, 3: 서
		direction = Integer.parseInt(st.nextToken()); //캐릭터가 바라보고있는 방향
		d[x][y] = 1; //현재 좌표 방문처리
		
		//전체 맵 정보 입력
		for(int i=0; i<N; i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++){
				arr[i][j] = Integer.parseInt(st.nextToken());
 			}
		}
		
		//시뮬레이션 시작
		int cnt = 1;
		int turn_time = 0;
		while(true){
			//왼쪽으로 회전
			turn_left();
			int nx = x + dx[direction];
			int ny = y + dx[direction];
			//회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
			if(d[nx][ny] == 0 && arr[nx][ny] == 0){
				d[nx][ny] = 1; //방문 확인
				x = nx;
				y = ny;
				cnt ++;
				turn_time = 0;
				continue;
			}
			//회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우 
			else turn_time ++;
			//네 방향 모두 가봤거나, 바다인 경우
			if(turn_time == 4){
				nx = x - dx[direction];
				ny = y - dy[direction];
				//뒤로 갈 수 있다면 이동
				if(arr[nx][ny] == 0){
					x = nx;
					y = ny;
				}
				//뒤가 바다인 경우
				else break;
				turn_time = 0;
			}
		}
		System.out.println(cnt);
	}

}

시뮬레이션 문제에서 방향을 설정해 이동하는 문제 유형은 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.