Intro

코딩테스트를 준비하다보면 아래의 경우를 고려하여 완전 탐색해야하는 문제를 쉽게 만날 수 있습니다. 

1) 서로 다른 N개중 순서를 생각하지 않고 M개를 선택하는 경우의 수

2) 서로 다른 N개중 순서를 생각하지 않고 중복을 허용하여 M개를 선택하는 경우의 수 

3) 서로 다른 N개중 순서를 생각하고 M개를 선택하는 경우의 수

4) 서로 다른 N개중 순서를 생각하고 중복을 허용하여 M를 선택하는 경우의 수

따라서, 위의 경우를 효율적으로 탐색하기 위해서 시간 복잡도와 모듈을 활용한 탐색 방법을 정리해 두려고 합니다.

저는 주로 python3를 사용하여 ps하기 때문에 itertools 패키지 사용법과 함께 정리하겠습니다.

위의 경우를 순서대로 알아보겠습니다.

1) 조합 (combiantions)

시간복잡도: nCr = n!/(n-r)!r!

from itertools import combinations

nums = [1,2,3]
for i in range(1, len(nums)+1):
	print(list(combinations(nums,i)))
    
# [(1,), (2,), (3,)]
# [(1, 2), (1, 3), (2, 3)]
# [(1, 2, 3)]

2) 중복 조합

시간복잡도: nHr=n+r−1Cr = (n+r-1)! / r!

from itertools import combinations_with_replacement

nums = [1,2,3]
for i in range(1, len(nums)):
	print(list(combinations_with_replacement(nums, i)))
    
# [(1,), (2,), (3,)]
# [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

3) 순열

시간복잡도: nPr = n!/(n-r)!

from itertools import permutations

nums = [1,2,3]
for i in range(1, len(nums)):
	print(list(permutations(nums, i)))
    
# [(1,), (2,), (3,)]
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

4) 중복 순열

시간복잡도: n∏r = n^r

from itertools import product

nums = [1,2,3]
for i in range(1, len(nums)):
	print(list(product(nums, repeat = i)))
    
# [(1,), (2,), (3,)]
# [(1, 1), (1, 2), (1, 3),(2, 1), (2, 2), (2, 3),(3, 1), (3, 2), (3, 3)]

문제보러가기

- 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))