📖 문제

📖 예제

📖 풀이

def solution(n, s):
    if n > s:
        return [-1]

    initial = s // n
    answer = [initial for _ in range(n)]

    idx = len(answer) - 1
    for _ in range(s % n):
        answer[idx] += 1
        idx -= 1
    return answer

n이 s보다 클 경우 각 요소의 값은 0을 가질 수 밖에 업게 되므로 [-1]을 출력한다. 이외의 경우 s // n 값을 각 요소에 초기화해주고 나머지 값은 요소에 1씩 증가시켜주는 방식으로 할당한다.

📖 문제

📖 예제

📖 풀이

def solution(skill, skill_trees):
    answer = 0
    for skill_tree in skill_trees:
        arr = ''
        for i in skill_tree:
            if i in skill:
                arr += i
        if arr == skill[:len(arr)]:
            answer += 1
    return answer

문자열을 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

from collections import Counter

def solution(topping):
    answer = 0
    Dict = Counter(topping)
    sets = set()
    for i in topping:
        sets.add(i)
        Dict[i] -= 1
        if Dict[i] == 0:
            Dict.pop(i)
        if len(sets) == len(Dict):
            answer += 1
    return answer

Counter() 함수를 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(progresses, speeds):
    answer = []
    cnt = 0
    time = 0
    while progresses:
        if progresses[0] + time * speeds[0] >= 100:
            progresses.pop(0)
            speeds.pop(0)
            cnt += 1
        else:
            if cnt > 0:
                answer.append(cnt)
                cnt = 0
            time += 1
    answer.append(cnt)
    return answer

progresses의 첫 번째 항이 100을 넘을 때 까지 time을 1씩 증가시킨다. progresses의 첫 번째 항이 100을 넘을 경우 그 항을 제거해주고 cnt를 1 증가시킨다. progresses의 첫 번째 항이 100이 넘지 않을 경우 증가한 값 만큼의 cnt를 answer에 추가한 후 cnt를 0으로 설정하고 앞의 과정을 반복한다.

📖 문제

📖 예제

📖 풀이

def solution(land):
    answer = 0
    for i in range(1, len(land)):
        for j in range(4):
            if j == 0:
                land[i][j] += max(land[i-1][1], land[i-1][2], land[i-1][3])
            elif j == 1:
                land[i][j] += max(land[i-1][0], land[i-1][2], land[i-1][3])
            elif j == 2:
                land[i][j] += max(land[i-1][0], land[i-1][1], land[i-1][3])
            else:
                land[i][j] += max(land[i-1][0], land[i-1][1], land[i-1][2])

    return max(land[-1])

동적 계획법 알고리즘을 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(dirs):

    UDRL = {'U':(1,0), 'D':(-1,0), 'R':(0,1), 'L':(0,-1)}
    y, x = 0, 0
    sets = set()

    for i in dirs:
        dy, dx = UDRL[i]
        ny = y+dy
        nx = x+dx
        if -5<=ny<=5 and -5<=nx<=5:
            sets.add(((ny,nx), (y,x)))
            sets.add(((y,x), (ny,nx)))
            y = ny
            x = nx
    return len(sets) // 2

자료구조 딕셔너리와 집합을 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(prices):
    answer = [0] * len(prices)

    for i in range(len(prices)):
        cnt = 0
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                cnt += 1
            else:
                cnt += 1
                break
        answer[i] = cnt
    return answer

answer을 prices 값의 수 만큼 0으로 초기화시킨 후 특정 인덱스의 값보다 연속적으로 큰 수만큼 cnt를 올려 answer의 인덱스에 초기화 한다. 자신의 값보다 큰 수를 발견하더라도 cnt를 1 증가시키고 중단해야한다.

📖 문제

📖 예제

📖 풀이

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0

    return BFS(begin, target, words)

def BFS(begin, target, words):
    queue = deque()
    queue.append((begin, 0))
    while queue:
        now, step = queue.popleft()

        if now == target:
            return step

        for word in words:
            cnt = 0
            for i in range(len(now)):
                if now[i] != word[i]:
                    cnt += 1
            if cnt == 1:
                queue.append((word, step+1))

target 단어가 words에 없을 경우 0을 리턴한다. target 단어가 words에 있을 경우 BFS를 활용하여 문제를 해결할 수 있다. begin이 target까지 도달하는 최단거리를 구하는 문제이다.

📖 문제

📖 예제

📖 풀이

def solution(scoville, K):
    import heapq

    answer = 0
    heapq.heapify(scoville)

    while scoville:
        if scoville[0] >= K:
            return answer
        if len(scoville) == 1:
            return -1
        new = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        heapq.heappush(scoville, new)
        answer += 1

자료 구조 heap을 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(numbers):
    stk = []
    answer = [-1] * len(numbers)

    for i in range(len(numbers)): 
        while stk and numbers[stk[-1]] < numbers[i]:
            answer[stk.pop()] = numbers[i]
        stk.append(i)
    return answer

자료 구조 스택을 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

from collections import deque

dx = [0,0,-1,1]
dy = [1,-1,0,0]

def BFS(x, y, maps):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<= nx<len(maps) and 0<=ny<len(maps[0]) and maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx,ny))

def solution(maps):
    BFS(0, 0, maps)
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[-1][-1]

BFS를 활용하여 최단거리 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(word):
    from itertools import product

    words = []
    for i in range(6):
        c = product(['A', 'E', 'I', 'O', 'U'], repeat=i)
        for i in c:
            words.append(''.join(i))

    words.sort()
    return words.index(word)

product() 함수를 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(n, works):
    import heapq

    if n >= sum(works):
        return 0

    works = [-w for w in works]
    heapq.heapify(works)

    for _ in range(n):
        i = heapq.heappop(works)
        i += 1
        heapq.heappush(works, i)
    return sum([w ** 2 for w in works])

여러번의 반복동안 가장 큰 수에 연산을 수행해야 할 경우 heapq.heapify()를 다음과 같이 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def convert(k, base):
    arr = '0123456789ABCDEF'
    q, r = divmod(k, base)
    if q == 0:
        return arr[r]
    else:
        return convert(q, base) + arr[r]

def solution(n, t, m, p):
    answer = ''
    number = []
    for i in range(t*m):
        cnv = convert(i, n)
        for j in cnv:
            number.append(j)

    for i in range(p-1, t*m, m):
        answer += number[i]
    return answer

convert() 함수를 이용해 모든 수를 n진수로 변형한 뒤 튜브가 말해야하는 수만 따로 모아서 출력한다.

📖 문제

📖 예제

📖 풀이

def solution(msg):
    answer = []
    Dict = {}
    # 딕셔너리에 알파벳 저장
    for i in range(1, 27):
        Dict[chr(i+64)] = i

    while True:
        if msg in Dict:
            answer.append(Dict[msg])
            break
        for i in range(1, len(msg)):
            if msg[:i+1] not in Dict:
                answer.append(Dict[msg[:i]])
                Dict[msg[:i+1]] = len(Dict) + 1
                msg = msg[i:]
                break
    return answer

알파벳을 딕셔너리에 저장하는 방법을 배울 수 있었다.

📖 문제

📖 예제

📖 풀이

def DFS(i, n, computers, visited):
    visited[i] = 1
    for j in range(n):
        if visited[j] == 0 and computers[i][j] == 1:
            DFS(j, n, computers, visited)

def solution(n, computers):
    answer = 0
    visited = [0] * n
    for i in range(n):
        if visited[i] == 0:
            DFS(i, n, computers, visited)
            answer += 1
    return answer

DFS를 활용해 다음 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(operations):
    import heapq
    heap = []
    max_heap =[]
    for i in operations:
        i = i.split()
        if i[0] == 'I':
            heapq.heappush(heap, int(i[1]))
            heapq.heappush(max_heap, (int(i[1])*-1, int(i[1])))
        else:
            if not heap:
                pass
            elif i[1] == '1':
                num = max(heap)
                heap.remove(num)
                heapq.heappop(max_heap)
            else:
                num = max(max_heap)
                max_heap.remove(num)
                heapq.heappop(heap)
    if heap:
        return [heapq.heappop(max_heap)[1], heapq.heappop(heap)]
    else:
        return [0,0]

heap 자료구조는 최소힙을 기본으로 구성되어있기 때문에 큰 수를 빼는 것을 고려하여 -1을 곱한 값을 우선순위로 저장할 max_heap도 heap과 함께 준비한다.

📖 문제

📖 예제

📖 풀이

def solution(triangle):
    answer = 0
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])

    return max(triangle[-1])

동적계획법을 활용하여 문제를 해결할 수 있다.

📖 문제

📖 예제

📖 풀이

def solution(n, k):
    answer = 0
    num = ''
    # k진수로 변환하는 방법
    while n > 0:
        num = str(n % k) + num
        n = n // k
    num = num.split('0')

    for i in num:
        if i != '':
            if int(i) < 2:
                continue
            else:
                check = True
                # 소수 확인
                for j in range(2, int(int(i)**0.5)+1):
                    if int(i) % j == 0:
                        check = False
                        break
                if check:
                    answer += 1
    return answer

해당 문제를 통해 k진수로 변환하는 방법과 소수를 확인하는 가장 효율적인 방법인 '에라토스테네스의 체'를 배울 수 있었다.

1. 특정 수를 k진수로 변환하기 위해서 특정 수에서 k를 나눈 나머지를 기존 수의 앞으로 붙여주는 수행을 특정 수가 0이 될 때까지 반복해준다.
2. 어떤 수가 소수가 아니라면, 그 수의 최소 소인수는 그 수의 제곱근 이하에 존재한다는 사실을 바탕으로 제곱근까지만 확인하여 나누어 떨어지는 수가 있는지를 확인한다.

📖 문제

📖 예제

📖 풀이

def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        term = []
        for i in leaves:
            term.append(i + num)
            term.append(i - num)
        leaves = term
    for i in leaves:
        if i == target:
            answer += 1
    return answer

입력 배열 numbers에서 값을 하나씩 불러와 기존에 저장되어 있는 배열 leaves의 값들에 +와 -연산을 수행한 뒤 leaves를 새롭게 초기화해준다.