11/30, 12/1 이틀 동안 LV2 문제들을 1페이지 가량 풀었다.... 약 20문제..
(정답률이 높은 기준으로 풀어 엄청 오래 걸리진 않았다!)
1페이지 가량 풀어보면서 LV1과의 차이점을 보면, 확실히 기본적인 구현을 요구하던 LV 1과는 달리, LV 2의 경우 수학적인 사고력과 자료구조 등을 이용하여 문제를 해결하는 방식에서 차이를 보였다.

아래 요약한 문제들은 LV2 1페이지를 풀면서 정리가 필요한? 문제들을 추려냈다.
정답률이 낮아질수록 작성하는 문제 수나 글 수가 줄어들 듯 싶다..

문제 풀이

짝지어 제거하기

문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

• 제한사항
  문자열의 길이 : 1,000,000이하의 자연수
  문자열은 모두 소문자로 이루어져 있습니다.

def solution(s):
    stack = []
    for i in s:
        if len(stack) == 0:
            stack.append(i)
        elif stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)
    if len(stack) == 0:
        return 1
    else:
        return 0
    

< 풀이 과정 >
스택 자료구조를 이용하여 문제를 해결하였다

1. 스택 자료구조 생성 (빈 리스트)
2. for 문으로 주어진 문자열을 탐색하고 1차적으로 stack이 비어있다면 문자열 내 첫번째 단어를 추가해준다.
3. 스택에 저장한 문자와 현재 문자열이 동일하다면 stack내 문자 제거하기
4. 그렇지 않다면 스택에 문자 추가해주기.
5. 위 방식으로 s 문자열 전체를 탐색하여 스택이 비어있다면 문자열이 모두 제거된 것이므로 1을 리턴, 그렇지 않다면 0을 리턴한다.

구명보트

문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

• 제한사항
  무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
  각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
  구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
  구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

from collections import deque

def solution(people, limit):
    answer = 0
    people.sort()
    queue = deque(people)
    while queue:
        if len(queue) >= 2:
            if queue[0] + queue[-1] > limit:
                queue.pop()
                answer += 1
            else:
                queue.pop()
                queue.popleft()
                answer += 1
        else:
            if queue[0] <= limit:
                queue.pop()
                answer += 1
    return answer

def solution(people, limit):
	people.sort()
    answer = 0
    first_idx = 0
    last_idx = len(people)-1
    while first_idx < last_idx:
    	if people[first_idx] + people[last_idx] <= limit:
        	first_idx += 1
        last_idx -= 1
        answer += 1
   	if first_idx == last_idx:
    	answer += 1
	return answer

< 풀이 과정 >
우선 문제를 보자마자 주어진 people 리스트 즉 몸무게를 오름차순으로 정렬해야겠다는 생각을 했다.
주어진 몸무게 리스트 오름차순 정렬 후에 최대 2명 만이 보트에 탑승할 수 있으므로, 몸무게 리스트의 최솟값과 최댓값을 더해가며 limit보다 작을 경우 두명이 한 보트에 탑승한 것으로 판단하고 문제 풀이를 진행했다. (최솟값과 최댓값을 제거하는 함수가 필요하기에 deque를 사용하였다.)

1. 주어진 몸무게 리스트 sort, queue에 people 리스트를 deque로 추가
2. queue에 2명이상인 경우와 1명인 경우 2가지의 경우의 수로 문제를 해결!
   2-1 ) queue에 사람 수가 2명 이상인 경우 몸무게 최솟값 + 최댓값 > limit인 경우와 아닌 경우로 구분! limit 보다 크다면, 몸무게가 가장 큰 사람을 하나의 보트에만 태운다. queue.pop()으로 해당 인원 리스트에서 제거 limit보다 작다면 두 인원을 queue에서 제거하고 해당 인원들을 한 보트에 태운다.
   2-2 ) 위 방식으로 while문을 진행하여 queue에 인원이 1명인 경우 limit보다 작으면 해당 인원을 보트에 태운다

N개의 최소공배수

문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

• 제한 사항
  arr은 길이 1이상, 15이하인 배열입니다.
  arr의 원소는 100 이하인 자연수입니다.

def solution(arr):
    answer = max(arr)
    while True:
        cnt = 0
        for i in arr:
            if answer % i == 0:
                cnt += 1
            else:
                break
        if cnt == len(arr):
            break
        answer += 1
    return answer

< 풀이 과정 >
주어진 2개의 숫자로 최소공배수를 구하는 문제는 풀어봤으나 주어진 리스트 전체의 최소공배수를 구하는 문제는 처음이어서 나름 시간 투자를 하였다.
for문보다는 while문으로 반복하여 진행하는 것이 효율적이라고 판단하여 진행!

1. 주어진 배열의 최댓값을 answer에 저장하고 while문 내 for문으로 배열을 돌려 가장 큰 값이 주어진 배열 내 숫자들을 모두 나눌 수 있다면 cnt += 1을 진행한다.
2. 주어진 배열의 길이와 cnt값이 동일하다면 최소공배수를 구한 것을 의미하므로 break를 걸어 중단해준다.

H-Index

문제 설명
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

• 제한사항
  과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
  논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

def solution(citations):
    citations.sort()
    for i in range(len(citations)):
        if citations[i] >= len(citations) - i:
            return len(citations) - i
    return 0

< 풀이 과정 >
문제를 보자마자 주어진 citations 리스트를 sort해야겠다는 생각이 들었다.
이후 for 문을 돌려 논문의 인용횟수들 중 h번 이상 인용된 논문 들이어야 하고 이외의 논문이 h번 이하여야 하므로 len(citations) - i로 return하도록 코드를 짰다.

직접 코드로 구현하기 이전 여러 케이스를 머리로 생각해내고 풀어내느라 시간이 좀 걸렸던 문제.

[1차] 캐시

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

• 입력 형식
  캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
  cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
  cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
  각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
• 조건
  캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
  cache hit일 경우 실행시간은 1이다.
  cache miss일 경우 실행시간은 5이다.

def solution(cacheSize, cities):
    answer = 0
    idx = 0
    cache = []
    if cacheSize == 0:
        return len(cities) * 5
    for c in cities:
        city = c.upper()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
        else:
            answer += 5
            if idx < cacheSize:
                cache.append(city)
                idx += 1
            else:
                cache.pop(0)
                cache.append(city)
    return answer

< 풀이 과정 >

문제를 풀기 전 cache hit과 cache miss를 이해하고 문제를 풀었다. 처음들어보는 거라서..
짧게 요약을 하면 cache hit란 캐시 내 찾고자 하는 데이터가 존재함을 의미하고 cache miss란 찾고자 하는 데이터가 없을 때를 의미한다.

1. cache 빈리스트를 생성하고 초기 인덱스 값을 0으로 지정해주었다.
2. for 문으로 cities 리스트를 돌며 대소문자 구분을 통일해주기 위해 각 도시들을 모두 대문자로 처리!
3. 만일 cache내 city가 존재한다면 hit이므로 cache내 도시 제거 후 현재 도시 추가해주고 answer += 1처리
4. cache 내 city가 없다면 miss에 해당하므로 answer += 5 진행!
5. 이때 주어진 캐시사이즈 보다 작아야만 캐시에 포함되므로 이를 인덱스값을 하나씩 추가해주면서 진행하였다.

점프와 순간이동

def solution(n):
    ans = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
            ans += 1
    return ans

< 풀이 과정 >
2칸 씩 순간 이동할 경우 건전지 사용량이 줄지 않고, 1칸씩 이동하면 건전지 사용량이 1씩 줄어든다. 따라서 이를 그래도 구현한 문제

멀리 뛰기

def solution(n):
    dp = [0]*(n+1)
    if n < 3:
        return n
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n] % 1234567

< 풀이 과정 >
동적계획법 dp를 활용하여 n이 3미만이면 dp[n] = n이고 3,(n+1)의 범위에 한해서 dp[n] = dp[n-2] + dp[n-1]로 계산해 dp[n]을 리턴한다.

괄호 회전하기

문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

• 제한사항
  s의 길이는 1 이상 1,000 이하입니다.

def solution(s):
    answer = 0
    for i in range(len(s)):
        stack = []
        s += s[0]
        s = s[1:]
        check = True
        for j in s:
            if j in ['[', '{', '(']:
                stack.append(j)
            else:
                if not stack:
                    check = False
                    break
                if j==']' and stack[-1]=='[' or j=='}' and stack[-1]=='{' or j==')' and stack[-1]=='(':
                    stack.pop()
                else:
                    check = False
                    break
        if not stack and check == True:
            answer += 1
    return answer

< 풀이 과정 >
앞서 비슷한 괄호문제를 풀었기에 비슷한 유형(스택 자료구조)으로 생각하고 문제를 풀었다.
처음 문제를 풀었을 때는 check 없이 진행하였으나 해결하지 못하였고 주어진 stack 이 비어있는 경우와 check 값이 True인 경우일 때만 횟수 + 1하는 방식으로 진행했다.

좀 더 풀어서 설명하자면, 나는 '{', '(', '[' 문자가 스택에 추가되면 이후 문자가 '}',')',']' 아닌 경우 False처리하여 문제를 해결하였다.

1. 주어진 문자열을 순환하기 위해 for문을 사용하였고 주어진 문자열을 왼쪽으로 회전시키는 과정을 리스트의 인덱스로 표현하였다.
2. 주어진 문자열의 문자 j들을 이제 각각 탐색하는데, 초기 문자가 [, (, { 라면 스택에 추가해준다.
3. 아닌 경우의 if문을 2개로 처리하였는데 이유는 다음과 같다.
   3-1) 만일 주어진 s 문자열이 테스트 케이스 4번처럼 (((라면 if stack == []: check = False, break 가 없다면 스택에 append처리를 진행할 수 있게 되고, 결과적으로 3을 리턴하게 된다.

이를 방지하고자, 위 코드 대로 진행했고, stack에는 (, [, { 가 있고 문자 j가 이를 닫아주는 괄호 문자로 구성되어 있다면, 스택 내 문자를 pop하는 과정으로 코드를 진행했다.

행렬의 곱셈

def solution(arr1, arr2):
    answer = [[0]*len(arr2[0]) for _ in range(len(arr1))]
    for i in range(len(arr1)):
        for j in range(len(arr2[0])):
            for k in range(len(arr1[0])):
                answer[i][j] += arr1[i][k] * arr2[k][j]
    return answer

< 풀이 과정 >
행렬곱을 그대로 구현한 문제.
행렬 곱에서 제일 중요한 것은 AXB에 있어서 A의 열과 B의 행의 길이가 같아야한다. 따라서 이를 이용하여 answer 2차원리스트에 len(arr1)는 행을, len(arr2[0])을 열로 나타내어 표현했다.
이후 for문으로 행, 열, len(arr1[0]) 순서대로 순차하며 Product 연산을 진행한다.

👍풀이 하면서 잘했던 점

알고리즘을 구현해내는 사고력이 확실히 요새 늘어난 느낌. 문제를 하도 풀어서 그런가보다. 물론 아직 실력이 많이 부족하고 LV 2도 정답률이 높은 문제들만 풀어서 그런진 몰라도 문제를 보자마자 접근하는 시간이 줄어든 느낌이다.

❗일정

드디어 코테 공부를 시작했던 이유인 naver AI boostcamp 5기 일정이 나왔다!
1차 코테는 1월 13일 시험 예정..
12월 한달 동안 잠을 좀 줄여가면서라도 해야겠다..
12월 6일 ~ 12월 19일은 기말고사와 코테, 중간 중간 SQL Study, Texas 강의... 후....
병행할 것들이 한 둘이 아니지만 최대한 코테 문제 풀이를 소홀히 하지 않으려고 한다.
화이팅해보자!!