구현(Implementation) 문제 (완전 탐색, 시뮬레이션)

📌 구현(Implementation) 이란?

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이지만, 보통 특별한 알고리즘보다는 문제를 요구사항에 맞춰 코드로 풀어내는 능력 + 프로그래밍 언어의 문법의 정확한 이해를 갖추고 있는지 보는 문제라고 생각하면 될 것 같다. 

 

예시로는 다음과 같은 것들이 있다.

• 알고리즘은 간단한데 코드가 지나치게 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제
• 사소한 조건 설정이 많은 문제

 

보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 하지만 고차원적인 사고력을 요구하는 문제는 나잊 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다. 

 

그리고 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데, C/C++나 Java에서는 문자열 처리가 파이썬에 비해 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용해야 하기 때문에 C/C++나 Java로 풀기 어려울 수 있다. 

 

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 카카오 공채 때 API 개발 문제가 출제된 적이 있는데, 이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. 이는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다. 이런 기능을 구현해야 할 때, C++이나 Java에 비해 파이썬은 매우 간결하고 직관적인 코드의 라이브러리를 사용할 수 있어 더 유리하다. 

(나는 API 개발 문제를 풀어본 적이 없어서 잘 모르겠다🤔)

 

 

---

 

 

 

완전 탐색과 시뮬레이션 유형은 구현이 핵심이 되는 경우가 많으므로 이에 대해서도 잠깐 알아보자. 

 

📌  완전 탐색이란?

모든 경우의 수를 주저 없이 다 계산하는 해결 방법이다.

 

📌  시뮬레이션이란?

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형이다. 

 

 

---

 

이제 예제를 풀어보자.

 

1️⃣  상하좌우

Q. (1, 1)에서 출발해 입력값(R, L, U, D) 개수만큼 이동했을 때 최종 좌표를 구하시오. 전체 공간의 크기는 (N, N)이며, (1, 1) ~ (N, N) 공간을 벗어나는 이동은 무시한다.

 

A. 이 유형은 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로 분류되며, 구현이 중요한 대표적인 문제 유형이다. 이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 따라서 시간 복잡도는 O(N)이며 매우 넉넉한 편이다.

 

아래는 내가 작성한 코드이다. 

교재에 나와있는 답안 예시가 더 세련되었지만.. 지금은 시간이 없으니 고치는건 나중에 하기로 한다.

package org.example.chap4;

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

public class Ex4_1 {
	public static void main(String[] args) throws IOException {
		int x = 1, y = 1;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());

		while (st.hasMoreTokens()) {
			String dir = st.nextToken();

			if ("L".equals(dir)) y -= 1;
			else if ("R".equals(dir)) y += 1;
			else if ("U".equals(dir)) x -= 1;
			else if ("D".equals(dir)) x += 1;

			if (x < 1) x += 1;
			else if (x > N) x -= 1;
			else if (y < 1) y += 1;
			else if (y > N) y -= 1;
		}

		System.out.println(x + " " + y);
	}
}

 

 

2️⃣  시각

Q. 0시 0분 0초부터 N시 59분 59초까지 3이 들어간 시각의 개수를 세시오.

 

A. 완전탐색 문제로, 하나씩 돌리면서 3이 들어가는지 체크하면 된다. 전체 경우의 수는 24*60*60 = 86400개이므로 완전탐색이더라도 1초 안에 풀 수 있는 문제이다.

 

아래는 코드 중 주석처리한 부분이 내가 짠 코드인데, 왜 답이 다르게 나오는지 모르겠다.

유튜브 강의 보고 이유를 찾아보는걸로.

package org.example.chap4;

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

public class Ex4_2 {

	public static boolean check(int h, int m, int s) {
		// h -> 1의 자리가 3, m -> 30이거나 1의 자리가 3, s -> 30이거나 1의 자리가 3
		if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
			return true;
		return false;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int count = 0;
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j < 60; j++) {
				for (int k = 0; k < 60; k++) {
					// String time = Integer.toString(N).concat(Integer.toString(j)).concat(Integer.toString(k));
					// System.out.println(time);
					// if (time.contains("3")) count++;

					if (check(i, j, k)) count++;
				}
			}
		}

		System.out.println(count);
	}
}

 

🔗  참고 자료