Haribo Blog

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

선입 선출 스케줄링

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

최적의 행렬 곱셈

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

8/23