끄적끄적

문제풀이

1. $k_t$를 길이가 t이고 k로 끝나는 오르막 수라고 하고 점화식을 세우면 다음과 같습니다.

$k_t = \sum_{l=0}^k l_{t-1}$

즉, 길이가 2인 1로 끝나는 오르막 수의 개수는 길이가 1인 0으로 끝나는 오르막 수의 합(한개(0))과 길이가 1인 1로 끝나는 오르막 수의 합(한개(1))인 2개입니다. 0 뒤에 1을 붙이고, 1 뒤에 1을 붙여 {00, 01} 두 개가 됩니다.

2. 위의 $k$를 1부터 $n$까지 올리며 계산한 후, $\sum_{k=0}^9 k_n$을 반환합니다.

Python Code

Line 4, 6 : 문제의 조건에 따라 %10007을 해줍니다.

문제링크

2018 카카오 블라인드 채용 문제입니다.

문제풀이

먼저, LRU 알고리즘 : 새로운 페이지가 등장했을 때, 가장 오래전에 사용된 페이지를 캐시에서 삭제합니다.

즉, 캐시 사이즈가 2이고, 캐시에 t=1일 때 A, t=2일 때 B가 들어오면, A와 B는 캐시가 비어있으므로 그냥 캐시에 추가합니다. t=3 일 때 C가 등장한다면, 가장 오래전에 사용된 A를 캐시에서 제거하고 C를 캐시에 추가합니다.

=> 큐 자료구조를 활용합니다.

1. cities에서 city를 꺼내고 대소문자를 구분하지 않는다고 했으므로 전부 대문자로 변환합니다.

2. queue 자료구조로 cache를 선언합니다. cache의 앞에 있을수록 사용한지 오래된 페이지입니다.

위의 예에서 cache는 [A] -> [A, B] -> [B, C]로 변화합니다.

3-1. city가 cache에 있다면 cache에서 city를 삭제하고 city를 다시 넣어줍니다. answer에는 1을 더해줍니다.

* pop()으로 꺼내지 않고 remove(cache)로 지워야합니다. 여기서 city를 지우는 이유는 city를 가장 최근에 사용된 것으로 바꾸기 위해 cache의 맨 끝에 넣기 위함인데, pop()으로 지우면 cache에서 city가 아니라 가장 오래된 것이 지워집니다.

** cache가 [A, B, C] 일 때, B가 들어오면, cache를 [A, C, B]로 바꾸기 위해 B를 지운 후 다시 넣는 것을 말합니다.

3-2. city가 cache에 없다면 cache의 첫번째 요소를 제거(pop())한 후, city를 cache에 넣어줍니다. answer에는 5를 더해줍니다.

*cache의 크기가 cacheSize보다 작을 때는 첫번째 요소를 제거하지 않고 city를 cache에 넣어주는 작업만 수행합니다.

Python Code 

Line 4 : cacheSize가 0인 경우에는 cities의 요소 수에 5를 곱해 반환합니다.

Line 6 : cache에 cities의 첫번째 요소를 넣은 채 선언합니다. 따라서 answer 역시 5로 초기화합니다.

Line 9 : city가 cache에 있는 경우입니다.

Line 13 : city가 cache에 없는 경우입니다.

문제 링크

2019 카카오 개발자 겨울 인턴십 문제입니다.

문제풀이

1. 문제가 잘 이해가 안되는데, 예로 [2,1,3,4]를 설명하면 다음과 같다.

[2,1,3,4]는 {{2},{2,1},{2,1,3},{2,1,3,4}}로 쓸 수 있는데, 이 집합의 순서를 아래와 같이

{{2,1},{2,1,3},{2},{2,1,3,4}} 등으로 바꿀 경우, 이 집합을 통해 [2,1,3,4]를 맞추는 문제이다.

2. 집합의 각 요소를 살펴보면, 2가 4번, 1이 3번, 3이 2번, 4가 1번 등장하는 것을 볼 수 있다.

즉, 많이 순서대로 앞에 위치하는 요소가 된다.

Python Code

Line 4 : 각 집합을 꺼냅니다.

Line 5 : 각 집합의 요소를 꺼내 int로 변환해줍니다(Line 6).

Line 3, 7 - 10 : co는 각 요소가 key, 등장하는 횟수가 value인 딕셔너리 자료구조입니다.

Line 11 : co의 key들을 등장 횟수를 기준으로 정렬하여 리스트로 반환합니다.

문제링크

2018 KAKAO BLIND RECRUITMENT 3차 문제입니다.

문제 풀이

1. 0부터 차례대로 n진수로 변환합니다.

2. n진수로 변환한 수를 q에 넣어줍니다.

3. q에 들어간 요소의 수가 게임 참가자의 수 m보다 크게되면 answer에 큐의 p번째 요소(튜브의 순서)를 넣어주고 q에서 m개의 요소를 제거하여 줍니다.

4. 1 ~3의 과정을 answer의 길이가 t가 될 때까지 반복해줍니다.

* 단계1에서 0부터 계속 n진수로 바꾸는 것을, 0에 계속 1씩 더해가는 방식으로 수정하면 더 빠를 것 같습니다.

Python Code

Line 4 : 숫자 n을 base 진수로 변환시켜주는 함수입니다. 재귀식으로 수행됩니다.

결과

두번째 풀이

위의 풀이에 *로 써놓은 것을 구현한 코드입니다.

Python Code

Line 3: Num 클래스는 n진수이며 처음에  num 변수는 [0]로 초기화됩니다.

Line 8 : Num 클래스의 add 메소드는 num 변수에 1을 더하는 메소드로 addNum이라는 메소드를 통해 실행됩니다.

Line 10 : addNum은 depth 자릿수의 숫자에 1을 더하는 것으로, 수가 가득차는 경우(10진수의 경우 9에 1을 더해 10이 되는 경우)에는 depth 자릿수의 숫자는 0으로 하고 depth+1번째 자릿수에 1을 더하게 됩니다.

결과

테스트 24번을 기준으로 앞의 풀이보다 약 5ms 빨라진 것을 볼 수 있습니다.

문제 링크

문제 풀이

1. GROUP BY 를 통해 각 이름의 개수를 세어줍니다.

2. 개수가 2개 이상인 이름만 출력합니다.

* 이름이 NULL인 것이 함정입니다.

Oracle Code

문제 링크

문제 풀이

1. 요거트가 담긴 바구니의 카트 아이디 중 우유가 담긴 바구니를 찾는다.

Oracle Code

Line 2~4 : 요거트가 담긴 바구니의 카트 아이디를 구한다.

Line 5 : 우유가 담긴 바구니의 카트 아이디 중 요거트가 담긴 바구니의 카트 아이디와 같은 것을 찾아 반환한다.

문제링크

2020 KAKAO BLIND RECRUITMENT 문제

위의 카카오 공식 해설을 참조하시면 좋을 것 같습니다.

문제 풀이

1. 압축하는 글자 수는 1개부터 글자수의 절반까지만 하면 됩니다.

2. 압축 글자 수를 num이라 할 때, 첫 문자열의 위치를 i, 다음 문자열의 위치를 j라 하면 s[i:i+num]와 s[j:j+num]을 비교하며 같으면 j를 j+num으로 고쳐주며 같은 단어의 수를 세어줍니다.

3. 다른 경우에는 정답 문자열에 같은 단어의 숫자 + s[i:i+num]을 더해줍니다.

4. 위의 과정을 반복한 후, 남은 문자열을 더해줍니다. (xxxxi를 압축하는 경우, 위의 과정을 반복하면 2xx가 되고, 남는 i를 더해 2xxi를 완성합니다.)

Python Code

Line 3 : 압축은 1개부터 문자열의 절반까지만 수행합니다.

Line 11 : i는 기준 문자열의 시작점입니다.

Line 12 : j는 비교할 문자열의 시작점입니다. 처음에는 s[0:num]과 s[num:num+num]을 비교하게 됩니다.

Line 13 : cnt는 기준 문자열이 반복되는 횟수입니다. 반복되는 문자열이 없는 경우에는 1이 됩니다.

Line 14 : 기준 문자열의 시작점이 문자열보다 커지면 중단합니다.

Line 15 : 기준 문자열이 반복되면 cnt에 1을 더해주고, j에 num을 더해 다음 문자열을 기준 문자열과 비교합니다.

Line 19 : cnt가 1인 경우에는 쓰지 않습니다.

Line 20 : 위의 과정4인 남는 문자열을 씁니다.

문제 링크

문제 풀이

1. dictionary 자료구조를 활용하여 각 나무의 등장 횟수를 세어줍니다.

2. 이 때, defaultdict를 사용하면, 해당 나무가 이미 등장한 적이 있는지 검사하는 코드를 작성할 필요가 없습니다.

3. format 함수를 이용하여 각 나무의 점유율을 소수점 넷째 자리까지 출력합니다.

Python Code

문제링크