Haribo Blog

알고리즘, 문제풀이, ML, AI

스티커 모으기(2)

2021-03-02

Haribo

프로그래머스 Summer/Winter_Coding(~2018)

Lv.4 DP

도둑질 문제와 100% 동일

def solution(sticker):
    if len(sticker) < 3 : return max(sticker) # 스티커갯수 3개가 안될경우
    x1, y1, z1 = sticker[0], max(sticker[:2]), max(sticker[0]+sticker[2], sticker[1]) #첫집 터는 경우
    x2, y2, z2 = 0, sticker[1], sticker[2] # 첫집 안터는 경우
    for i in sticker[3:]:
        x1, y1, z1 = y1, z1, max(x1, y1)+i
        x2, y2, z2 = y2, z2, max(x2, y2)+i
    return max(x1, y1, y2, z2)

Read All

올바른 괄호의 갯수

2021-03-02

Haribo

프로그래머스

Lv.4 DP
카탈랑 수 나무위키

카탈랑 수 응용
```
from math import comb
solution = lambda n : comb(2 * n, n) / (n + 1)
```
Read All

숫자 블록

2021-03-02

Haribo

프로그래머스

Lv.4

def divisor(m) :
    for i in range(2, int(m**0.5)+1) :
        if m%i == 0 and (measure := m//i) <= 10000000 : return measure
    return 1 if m > 1 else 0

def solution(begin, end):
    return [divisor(x) for x in range(begin, end+1)]

Read All

선입 선출 스케줄링

2021-03-01

Haribo

프로그래머스

Lv.4 BinarySearch

이진 탐색 알고리즘

def solution(n, cores):
    min_ = min(cores) * (n//len(cores))  
    max_ = max(cores)* (n//len(cores))  
    while min_ < max_ :
        t = (min_+max_)//2
        cnt_jobs = sum(t//core + 1 for core in cores)
        if cnt_jobs >= n :
            max_ = t
        else :
            min_ = t + 1
    free_cores_at_t = [i for i, core in enumerate(cores) if min_ % core == 0]
    left_jobs_at_t = n - sum((min_-1)//core + 1 for core in cores)
    return free_cores_at_t[left_jobs_at_t - 1] + 1

Read All

게임 맵 최단거리

2021-03-01

Haribo

프로그래머스 찾아라_프로그래밍_마에스터

Lv.4 DFS/BFS

기본적인 BFS 문제.

import numpy as np
def solution(maps):
    board = np.pad(maps, ((1,1),(1,1)), 'constant', constant_values=0).tolist() # 1칸씩 패딩
    n, m = len(board)-2, len(board[0])-2 # 원본 맵 크기
    d = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 이동 벡터
    que = [[1, 1, 1]] # h, w, cost 
    while que :
        h, w, cost = que.pop(0)
        if cost > n*m : continue # 목표지점까지 못가는 경우
        if (h, w) == (n, m) : return cost # 목표지점 도달 했을 경우
        for next_h, next_w in [[h+dh, w+dw] for dh, dw in d] :
            if board[next_h][next_w] != 0  : # 벽이 아닌 경우
                que.append([next_h, next_w, cost+1])
                board[next_h][next_w] = 0 # 이미 지나간 길은 벽으로 막음
    return -1

Read All

사칙연산

2021-02-28

Haribo

프로그래머스 찾아라_프로그래밍_마에스터

Lv.4 DP

최적 행렬곱셈 업그레이드 문제. 하지만 2가지 풀이가 존재한다.

import re
def solution(arr):
    num = re.findall('\d+', (k := ''.join(arr)))
    sign = re.findall('\D', k )
    n = len(num)
    dp_max = [[-1e9]*n for _ in range(n)]
    dp_min = [[1e9]*n for _ in range(n)]

    for i in range(n) :
        dp_max[i][i] = int(num[i])
        dp_min[i][i] = int(num[i])

    for gap in range(1, n) :
        for i in range(n-gap) :
            for k in range(i, (j := i+gap)) :
                if sign[k] == '+' :
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k+1][j])
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k+1][j])
                else :
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] - dp_min[k+1][j])
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] - dp_max[k+1][j])
    return dp_max[0][-1]

Read All

매출 하락 최소화

2021-02-28

Haribo

프로그래머스 2021_KAKAO_BLIND_RECRUITMENT

Lv.4 DFS/BFS DP Tree

코드

코드

from collections import defaultdict
def solution(sales, links):
    global graph, DP
    graph = defaultdict(list)
    for v1, v2 in links :
        graph[v1-1].append(v2-1)
    DP = [[0, 0, 0] for _ in range(len(sales))]
    dfs(sales, 0)
    return min(DP[0][0], DP[0][1])
def dfs(sales, node) :
    if node not in graph :
        DP[node][1] = sales[node]
    else :
        for child in graph[node] :
            dfs(sales, child) 
        children = graph[node]
        flag = sum(DP[child][2] for child in children)
        DP[node][1] = sales[node] + (s := sum(min(DP[child][0] , DP[child][1]) for child in children))
        DP[node][0] = s if flag else s + min(DP[child][1] - DP[child][0] for child in children)
        DP[node][2] = 1 if DP[node][1] < DP[node][0] else 0

Read All

트리 트리오 중간값

2021-02-27

Haribo

프로그래머스 월간_코드_챌린지_시즌1

Lv.4 DFS/BFS

from collections import defaultdict, deque
from copy import deepcopy
def level(node, levels) :
    levels[node] = -1
    que = deepcopy(graph[node])
    level = 0
    while que :
        for _ in range(len(que)) :
            child = que.popleft()
            if not levels[child] :
                levels[child] =  level + 1
                que.extend(deepcopy(graph[child]))
        level += 1
    return levels

def solution(n, edges):
    global graph
    graph = defaultdict(deque)
    for v1, v2 in edges:
        graph[v1-1].append(v2-1)
        graph[v2-1].append(v1-1)
    v1 = level(0, [0]*n)
    v2 = level(v1.index(max(v1)), [0]*n)
    if v2.count((max_ := max(v2))) >= 2 :
        return max_ 
    else :
        v3 = level(v2.index(max_), [0]*n)
        return max_ if v3.count((max_ := max(v3))) >= 2 else max_ - 1

Read All

도둑질

2021-02-25

Haribo

프로그래머스

Lv.4 DP

def solution(a):
    x1, y1, z1 = a[0], max(a[:2]), max(a[0]+a[2], a[1])
    x2, y2, z2 = 0, a[1], a[2]
    for i in a[3:]:
        x1, y1, z1 = y1, z1, max(x1, y1)+i
        x2, y2, z2 = y2, z2, max(x2, y2)+i
    return max(x1, y1, y2, z2)

빡고수 코드

Read All

코딩 테스트 준비

2021-02-15

Haribo

프로그래머스 노트

코딩테스트

코딩테스트를 위해 어려운 문제, 지난 코딩테스트 문제들만 골라 풀다보니 문득 특정 알고리즘들이 약하다는 것을 깨닫고 프로그래머스 Level1 문제부터 차근차근 풀어보고 느낀점이 무조건 Level1 부터 풀고 공부해야 합니다. 각 Level에 따라 필수적으로 익숙해져야하는 부분들이 몇가지 있었습니다.

Read All

7/23