문제보러가기

- https://school.programmers.co.kr/learn/courses/30/lessons/43238

풀이

• 이 문제는 입국심사를 기다리는 사람이 1,000,000,000 명인 경우를 고려해 이진 탐색 방법을 떠올려야한다.
• 10억인 경우를 완전탐색 할 수 없다. 이진 탐색을 할경우 O(log2(N))으로 약 30 번만에 탐색이 가능하다.
• 우리가 찾으려는 시간은 주어진 심사대를 모두 사용하여 가장 빨리 입국심사를 마무리할 수 있는 시간이다.
• 따라서, 가장 빠른 시간을 찾기 위해서는 각 심사대에서 처리한 사람수의 합이 주어진 n과 같아지는 경우를 찾아야 한다.
• 이를 코드로 구현하면 boared += mid//time으로 식을 세우고, 이를 만족하는 경우를 찾아 이진 탐색을 하면 된다.

코드

def solution(n, times):
    answer = 0

    left = 0
    right = max(times)*n

    while left <= right:
        mid = (left + right) // 2
        boarded = 0
        for time in times:
            boarded += mid//time
        if boarded >= n:
            right = mid - 1
        else:
            left = mid +1
    answer = left
    return answer

문제보러가기

- https://school.programmers.co.kr/learn/courses/30/lessons/84512

풀이

• 시간복잡도: 중복조합 2**i (i=1~5) => 32임으로 모든 경우 탐색 가능
• 순서를 구하기 위해 먼저 모음 길이가 다른 모음 단어를 모두 조합하여 단어장에 추가하여줍니다.
• 모듬은 중복될 수 있으며, 길이가 1~5까지의 단어임으로 파이썬 itertools의 product를 사용하여 중복 조합을 하였습니다.
• 모든 단어를 구한 후 단어장을 오름차순으로 정렬하고, 주어진 word의 순서를 반환합니다.

코드

from itertools import product

def solution(word):

    alphabet = ['A','E','I','O','U']
    all_word = []
    for i in range(1,6):
        for p in product(alphabet,repeat=i):
            p = ''.join(p)
            all_word.append(p)

    all_word.sort()

    return all_word.index(word)+1

문제보러가기

- https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

풀이

• 기출을 통해 느낀바로는 카카오는 시간 혹은 기간을 사용한 문제를 좋아하는 것 같습니다.
• 이 문제 또한 주어진 String 값을 시간(초)으로 변환하고, 주어진 포맷으로 반환하여야 합니다.
• 따라서 strTosec, secTostr 함수를 구현하여 주어진 값을 활용할 수 있도록 했습니다.
• 또한, 주어진 범위가 00:00:01 이상 99:59:59 임으로 100시간 즉 360,000초 입니다.
• 즉, 영상 시간의 초 단위 사이즈로 배열을 잡는데 무리가 없음을 알 수 있습니다.
  • view = [0 for _ in range(play_sec+1)]
• logs를 순회하며 i초에 시청하는 사람수를 업데이트 하고 구간합을 구하는 방법을 우선적으로 떠올리게 됩니다.
• 하지만 그렇게 구현을 하게되면 logs를 순회하며 업데이트를 할때O(len(logs)시청시간) = 300,000*360,000 => 약 1000억으로 시간복잡도를 통과하지 못하게 된다.
• 따라서, 구간의 시작(+1), 구간의 끝(-1)을 len(logs) 만큼 표시하고 view[i] = view[i] +view[i-1]으로 한번에 구간별 시청자 수를 업데이트 하게되면 O(len(logs) + 영상시간) = 300,000 +360,000 으로 개선할 수 있다.
• 여기서 수학적 인사이트가 필요합니다.
• 최종적으로 광고를 가장 많이 시청한 구간을 찾기위해서 우리는 i 시간에서 i+adv_sec 사이의 시청자수가 가장 많은 구간을 찾아야 합니다.
• 이를 위해서, 위의 식을 다시 한번 사용하여 모든 구간의 시청자를 누적합니다.
• 그리고, view[i] - view[i-adv_sec] (구간 누적 시청자) 가 가장 많은 시간을 탐색합니다.

코드

def strTosec(s):
    return int(s[:2])*3600 + int(s[3:5])*60 + int(s[6:]) 

def secTostr(n):
    return f'{str(n//3600).zfill(2)}:{str((n%3600)//60).zfill(2)}:{str((n%3600)%60).zfill(2)}'

def solution(play_time, adv_time, logs):

    play_sec = strTosec(play_time)
    adv_sec = strTosec(adv_time)

    view = [0 for _ in range(play_sec+1)]

    for log in logs:
        start_sec = strTosec(log[:8])
        end_sec = strTosec(log[9:])
        view[start_sec] +=1
        view[end_sec] -=1

    for i in range(1, len(view)):
        view[i] += view[i-1]

    for i in range(1, len(view)):
        view[i] += view[i-1]

    max_view = view[adv_sec-1]
    answer = 0

    for i in range(adv_sec, play_sec):
        tmp = view[i]-view[i-adv_sec]
        if max_view < tmp:
            max_view = tmp
            answer = i-adv_sec+1

    return secTostr(answer)

문제보러가기

- https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

풀이

• 주어진 쿼리 조건에 따라 정보를 완전탐색하면 정확성 TC는 통과합니다.
• 하지만,효율성 TC를 통화하기 위해서는 기존 탐색의 시간복잡도 O(len(query)len(info)) = 100,00050,000 => 50억 에서 개선이 필요합니다.
  • 탐색의 시간 복잡도를 줄이기 info의 모든 카테고리를 key로 갖고 int[]를 value로 갖는 딕셔너리를 만들고, info의 점수를 list에 담아줍니다.
  • 여기서, 점수 조건을 탐색하는 방법으로 이진탐색을 사용하여 O(len(qeury)log2(len(info)) = 100,00016 => 160만으로 시간 복잡도를 개선할 수 있습니다.
  • 애초에 주어진 조건을 읽고 100,000과 50,000를 보고 효율성 TC를 통과할 수 있는 접근법을 떠올리고 접근해야하는 문제였다는 것을 알 수 있습니다.
• 이진 탐색을 직접 구현할 수도 있지만, 파이썬에서는 bisect 모듈을 사용할 수 있습니다.
• query의 점수 이상인 사람들을 탐색하여야 함으로 disect_left를 사용해 lower boud 이진 탐색을 하면 조건을 만족하는 사람의 수를 구할 수 있습니다.
  
  

코드

from bisect import bisect_left
from itertools import combinations
from collections import defaultdict

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    for i in info:
        i =i.split()
        condition = i[:-1]
        score = int(i[-1])
        for n in range(5):
            case = list(combinations([0,1,2,3],n))
            for c in case:
                tmp = condition.copy()
                for idx in c:
                    tmp[idx] = '-'
                key = "".join(tmp)
                dic[key].append(score)

    for value in dic.values():
        value.sort()

    for q in query:
        q = q.replace("and", "").split()
        target_key = "".join(q[:-1])
        target_score = int(q[-1])
        cnt = 0
        if target_key in dic:
            target_list = dic[target_key]
            idx = bisect_left(target_list, target_score)
            cnt = len(target_list)-idx
        answer.append(cnt)

BOJ_2217 로프 -Python3

문제분석

1. 관찰
- n개의 로프 중 k 개의 로프를 선택하는 모든 경우를 탐색한다.
- K개의 로프중 '가장 w가 작은 로프'에 '로프개수'를 곱한값. 즉, '최소값*로프개수'이 최대 감당 가능한 무게가 된다.

이를 시간 복잡도를 고려해 구현하면
내림차순으로 로프를 정렬하여
'k번째 로프(최소값)*k개의 로프'로 '최대 감당 가능 무게'를 갱신해 값을 구한다.  

2. 복잡도
- O(N) = 1만 가능

3. 자료구조
- 로프 int[]

해결코드

import sys
si = sys.stdin.readline

n = int(si())
ropes = [int(si()) for _ in range(n)]
ropes.sort(reverse=True)
values = []

for i in range(n):
    values.append(ropes[i]*(i+1)) # 최소값*로프개수 
print(max(values))

BOJ_1463 1로 만들기 -Python3

문제분석

1. 관찰
- 입력: 1000000 => 백만
- N%3 == 0 => nxt = N / 3
- N%2 == 0 => nxt = N / 2
- nxt = N - 1
- 출력: N을 1로 만드는 연산의 최소 횟수 

- 3 으로 나누기, 2로 나누기, 1빼기 순으로 진행할 수로 연산을 줄일 수 있다.

구하려는 값은 N을 1로 만드는 연산의 최소 횟수이다.
N이 1이 될때연산의 횟수는 이전의 연산에 영향을 받는다.
=> dp   1~N까지 기억하여 연산, cnt는 1,2,3이 되는데 필요한 연산 횟수를 초기화 하고 N이 될때 필요한 연산을 1에서 부터 N이 될때 까지 보텀엄 방식으로 연산한다.
dp  : 0 1 2 3 4 5 6 7 ...
cnt : 0 0 1 1 ... 점화식

보텀업 방식으로 연산

2. 복잡도
- O(N) = 10**6 >> 10만 가능

3. 자료구조
- dp : int[]

해결코드

import sys
si = sys.stdin.readline

N = int(si())
dp = [0 for _ in range(N+1)]  

for n in range(2,N+1): # 2부터 N이 될때 까지 필요한 연산횟수 리턴
    # 1을 더하는 방식 2,3을 곱하는 방식 연산 횟수 비교하여 초기화
    if n%3==0 and n%2==0: 
        dp[n] = min(dp[n-1], dp[n//2], dp[n//3])+1
    elif n%3==0 and n%2!=0:
        dp[n] = min(dp[n-1], dp[n//3])+1
    elif n%3!=0 and n%2==0:
        dp[n] = min(dp[n-1], dp[n//2])+1
    else:
        dp[n] = dp[n-1] + 1 # dp[2], dp[3] 각각 연산횟수 1,1로 초기화됨
print(dp[N]) 

배운점

다이나믹 프로그래밍은 
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 문제에서도 동일하다.
는 규칙을 만족하는데

이 문제를 계속 고민하다보니 

1을 만들기 위한 최소연산 횟수는 이전의 연산 횟수를 구하는 것의 반복임을 발견하게 되었다.

맨 처음에는 dp 배열을 연산에서 어떻게 활용하여야 하나 고민되었는데,
문제에서 구하려는 값이 N을 1로 만드는데 필요한 최소연산 횟수 임으로 
N+1길이의 dp 배열에서 연산횟수를 기록하여 연산을 할 수 있다는 것을 이해하였다.