Vamos ser Programador com Devfon

2017 카카오 신입 공채 1차 코딩 테스트 <캐시> in Java

3. 캐시(난이도: 하)

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

public class Cache {
	
	public static void main(String[] args) {
		int cacheSize = 2;
		String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};
		LRU(cacheSize, cities);
	}
	
	public static int LRU(int size, String[] cities) {
		String[] caches = new String[size];
		int runtime = 0; int findFlag;
		int inputSize = cities.length;
		int idx = 0;
		
		if(size == 0) { // exception handling
			runtime = 5 * inputSize;
			return runtime;
		}
		// lower every city's name
		for(int i = 0; i < inputSize; i++) 	cities[i] = cities[i].toLowerCase();
	
		for(int i = size - 1; i >= 0; i--) { // initialize cache 
			caches[i] = cities[idx];
			runtime += 5; idx++;
		}
		
		for(int i = size; i < inputSize; i++) {
			findFlag = find(cities[i], caches);
			if (findFlag == 1) 		runtime += 1; 		
			else 					runtime += 5; 
		}

		return runtime;
	}
	
	public static int find(String name, String[] caches) {
		int lastIdx = caches.length - 1; 
		
		for(int i = 0; i < caches.length; i++) {
			if(name.equals(caches[i])) { 	
				String tmp = caches[i];
				
				if(i == lastIdx) {
					for(int j = lastIdx; j > 0 ; j--) 		caches[j] = caches[j-1];
				}
				
				else if(i != 0 && i != lastIdx) {
					for(int j = i; j > 0 ;j--) 			caches[j] = caches[j-1];
				}
				
				caches[0] = tmp;
				return 1;
			}
		}
		for(int i = lastIdx; i > 0; i--) 		caches[i] = caches[i-1];
		caches[0] = name;
		
		return 0;
	}
}

2017 카카오 신입 공채 1차 코딩 테스트 <다트 게임> in Java

2. 다트 게임(난이도: 하)

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.

갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

“점수|보너스|[옵션]”으로 이루어진 문자열 3세트.
예) 1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예제

2017 카카오 신입 공채 1차 코딩 테스트 <비밀 지도> in Java

1. 비밀 지도(난이도: 하)

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 “공백”(“ “) 또는 “벽”(“#”) 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. “지도 1”과 “지도 2”는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

method 'SecretMap'

: 주어진 arr1, arr2 정수 배열의 원소들을 bitwise - OR 해주어 결과값을 구해준다. 이후, 구한 정수값을 Binary String으로 변환해준 후, '1'이 들어간 자리는 '#'으로 '0'이 들어간 자리는 ' '으로 replace 해주어 최종 결과를 구할 수 있다.

method 'reversepad'

: 주어진 정수 n보다 result의 길이가 작을 경우, 그 크기의 차이 만큼 좌측을 공백으로 padding 해주는 기능을 수행한다. 먼저, String에 공백을 추가시켜준 뒤 해당 String을 for문을 통해 reverse 시킴으로써 좌측 padding의 기능을 수행할 수 있다.

[Sorting Algorithm]

정렬이란 데이터를 특정 순서에 따라 나열하는 일련의 과정으로, 대개 우리는 배열 요소에 저장되어 있는 값에 따라 정렬을 한다. 이러한 정렬에 있어 그 기준은 수가 될 수도 있고, 단어 혹은 배열에 인접한 쌍(pairs)이 될 수 있다. 이를테면, 우리는 학급에 속한 학생들을 키에 따라 정렬해볼 수 있다. 혹은 우리나라의 도시를 영문 알파벳 순으로 혹은 도시에 거주하는 시민의 수에 따라 정렬해볼 수도 있을 것이다. 그리고 이러한 정렬 과정에 있어 가장 많이 사용되는 기준은 수의 크기에 따른 정렬(numerical order) 혹은 알파벳순에 따른(alphabetical order) 정렬이다.

다음 그림과 같이 정수로 이루어진 간단한 배열을 생각해보자

우리는 이 배열을 다음과 같은 오름차순으로 정렬하고자 한다.

Computer Science의 Algorithm에는 위같은 정렬을 위한 많은 정렬 알고리즘이 있으며, 각각의 알고리즘들은 시간 복잡도와 메모리 사용에 있어 큰 차이를 가진다. 다음, 정렬 알고리즘의 몇 가지 예를 살펴보자.

1) Selection Sort

# Code in Python3

-      개념: 배열의 첫 번째 원소에서 시작하여, 첫 번째 원소를 포함한 배열의 모든 값들 중 최소값을 찾은 후 이 최소값을 배열의 첫 번째 원소와 교환한다. 이후 두 번째 원소로 넘어가 첫 번째 원소를 제외한 배열의 값들 중 다음 최소값을 찾는다. 이러한 과정을 마지막 원소까지 반복하게 된다.

배열의 원소 개수가 k개라면, 첫 번째 원소는 k번의 반복 이후 자기의 자리(right order)를 찾아가게 된다. 이러한 성질을 ‘loop invariant’라고 하며, 자세한 내용은 링크 참조.

* 시간 복잡도는 두 번의 반복문이 중첩되어 있으므로, O(n²)

2) Counting Sort

[Input으로 받은 배열에서 0이 5번, 1이 3번, 2가 4번, 3이 0번 그리고 4가 2번 발생하였기 때문에 count array에 5, 3, 4, 0, 2가 기록되게 된다. 이 기록을 가지고 정렬된 배열을 Output으로 return 한다]

# Code in Python3

-      개념: Counting Sort를 이용하기 위해서는 정렬할 배열의 최대 크기 k를 알아야 한다. 이후 0을 포함하기 위해 배열의 최대 크기인 k에 1을 더한 크기 만큼의 [0]자 배열 count를 생성한다.

이후, 배열 A의 크기 만큼 반복문을 돌며 count의 index에 맞는 요소에 각 숫자의 등장 횟수를 count 해준다. 이후, count된 숫자를 그 등장 횟수만큼 배열 A에 삽입해주면, 오름차순 + 등장 횟수에 따른 배열 A가 정렬되게 된다.

* 시간 복잡도는 O(n + k). 배열의 모든 요소들을 정리하기 위해, O(k) 크기 만큼의 추가 메모리가 필요하다. 따라서 위 코드의 실행을 위해 필요한 시간 복잡도가 크게 느껴질 수 있다. 그러나 결국 이중 중첩된 아래 반복문의 연산(line 11, 12)은 O(n) 이상으로 수행되지 않는다.

3) Merge Sort * 아래 간단한 설명보다 구현이 복잡하기 때문에 wikipedia를 참고하는 것을 추천드립니다.

-      개념: 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 간주하지만, 그렇지 않은 경우 정렬되지 않은 리스트를 절반(홀수라면 한 개의 차이가 발생하도록)으로 잘라 비슷한 크기의 2개의 리스트로 나눈다. 이후 나뉘어진 두 개의 부분 리스트를 recursive 하게 합병 정렬을 이용해 정렬한다. 마지막으로 나누어진 두 부분 리스트들이 다시 재귀적으로 하나의 정렬된 리스트로 합병하도록 한다.

* 시간 복잡도는 O(n log n)

4) Sorting functions

-      만약 정렬하고자 하는 배열에 속한 값들의 그 범위를 모를 경우, O(n log n)의 시간 복잡도를 가지는 내장 정렬 함수를 통해 모든 값들을 정렬할 수 있다. 우리가 사용하는 많은 다양한 프로그래밍 언어들의 장점은 그것들이 가지는 내장 정렬 함수 기능에 있다. 만약 Python에서 list를 정렬하고 싶다면 우리는 아래의 한 줄 코드로 이같은 정렬을 수행할 수 있다.

* 시간 복잡도 O(n log n)

* 결론: 일반적으로, 정렬 알고리즘은 다른 알고리즘 문제에도 사용될 수 있는 흥미로운 수학적 개념들을 사용한다. 따라서 위와 같은 정렬 알고리즘이 내부적으로 어떻게 작동하는지 아는 것은 큰 배움이 될 수 있다. 그리고 더 나아가 이 알고리즘들을 스스로 구현해보는 것 역시 작동 방식을 아는 것 이상의 가치를 가진다! 또한 미래에는 내장된 정렬 함수를 사용해도 좋을 것이다. 내장 정렬 함수는 점점 빠른 성능을 보이게 될 것이며, 내장함수를 사용하는 것이 여러분의 코드를 보다 짧고 읽기 쉽게 만들어줄 것이기 때문이다.

[무식하게 풀기: Brute-Force]

1.     도입

l  알고리즘을 공부한 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸려는 시도를 하는 것

l  ‘무식하게 풀자(brute-force)’: 컴퓨터의 빠른 연산 능력을 백분 활용하여 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법으로 시작하자! à 완전 탐색(exhaustive search)

2.     재귀 호출과 완전 탐색

l  재귀호출: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지 조각들은 자기 자신을 호출하는 재귀적 호출을 통해 실행하는 함수

l  기저 사례(base case): 모든 재귀 함수가 ‘더 이상 쪼개지지 않는’ 최소한의 작업에 도달했을 때, 답을 곧장 반환하는 조건문. 기저 사례가 존재하지 않거나, 제대로 설정되지 않는 경우 재귀 호출은 올바른 탈출을 못한 채 무한대로 돌게 되는 무한 Loop를 발생시키게 된다.

l  이러한 재귀호출은 코딩을 간편하게 해줄 수 있는 무기가 될 수 있다.

[알고리즘의 시간 복잡도 분석]

0. 알고리즘이란?

- 알고리즘: 어떤 한 작업이 주어졌을 때 컴퓨터가 그 작업을 해결하는 방법으로, 하나의 같은 문제를 해결하더라도 다양한 경우의 수를 가진 알고리즘들이 나타날 수 있다.

* 좋은 알고리즘의 평가 기준

- 시간: 알고리즘이 적은 시간을 사용한다면 더 빠르게 동작한다.

- 공간: 알고리즘이 적은 공간을 사용한다면 더 적은 용량의 메모리를 사용한다.

그러나 이 두 가지가 상충한다면 더 우선시 되어야 하는 것은 알고리즘의 ‘시간’이며, 메모리 사용량을 희생하여 수행 속도를 높이는 ‘동적 계획법’이 그 대표적인 예이다.

1. 도입

: 보다 빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 알고리즘의 속도 측정 방법을 정하는 것으로, 두 알고리즘의 속도를 비교하는 가장 직관적 방법은 각각의 알고리즘을 프로그램으로 구현하여 구현된 프로그램의 수행 시간을 측정하는 것이다.

그러나, 이렇게 구현된 프로그램의 수행 시간은 프로그래밍에 사용된 언어, 프로그램을 동작시키는 컴퓨터의 하드웨어, 운영체제, 컴파일러 등 수많은 요소에 의해 바뀔 수 있기 때문에 적합한 측정 방법이라 할 수는 없다.

cf) C++에서 크기가 큰 구조체를 함수의 인자로 넘길 때는 reference 형태로 넘겨 주는 것이 좋다. Vector 전체를 넘길 경우, vector를 모두 읽어오는 것부터 많은 시간을 잡아먹기 때문으로, reference(in C++) 혹은 pointer(in C)의 형태로 넘기는 것이 시간적으로 더 유리하다.

“반복문이 지배한다”

여러 비교에 있어서 한 가지 항목이 다른 항목들의 대소를 지배(dominate)하는데, 알고리즘에서는 ‘반복문’이 시간 복잡도와 수행 시간을 지배하게 된다.

2. 선형 시간 알고리즘

Input의 크기 N에 정비례하는 수행 시간을 가지는 ‘선형 시간 알고리즘’

3. 선형 이하 시간 알고리즘

입력으로 주어진 자료에 대해 미리 알고 있는 경우, 선형 시간 알고리즘보다 빠르게 동작하는 알고리즘의 구현이 가능 (log N)

l  이진탐색(Binary Search): 10만 개의 자료 중 5만 번째 자료 확인 à 7만 5천번째 자료 확인 à … à 대략 17개의 자료만으로 원하는 결과 얻어낼 수 있음

l  Binsearch(A[ ], x) = 배열 A[ ]에서 x를 삽입할 수 있는 위치 중 가장 앞에 있는 것을 반환한다. 즉, 배열 내 x가 존재할 경우 첫 번째 x의 위치를, 없는 경우 x보다 큰 첫 번째 원소를 반환한다. 
ex {0, 0, 0, 0, 0, …, 0, 1, 1, 1, …, 1, 1, 1}

* cf. 결국에는 선형 시간?

1)    배열을 넘긴다고 하였지만 사실은 배열을 넘기는 것이 아니다. 확인하고 싶은 위치의 자료만 판단하면 되는 구조

2)    ‘10만 개의 자료를 미리 정렬한다는 의미’는 이 문제의 해결 뿐 아니라 다른 문제의 해결을 위해서도 쓰일 수 있는 것이기 때문에 문제 해결의 일환으로 보지 않는다.

4. 지수 시간 알고리즘

l  다항 시간 알고리즘: 반복문의 수행 횟수인 N에 따라 달라지는 다항 시간 알고리즘. 다항 시간 알고리즘 간에 발생하는 지수의 차이에 따라 수행 시간에 큰 차이가 발생

l  가장 단순하게 최소값을 구하는 방법은 재귀 알고리즘 형태의 구현!

l  지수 시간 알고리즘: 지수의 증가에 따른 수행 시간의 증가

l  다항 시간 알고리즘의 구현이 가능한 문제는 쉬운 문제, 그렇지 않은 문제는 어려운 문제로 단순하게 분류할 수 있음.

l  숫자의 개수가 아닌 숫자의 크기에 따라 수행 시간이 달라지는 알고리즘들 또한 지수 수행 시간을 가질 수 있음
ex) 소인수 분해: 입력 값이 소수인 경우, n-1 번의 실행 횟수를 가지게 됨.

* cf. 과연 소인수 분해가 지수 수행시간을 가지는가?

이진 탐색, 이동 평균 계산 등은 입력의 값들이 일정 범위 내에 있기 때문에 입력의 개수가 메모리에서 차지하는 공간이 직접적으로 비례한다.

그러나, 소인수 분해 문제에서는 입력 값에 따라 알고리즘의 동작이 변화하기 때문에 숫자의 특정이 불가능하다. 입력의 값이 커지면 숫자를 저장하는 필요한 메모리의 공간 증가하게 되는 것이다. 이에 따라 Input값이 차지하는 메모리 내 비트의 수가 증가하여 수행 시간이 증가하게 되는 현상이 발생할 수 있게 된다..

* 비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 증가

5. 시간 복잡도

l  기본적인 연산: 더 작게 쪼갤 수 없는 최소 크기의 연산(대입, 사칙연산, 대소 비교 등)

l  반복문이 포함되는 순간, 그 연산은 기본적인 연산이 아니게 됨

l  입력 크기에 따라 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수 있음
ex) 반복문을 여러 개 중첩하더라도 입력값이 작으면 반복문이 적은 알고리즘보다 좋은 성능을 낼 수 있는 경우가 생김

l  최악의 수행 시간, 수행 시간의 기대치를 기준으로 알고리즘을 작성하는 것이 보편적

l  점근적 시간 표기(Big - O 표기)

: 식에 존재하는 상수 등은 고려하지 않고, 가장 빨리 증가하는 항인 반복문의 반복 수만 고려한 표기 방법

* 특이 알고리즘:
- N²M + N log M + NM^2 = O(N²M + NM²)
à N²M과 NM² 중 어느 식이 더 커질 지 모르기 때문에 두 식 모두 표기

- 42 = O(1) à 상수 시간 알고리즘

l  Big - O 표기법은 알고리즘의 수행 시간을 간단히 나타내는 표기법일 뿐, 최악의 수행 시간과 관련 있는 것은 아니다.

6. 수행 시간 어림짐작하기

l  주먹구구 법칙

: 시간 복잡도와 입력 크기로 대략적 수행 시간 예측이 가능한데, 1초당 반복문의 수행 횟수가 1억을 넘어가면 모든 문제에서 시간 제한을 초과할 가능성이 있다.

l  추가적으로 고려해야 할 요소

1)    시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: Big - O표기법의 경우 상수나 최고차항 이외의 항들을 모두 지워버리므로, 실제 프로그램의 수행 속도는 달라질 여지가 다분함

2)    반복문의 내부가 복잡한 경우: 반복문의 내부가 복잡하거나, 단순하면 Big – O의 예상치와는 다르게 작동하게 될 수 있음

3)    메모리 사용 패턴이 복잡한 경우: 하드웨어적으로 캐시의 사용은 시간 복잡도에는 영향을 미치지 않지만, 수행 속도에 영향을 미치게 된다. 따라서 캐시의 사용 여부에 따라 프로그램의 수행 시간 차이를 보일 수 있음

4)    언어와 컴파일러의 차이: C++의 최적화의 사용 여부 등 언어와 컴파일러에 따라 수행 시간의 차이가 발생하게 됨

7. 더 읽을거리

마스터 정리(Master Theorem): 재귀적 알고리즘의 시간 복잡도를 계산하는 수학적 정리