[알고리즘] 문제 풀이

목표

코드를 치기 전에, 조건을 정확히 이해하고 주제를 정한 뒤 시간복잡도를 계산한다.

각 로직의 세부사항(분기 조건, 반복 조건, 함수 시그니처)를 이해하고 손으로 작성한 뒤에 코드를 작성한다.

 

 

---

 

 

도넛과 막대 그래프

 

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

import sys
sys.setrecursionlimit(1_000_000)

N = 1_000_001
edge_in = [0] * N
edge_out = [[] for _ in range(N)]
result = [0, 0, 0]
visited = [False] * N

def solution(edges):
    for a, b in edges:
        edge_in[b] += 1
        edge_out[a].append(b)
        
    additional_node = None
    for node in range(1, N):
        if is_additional_node(node):
            additional_node = node
            break
    
    for adj in edge_out[additional_node]:
        index = dfs(adj, visited)
        if not index:
            index = 0
            
        result[index] += 1
    
    return [additional_node] + result
    
    
def is_additional_node(n):
    return not edge_in[n] and len(edge_out[n]) >= 2


def dfs(cur, visited):
    if visited[cur]:
        return
    
    visited[cur] = True
    if len(edge_out[cur]) == 2:
        return 2
    
    if not edge_out[cur]:
        return 1
    
    for adj in edge_out[cur]:
        if not visited[adj]:
            return dfs(adj, visited)

 

포인트

재귀 함수 스택을 조절해야한다.

edge_in은 들어오는 간선의 수만 저장해도 충분하다.

 

 

---

 

 

석유 시추

 

https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=python3

프로그래머스

 

from collections import defaultdict
import sys
sys.setrecursionlimit(250_000)

color = [0]
N = 500
visited = [[False]*N for _ in range(N)]
oil = defaultdict(int)

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


def solution(land):    
    r, c = len(land), len(land[0])
    
    for i in range(r):
        for j in range(c):
            if land[i][j] and not visited[i][j]:
                color[0] += 1
                dfs(i, j, land, r, c)
    
    max_value = 0
    for j in range(c):
        cur_sum = calculate_oil(j, land, r)
        max_value = max(max_value, cur_sum)
    
    return max_value


def dfs(i, j, land, r, c):
    if visited[i][j]:
        return
    
    oil[color[0]] += 1
    land[i][j] = color[0]
    visited[i][j] = True
    for d in range(4):
        nx, ny = i+dx[d], j+dy[d]
        if 0 <= nx < r and 0 <= ny < c and land[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny, land, r, c)


def calculate_oil(column, land, r):
    result = 0
    unique = set()
    
    for i in range(r):
        if land[i][column] not in unique:
            unique.add(land[i][column])
            result += oil[land[i][column]]
    
    return result

 

 

---

 

 

 

광물 캐기

 

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

 

from itertools import combinations


cost = {
    "dia": {"diamond": 1, "iron": 1, "stone": 1},
    "iron": {"diamond": 5, "iron": 1, "stone": 1},
    "stone": {"diamond": 25, "iron": 5, "stone": 1}
}

cost_by_index = {
    "dia": [0] * 15,
    "iron": [0] * 15,
    "stone": [0] * 15
}

def solution(picks, minerals):
    dia, iron, stone = picks
    sum_picks = sum(picks)
    picks = ["dia", "iron", "stone"]
    
    # brute force 풀이
    # 곡괭이의 순서를 무작위로 선택함
    # 곡괭이 순서가 결정되면 그 순서에서 나오는 피로도 결정되기 때문에
    # 곡괭이와 인덱스로 피로를 구할 수 있는 cost_by_index 정의한다.
    for pick in picks:
        for idx_pick in range(sum_picks):
            s = idx_pick*5
            e = s+5
            e = e if len(minerals) >= e else len(minerals)
            for idx_m in range(s, e):
                cur_minerals = minerals[idx_m]
                cost_by_index[pick][idx_pick] += cost[pick][cur_minerals]
    
    min_value = 10_000
    for dia_idxes in combinations(range(sum_picks), dia):
        cur_value = 0
        for idx in dia_idxes:
            cur_value += cost_by_index["dia"][idx]
        
        rest_idxes = [i for i in range(sum_picks) if i not in dia_idxes]
        for iron_idxes in combinations(rest_idxes, iron):
            stone_idxes = [i for i in range(sum_picks) if i not in dia_idxes+iron_idxes]
            
            tmp = cur_value
            for idx in iron_idxes:
                cur_value += cost_by_index["iron"][idx]
            
            for idx in stone_idxes:
                cur_value += cost_by_index["stone"][idx]
                
            min_value = min(min_value, cur_value)
            cur_value = tmp

    return min_value if min_value != 10_000 else 0

 

def solution(picks, minerals):
    def solve(picks, minerals, fatigue):
        if sum(picks) == 0 or len(minerals) == 0:
            return fatigue
        result = [float('inf')]
        for i, fatigues in enumerate(({"diamond": 1, "iron": 1, "stone": 1},
                                      {"diamond": 5, "iron": 1, "stone": 1},
                                      {"diamond": 25, "iron": 5, "stone": 1},)):
            if picks[i] > 0:
                temp_picks = picks.copy()
                temp_picks[i] -= 1
                result.append(
                    solve(temp_picks, minerals[5:], fatigue + sum(fatigues[mineral] for mineral in minerals[:5])))
        return min(result)

    return solve(picks, minerals, 0)

 

정석 풀이는 그리디와 정렬을 이용한 것이지만,

같은 것이 있는 순열로 계산했을 때, 약 80만 정도의 반복을 가지므로 brute force로도 풀 수 있다.

하지만 구현의 방법에 따라 큰 차이를 보일 수 있는데

위는 조합을 이용한 풀이, 아래는 백트래킹 풀이이다.

 

 

---

 

 

리코쳇 로봇

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

from collections import deque


dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

def solution(board):
    
    # 시작 지점
    s_r, s_c = None, None
    R, C = len(board), len(board[0])
    for i in range(R):
        for j in range(C):
            if board[i][j] == "R":
                s_r, s_c = i, j
    
    answer = int(1e9)
    q = deque([(s_r, s_c, 0)])
    visited = [[False]*C for _ in range(R)]
    while q:
        r, c, cnt = q.popleft()
        if visited[r][c] or cnt >= answer:
            continue
            
        visited[r][c] = True
        for d in range(4):
            nr, nc = r, c
            while True:
                nr, nc = nr+dr[d], nc+dc[d]
                if 0 <= nr < R and 0 <= nc < C and board[nr][nc] != "D":
                    continue
                break
            
            nr, nc = nr-dr[d], nc-dc[d]
            if board[nr][nc] == "G":
                answer = cnt+1
            
            if not visited[nr][nc]:
                q.append([nr, nc, cnt+1])
    
    return answer if answer != int(1e9) else -1

 

문제 풀이

격자무늬, max 100줄

RGD, 시작, 목표, 장애물

움직임 -> 직선 -> 장애물 or 벽

최소 움직임 -> 격자 탐색, bfs (현재 위치, cnt)

 

bfs(현재 위치, cnt)

deque 사용, 시작위치 G와 cnt 0 초기 원소

현재 cnt answer 보다 크면 탐색 x

4방향 반복, while 멈출 때까지 무한 반복

멈추면 목표지점 확인

방문 안 했으면 큐 추가