Haribo Blog

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

매출 하락 최소화

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

최적의 행렬 곱셈

2021-02-05

Haribo

프로그래머스

Lv.4 DP

def solution(matrix_sizes):
    n = len(matrix_sizes)
    d = matrix_sizes[0] + [x[1] for x in matrix_sizes[1:]]
    dp = [[0]*n for _ in range(n)]
    for gap in range(1, n) :
        for i in range(n-gap) :
            for k in range(i, (j := i+gap)) :
                l = dp[i][k] + dp[k+1][j] + d[i]*d[k+1]*d[j+1]
                dp[i][j] = min(dp[i][j], l) if dp[i][j] else l
    return dp[0][-1]

참고블로그

Read All

징검다리

2021-02-04

Haribo

프로그래머스

Lv.4 BinarySearch

징검다리 건너기

입국심사

두 문제를 합쳐놓은 문제다. 대충설명 할꺼니까 위에 두 문제 모르면 공부ㄱ

import math
def solution(distance, rocks, n):
    rocks.sort()
    min_, max_ = 1, distance
    while min_ < max_ :
        destroy = 0; piv_rock = 0
        estimate_min_distance = (min_+max_) // 2 
        for rock in rocks :
            if rock - piv_rock < estimate_min_distance : destroy += 1
            else : piv_rock = rock
        if destroy > n : max_ = estimate_min_distance
        else : min_ = estimate_min_distance + 1
    return min_ - 1

Read All

3xn 타일링

2021-02-03

Haribo

프로그래머스

Lv.4 DP

def solution(n):
    if n%2 != 0 : return 0
    n_2 = 3
    n_1 = 11
    for i in range(3, n//2+1) :
        n_1, n_2 = (4*n_1 - n_2) % 1000000007, n_1
    return n_1

탈인간 코드. 어떻게 이런 패턴을 발견한건지 경이로워서 가져와봄. 이거패턴 무슨 방식인지 좀 알려주셈 난 도저히 모르겠음

def solution(n):
    pa, pb, pc, a, b, c = 1, 0, 0, 0, 0, 2
    for _ in range(1, n):
        pa, pb, pc, a, b, c = a, b, c, (c + pa) % 1000000007, c, (b + a * 2) % 1000000007
    return a

Read All

짝수 행 세기

2021-02-02

Haribo

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

Lv.4 DP

from collections import defaultdict
from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
def C(n,k): return comb(n,k)
def solution(a):
    one_cnt = [sum(ones) for ones in zip(*a)] # 각열 1의 갯수
    DP = defaultdict(int,{(rows := len(a))-one_cnt[0]:comb(rows, one_cnt[0])}) # 1열까지 계산한 DP
    for ones in one_cnt[1:]: # DP[2][j] 부터 계산
        next_DP = defaultdict(int)
        for even_rows in DP:
            odd_rows = rows-even_rows
            for add_one in range(max(0,ones-odd_rows), min(ones,even_rows)+1): # range 범위는 미만이기때문에 +1
                next_DP[even_rows+ones-2*add_one] += DP[even_rows] * C(even_rows, add_one) * C(odd_rows, ones-add_one)%(10**7+19)
        DP = next_DP
    return DP[rows]

Read All

지형 이동

2021-02-01

Haribo

프로그래머스 Summer/Winter_Coding(2019)

Lv.4 DFS/BFS

import heapq
def solution(land, height):
    N = len(land)
    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    board = [[0]*N for _ in range(N)]
    que = [(0, 0, 0)] 
    answer = 0
    while que :
        cost, h, w = heapq.heappop(que)
        if board[h][w] : continue
        board[h][w] = 1
        answer += cost
        cur_height = land[h][w]
        for next_h, next_w in [[h+dh, w+dw] for dh, dw in d if 0 <= h+dh < N and 0 <= w+dw < N] :
            next_height = land[next_h][next_w]
            next_cost = n_cost if (n_cost := abs(cur_height - next_height)) > height else 0
            heapq.heappush(que, (next_cost, next_h, next_w))
    return answer

Read All

숫자 게임

2021-01-31

Haribo

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

Lv.3

def solution(A, B):
    A.sort()
    B.sort()
    a = b = 0
    for _ in range(len(A)) :
        if A[a] < B[b] :
            a += 1
        b += 1
    return a

A 의 원소 a 보다 큰 B의 원소 중 b 의 최소값들의 갯수를 구하는 문제다.

a 보다 큰 b들 중 최소값의 갯수

Read All

9/24