리셋 되지 말자

class 3 본문

알고리즘

class 3

kyeongjun-dev 2022. 3. 1. 01:54

[백준 1003] 피보나치 함수 - 다이나믹(dp)

코드

def solution(arr):
    # 첫번째 원소는 0 출력 횟수, 두번째 원소는 1 출력 횟수
    fibo =[
        [1, 0],
        [0, 1]
    ]

    # 2~40까지 0과 1을 출력하는 횟수를 저장([i] = [i-2 + i-1])
    for i in range(2, 41):
        first = fibo[i-2][0]+fibo[i-1][0]
        second = fibo[i-2][1]+fibo[i-1][1]
        fibo.append([first, second])

    # 입력된 각 숫자마다 0과 1을 출력하는 횟수를 출력
    for idx in arr:
        print(fibo[idx][0], fibo[idx][1])

n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))
solution(arr)

 

[백준 11403] 경로 찾기 - 그래프, 플로이드와샬

설명

  • 최단거리를 구하는게 아닌 i에서 j로 갈 수 있는지 만 체크하면 된다.
  • 그래서 거리는 따로 측정하지 않고 갈 수 있으면 1 갈수 없으면 0 으로만 체크한다.
  • 다른점이 있다면 i에서 i로도 갈 수 있는 경우(자기 자신으로)가 있다면, 1로 체크해줘야 한다

코드

def solution(arr):
    for k in range(len(arr)):
        for j in range(len(arr)):
            for i in range(len(arr)):
                if arr[j][k] == 1 and arr[k][i] == 1:
                    arr[j][i] = 1
    
    for j in range(len(arr)):
        for i in range(len(arr)):
            print(arr[j][i], end=' ')
        print()

n = int(input())
arr = []
for i in range(n):
    l = list(map(int, input().split()))
    arr.append(l)
solution(arr)

[백준 1389] 케빈 베이컨의 6단계 법칙 - 그래프, bfs, 플로이드와샬

코드1 - bfs

from collections import deque
def solution(arr):
    # 각 번호의 케빈 베이컨 수 저장
    save = [-1 for _ in range(len(arr))]
    # 가장 작은 케빈 케이컨 수
    min_cnt = 1e9
    for i in range(1, len(arr)):
        # 각 번호의 사람마다 visit 배열 생성
        visit = [-1 for _ in range(len(arr))]
        q = deque([i])
        visit[i] = 0
        while q:
            target = q[0]
            q.popleft()
            for edge in arr[target]:
                if visit[edge] == -1:
                    visit[edge] = visit[target] + 1
                    q.append(edge)
        save[i] = sum(visit)+1
        min_cnt = min(min_cnt, save[i])
    answer = min(save[1:])
    print(save.index(answer))
    

n, m = map(int, input().split())
arr = [deque() for _ in range(n+1)]
for _ in range(m):
    node, edge = map(int, input().split())
    arr[node].append(edge)
    arr[edge].append(node)

solution(arr)

코드2 - 플로이드와샬

def solution(arr):
    for k in range(len(arr)):
        for j in range(len(arr)):
            for i in range(len(arr)):
                arr[j][i] = min(arr[j][i], arr[j][k]+arr[k][i])
    save = []
    for p in arr:
        save.append(sum(p))
    print(save.index(min(save))+1)
    
n, m = map(int, input().split())
arr = []
for i in range(n):
    l = [1e9 for _ in range(n)]
    l[i] = 0
    arr.append(l)
for _ in range(m):
    node, edge = map(int, input().split())
    arr[node-1][edge-1] = 1
    arr[edge-1][node-1] = 1

solution(arr)

[백준 1012] 유기농 배추 - queue, bfs, dfs

코드

from collections import deque
def make_arr(m, n, k):
    arr = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        arr[y][x] = 1
    return arr

def bfs(arr):
    dq = deque()
    # (y, x) 오른쪽, 아래쪽, 왼쪽, 위쪽
    dir = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0]
    ]
    # 연속된 배추구역기 몇개인지 count
    cnt = 0

    # 입력받은 배열 전체를 순회
    for y in range(len(arr)):
        for x in range(len(arr[0])):
            # 0 : 배추가 없는 곳, 1 : 탐색 시작, 2 : 탐색이 완료된 곳
            if arr[y][x] == 1:
                cnt += 1
                arr[y][x] = 2
                dq.append([y, x])
                while len(dq) != 0:
                    t_y = dq[0][0]
                    t_x = dq[0][1]
                    dq.popleft()
                    for i in range(4):
                        # 네 방향으로 탐색
                        if t_y+dir[i][0] < len(arr) and t_x+dir[i][1] < len(arr[0]) and t_y+dir[i][0] >= 0 and t_x+dir[i][1] >= 0:
                            # 네 방향 중 1이 있다면 큐에 insert. insert 하거나 탐색한 곳은 2로 업데이트
                            if arr[t_y+dir[i][0]][t_x+dir[i][1]] == 1:
                                dq.append([t_y+dir[i][0], t_x+dir[i][1]])
                                arr[t_y+dir[i][0]][t_x+dir[i][1]] = 2
                            else:
                                arr[t_y+dir[i][0]][t_x+dir[i][1]] = 2
    print(cnt)

case = int(input())
for _ in range(case):
    # 가로길이, 세로길이, 배추심는 개수
    m, n, k = map(int, input().split())
    bfs(make_arr(m, n, k))

 

[백준 11723] 연결 요소의 개수 - 그래프, bfs, dfs

설명

  • 무방향 그래프의 연결된 노드들의 집합 개수를 구하는 문제
  • 연결이 하나도 안된 노드도 카운트를 해야함
  • bfs로 구현했지만 dfs도 가능

코드

import sys
from collections import deque

input = sys.stdin.readline
def solution(n, m):
    answer = 0
    # 인접행렬 생성
    arr = [
        [0 for _ in range(n+1)] for _ in range(n+1)
    ]
    # 연결된 경우 입력값에 대칭된 위치를 1로 변경(1,2가 입력된 경우 [1][2], [2][1] 두 개를 모두 1로 변경)
    for _ in range(m):
        y, x = map(int, input().split())
        arr[y][x] = 1
        arr[x][y] = 1

    # 방문 여부를 저장하는 배열
    visit = [0 for _ in range(n+1)]

    # 1~n 까지의 노드 순서로 탐색 시작
    for i in range(1, n+1):
        q = deque()
        # 방문하지 않은 노드라면 연결요소개수(answer)를 1 증가시키고 que에 넣은 후 탐색 시작
        if visit[i] == 0:
            answer += 1
            q.append(i)
            visit[i] = 1
        # que가 empty 상태가 될때까지(연결된 모든 에지노드를 탐색할 때까지) 탐색
        while q:
            node = q[0]
            q.popleft()
            for idx, edge in enumerate(arr[node]):
                if idx > 0 and visit[idx] == 0 and edge == 1:
                    q.append(idx)
                    visit[idx] = 1
    # 연결 요소집합의 개수를 출력
    print(answer)
    
n, m = map(int, input().split())
solution(n, m)

[백준 2606] 바이러스 - 그래프, bfs, dfs

설명

  • 11723 연결 요소의 개수 코드를 사용하여 개선
  • 탐색을 시작하는 컴퓨터의 번호와 연결된 컴퓨터를 que에 넣을때 모두 집합(s)에 넣어줌
  • que가 빌때까지(연결된 컴퓨터를 모두 순회하면) 수행한 후, 1번 컴퓨터가 해당 집합에 있다면 집합(s)의 크기에서 1번 컴퓨터를 제외한 len(s)-1을 출력하고 종료한다

코드

import sys
from collections import deque

input = sys.stdin.readline
def solution(n, m):
    # 인접행렬 생성
    arr = [
        [0 for _ in range(n+1)] for _ in range(n+1)
    ]
    # 연결된 경우 입력값에 대칭된 위치를 1로 변경(1,2가 입력된 경우 [1][2], [2][1] 두 개를 모두 1로 변경)
    for _ in range(m):
        y, x = map(int, input().split())
        arr[y][x] = 1
        arr[x][y] = 1

    # 방문 여부를 저장하는 배열
    visit = [0 for _ in range(n+1)]

    # 1~n번 컴퓨터의 순서로 탐색 시작
    for i in range(1, n+1):
        q = deque()
        s = set()
        # 방문하지 않은 컴퓨터라면 s집합에 넣고 que에 넣은 후 탐색 시작
        if visit[i] == 0:
            q.append(i)
            visit[i] = 1
            s.add(i)
        # que가 empty 상태가 될때까지(연결된 컴퓨터를 탐색할 때까지) 탐색
        while q:
            node = q[0]
            q.popleft()
            for idx, edge in enumerate(arr[node]):
                if idx > 0 and visit[idx] == 0 and edge == 1:
                    q.append(idx)
                    s.add(idx)
                    visit[idx] = 1
        # 연결된 집합에 1번 컴퓨터가 들어있다면 1번 컴퓨터를 제외한 연결된 컴퓨터 개수를 출력하고 종료
        if 1 in s:
            print(len(s)-1)
            return
    
n = int(input())
m = int(input())
solution(n, m)

[백준 7576] 토마토 - 그래프, bfs

코드

from collections import deque

def solution(arr, roc_1, visit):
    dir = [
        (0, 1),
        (1, 0),
        (0, -1),
        (-1, 0)
    ]
    q = deque(roc_1)

    while q:
        cj = q[0][0]
        ci = q[0][1]
        q.popleft()

        for i in range(4):
            if cj + dir[i][0] >= 0 and cj + dir[i][0] < len(arr) and ci + dir[i][1] >= 0 and ci + dir[i][1] < len(arr[0]):
                if visit[cj + dir[i][0]][ci + dir[i][1]] == 0 and arr[cj + dir[i][0]][ci + dir[i][1]] != -1:
                    q.append((cj + dir[i][0], ci + dir[i][1]))
                    visit[cj + dir[i][0]][ci + dir[i][1]] = visit[cj][ci] + 1
                else:
                    continue


    answer = 0
    for j in range(len(visit)):
        for i in range(len(visit[0])):
            if visit[j][i] == 0 and arr[j][i] != -1:
                print(-1)
                return
            else:
                answer = max(answer, visit[j][i])
    print(answer-1)
    


m, n = map(int, input().split())
arr = []
visit = []
roc_1 = []
for _ in range(n):
    arr.append(list(map(int, input().split())))
    visit.append([0 for _ in range(m)])
for j in range(len(arr)):
    for i in range(len(arr[0])):
        if arr[j][i] == 1:
            visit[j][i] = 1
            roc_1.append((j,i))
solution(arr, roc_1, visit)

[백준 2178] 미로 탐색 - 그래프, bfs

설명

  • 입력받는 배열 arr과 크기가 같은 visit 배열을 사용한다
  • (0, 0)을 넣고 bfs를 큐가 빌때까지 수행한다
  • 큐에 방문하지 않은 좌표를 넣을 때, visit[ty][tx]에 저장된 값에 1을 더해서 기록한다

코드

from collections import deque

def solution(arr, visit):
    dq = deque([(0, 0)])
    dir = [
        (0, 1),
        (1, 0),
        (0, -1),
        (-1, 0)
    ]

    # 큐가 빌때까지 반복
    while dq:
        ty = dq[0][0]
        tx = dq[0][1]
        dq.popleft()
        for i in range(4):
            if ty+dir[i][0] >= 0 and ty+dir[i][0] < len(arr) and tx+dir[i][1] >= 0 and tx+dir[i][1] < len(arr[0]) and visit[ty+dir[i][0]][tx+dir[i][1]] == 0 and arr[ty+dir[i][0]][tx+dir[i][1]] == 1:
                dq.append((ty+dir[i][0], tx+dir[i][1]))
                visit[ty+dir[i][0]][tx+dir[i][1]] = visit[ty][tx] + 1
    print(visit[-1][-1]+1)


n, m = map(int, input().split())
arr = []
visit = []
for _ in range(n):
    arr.append(list(map(int, list(input()))))
    visit.append([0 for _ in range(m)])
solution(arr, visit)

[백준 2667] 단지번호 붙이기 - bfs, 그래프

코드

from collections import deque

def solution(arr, visit):
    answer = 0
    cnts = []
    for j in range(len(arr)):
        for i in range(len(arr[0])):
            if arr[j][i] == 1 and visit[j][i] == 0:
                answer += 1
                visit[j][i] = 1
                cnts.append(bfs(arr, visit, j, i))
    print(answer)
    cnts.sort()
    for cnt in cnts:
        print(cnt)

def bfs(arr, visit, y, x):
    dq = deque([(y, x)])
    dir = [
        (0, 1),
        (1, 0),
        (0, -1),
        (-1, 0)
    ]
    # 단지 개수
    cnt = 0
    # 큐가 빌때까지 반복
    while dq:
        ty = dq[0][0]
        tx = dq[0][1]
        dq.popleft()
        for i in range(4):
            if ty+dir[i][0] >= 0 and ty+dir[i][0] < len(arr) and tx+dir[i][1] >= 0 and tx+dir[i][1] < len(arr[0]) and visit[ty+dir[i][0]][tx+dir[i][1]] == 0 and arr[ty+dir[i][0]][tx+dir[i][1]] == 1:
                dq.append((ty+dir[i][0], tx+dir[i][1]))
                cnt += 1
                visit[ty+dir[i][0]][tx+dir[i][1]] =  1
    return cnt+1

n = int(input())
arr = []
visit = []
for _ in range(n):
    arr.append(list(map(int, list(input()))))
    visit.append([0 for _ in range(n)])
solution(arr, visit)

[백준 10026] 적록색약 - 그래프, dfs, bfs

코드

import copy

def dfs1(arr, visit):
    dir = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0]
    ]
    # 구역의 수
    answer = 0
    for y in range(len(arr)):
        for x in range(len(arr[0])):
            # 현재 위치가 방문한 적이 없으면 dfs 시작
            if visit[y][x]:
                visit[y][x] = False
                answer += 1
                color = arr[y][x]
                stack = [(y, x)]
                while stack:
                    ty = stack[-1][0]
                    tx = stack[-1][1]
                    stack.pop()
                    for k in range(4):
                        ny = ty + dir[k][0]
                        nx = tx + dir[k][1]
                        if ny >= 0 and nx >= 0 and ny < len(arr) and nx < len(arr[0]) and arr[ny][nx] == color and visit[ny][nx]:
                            visit[ny][nx] = False
                            stack.append((ny, nx))
    print(answer, end=' ')
                        
def solution(arr, visit):
    dfs1(arr, visit)

n = int(input())
arr1 = []
arr2 = []
visit = []
for _ in range(n):
    new = list(input())
    arr1.append(new)

arr2 = copy.deepcopy(arr1)

for j in range(n):
    for i in range(n):
        if arr2[j][i] == 'G':
            arr2[j][i] = 'R'

for y in range(n):
    visit.append([True for _ in range(n)])

solution(arr1, copy.deepcopy(visit))
solution(arr2, copy.deepcopy(visit))

[백준 1074] Z - 분할정복, 재귀

코드

def func(n, h, w):
    # 배열의 가로(세로 길이)
    length = 2**n

    # 1사분면에 있는지 체크
    if h < length//2 and w < length//2:
        return [0, h, w]
    # 2사분면에 있는지 체크
    elif h < length//2 and w >= length//2:
        return [1*(length//2 * length//2), h, w-length//2]
    # 3사분면에 있는지 체크        
    elif h >= length//2 and w < length//2:
        return [2*(length//2 * length//2), h-length//2, w]
    # 4사분면에 있는지 체크
    else:
        return [3*(length//2 * length//2), h-length//2, w-length//2]


n, h, w = map(int, input().split())
answer = 0
while n != 0:
    tmp, h, w = func(n, h, w)
    answer += tmp
    n -= 1

print(answer)

[백준 2630] 색종이 만들기 - 재귀, 분할정복

코드

import sys

input = sys.stdin.readline
d = dict()
d[0] = 0
d[1] = 0
def check(arr, y, x, l):
    start_color = arr[y][x]
    flag = True
    for j in range(y, y + l):
        for i in range(x, x + l):
            if arr[j][i] != start_color:
                flag = False
                break
        if flag == False:
            break
    if flag==False:
        check(arr, y, x, l//2)
        check(arr, y+(l//2), x, l//2)
        check(arr, y, x+(l//2), l//2)
        check(arr, y+(l//2), x+(l//2), l//2)
        return
    elif flag==True:
        d[start_color]+=1

def solution(arr):
    check(arr, 0,0, len(arr))
    print(d[0])
    print(d[1])
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

solution(arr)

[백준 1992] 쿼드트리 - 재귀, 분할 정복

설명

  • 2630 문제와 비슷한 문제다
  • 핵심은 배열 전체가 동일한 숫자가 아니면 4분할을 해야한다는 것이다
  • 즉, 분할해야할 때만 ( ) 괄호가 생긴다
  • 예를들어 [[1, 1, 1,1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]이면 정답 출력은 1이다

코드

def solution(arr, y, x, l):
    color = arr[y][x]
    for j in range(y, y+l):
        for i in range(x, x+l):
            # 나누어야 하면 괄호를 추가하여 나눈다
            if arr[j][i] != color:
                print('(', end='')
                solution(arr, y, x, l//2)
                solution(arr, y, x+l//2, l//2)
                solution(arr, y+l//2, x, l//2)
                solution(arr, y+l//2, x+l//2, l//2)
                print(')', end='')
                return
    print(color, end='')



n = int(input())
arr = []
for _ in range(n):
    l = list(input())
    arr.append(l)

solution(arr, 0, 0, n)

[백준 1780] 종이의 개수 - 재귀, 분할 정복

코드

d ={-1:0, 0:0, 1:0}
def solution(arr, y, x, l):
    color = arr[y][x]
    if l == 1:
        d[color] += 1
        return
    for j in range(y, y+l):
        for i in range(x, x+l):
            if arr[j][i] != color:
                solution(arr, y, x, l//3)
                solution(arr, y, int(x+l*(1/3)), l//3)
                solution(arr, y, int(x+l*(2/3)), l//3)

                solution(arr, int(y+l*(1/3)), x, l//3)
                solution(arr, int(y+l*(1/3)), int(x+l*(1/3)), l//3)
                solution(arr, int(y+l*(1/3)), int(x+l*(2/3)), l//3)

                solution(arr, int(y+l*(2/3)), x, l//3)
                solution(arr, int(y+l*(2/3)), int(x+l*(1/3)), l//3)
                solution(arr, int(y+l*(2/3)), int(x+l*(2/3)), l//3)
                return
    d[color] += 1
    
n = int(input())
arr = []
for _ in range(n):
    l = list(map(int, input().split()))
    arr.append(l)

solution(arr, 0, 0, len(arr))
for cnt in d.values():
    print(cnt)

[백준 1927] 최소 힙 - heap, heapq, 우선순위 큐

코드

import sys
import heapq
def solution(n):
    hq = []
    for _ in range(n):
        num = int(sys.stdin.readline())
        if num == 0:
            if len(hq) == 0:
                print(0)
            else:
                print(hq[0])
                heapq.heappop(hq)
        else:
            heapq.heappush(hq, num)

n = int(input())
solution(n)

[백준 1676] 팩토리얼 0의 개수 - 수학, 큰 수

코드1 - 팩토리얼 사용

from math import factorial

def solution(n):
    string = list(str(factorial(n)))
    cnt = 0
    idx = len(string)-1
    while string[idx] == '0' and idx != -1:
        cnt += 1
        idx -= 1
    print(cnt)


n = int(input())
solution(n)

 

코드2 - 수학적으로 

def solution(n):
    print(n//5+n//25+n//125)

def solution(n):
	cnt = 0
    while n>=5:
    	cnt += n//5
        n //= 5

n = int(input())
solution(n)

[백준 11279] 최대 힙 - 힙, 최대힙

코드

import sys
import heapq
def solution(n):
    hq = []
    for _ in range(n):
        num = int(sys.stdin.readline())
        if num != 0:
            # heapq는 최소힙 이므로, 음수를 같이 넣어서 최대힙처럼 구성
            heapq.heappush(hq, (-num, num))
        else:
            if len(hq)==0:
                print(0)
            else:
                print(hq[0][1])
                heapq.heappop(hq)
n = int(input())
solution(n)

[백준 11286] 절대값 힙 - 힙, 최소힙

코드

import heapq
import sys
def solution(n):
    hq = []
    for _ in range(n):
        num = int(sys.stdin.readline())
        if num == 0:
            if len(hq) == 0:
                print(0)
            else:
                print(hq[0][1])
                heapq.heappop(hq)
        else:
            heapq.heappush(hq, (abs(num), num))

n = int(input())
solution(n)

[백준 1463] 1로 만들기 - dp

코드

def solution(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n == 3:
        return 1
    else:
        arr = [0 for _ in range(n+1)]
        arr[1] = 0
        arr[2] = 1
        arr[3] = 1
        for i in range(4, n+1):
            if i % 3 == 0 and i % 2 == 0:
                arr[i] = min(min(arr[i//3], arr[i//2]), arr[i-1]) + 1
            elif i % 3 == 0 and i % 2 != 0:
                arr[i] = min(arr[i//3], arr[i-1]) + 1
            elif i % 3 != 0 and i % 2 == 0:
                arr[i] = min(arr[i//2], arr[i-1]) + 1
            elif i % 3 != 0 and i % 2 != 0:
                arr[i] = arr[i-1] + 1
    return arr[n]

n = int(input())
print(solution(n))

[백준 9095] 1, 2, 3 더하기 - dp

설명

  • 원래 dp로 풀어야 하는게 맞지만, num 범위가 1~10 까지로 적어서 직접 배열에 넣어서 풀었다.
  • 1, 2, 3 만 각각 1, 2, 4 이고 4~10은 이전 3개의 수를 더한값이다

코드1 - 배열

def solution(t):
    arr = [-1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]
    for _ in range(t):
        n = int(input())
        print(arr[n])
t = int(input())
solution(t)

코드2 - dp

def solution(t):
    arr = [-1, 1, 2, 4]
    for i in range(4, 11):
        arr.append(arr[i-3]+arr[i-2]+arr[i-1])
    for _ in range(t):
        n = int(input())
        print(arr[n])
    
t = int(input())
solution(t)

 

[백준 11726] 2xn 타일링 - dp

설명

  • n이 4개 또는 5개일 때까지 하면 규칙이 보인다
  • n 이 1일때 1, 2일때 2, 3일때 3, 4일때 5, 5일때 8 종류로 배치가 가능하다
  • 보면 n이 3 이상일 때, dp[n-2] + dp[n-1] = dp[n] 임을 확인할 수 있다
  • 문제 조건에 해당하는 10,007로 나눈 나머지를 출력한다

코드

def solution(n):
    if n == 1:
        print(1)
    elif n == 2:
        print(2)
    else:
        dp = [-1, 1, 2]
        for _ in range(n-2):
            dp.append(dp[-1]+dp[-2])
        print(dp[n]%10007)
    
n = int(input())
solution(n)

[백준 11727] 2xn 타일링 2 - dp

설명

  • 타일링1 문제와 다르게 규칙이 잘 보이지 않았다. dp를 푸는 다른 접근방식에 눈을 뜨게된 문제...
  • 2 x n 번째 타일을 만드는 경우에 세 가지 경우로 만드는게 가능
    1. 2 x (n-1) 번째 까지 타일링 후, 2 x 1 타일 하나를 붙이는 경우
    2. 2 x (n-2) 번째 까지 타일링 후, 2 x 1 타일 두 개를 붙인 2 x 2 타일을 붙이는 경우
    3. 2 x (n-2) 번째 까지 타일링 후, 2 x 2 타일을 붙이는 경우
  • 식을 세우면, arr[n] = arr[n-1] + 2*arr[n-2]가 된다

코드

def solution(n):
    arr = [0, 1, 3]
    for _ in range(n-2):
        arr.append(arr[-1] + arr[-2]*2)
    print(arr[n]%10007)

n = int(input())
solution(n)

[백준 2579] 계단 오르기 - dp

설명

  • 조건 1 : 한칸 또는 두칸씩 오를 수 있다
  • 조건 2: 세 칸을 연속으로 밟을 수 없다
  • 위 두 조건을 보면 두 가지로 접근할 수 있을 거 같다
    • 1번. 1칸을 0번 지나왔을 경우 : 이경우는 i-2에서 i로 2칸을 이동하여 왔을 경우
    • 2번. 1칸을 1번 지나왔을 경우 : 이 경우는 i-1에서 i로 1칸을 이동하여 왔을 경우
  • 1번의 경우는 다음 +1칸으로 이동할 수 있다
  • 2번의 경우는 +1칸으로 이동할 수 없다(연속 3칸 못밟음)

코드

n = int(input())
arr = [0 for _ in range(301)]
# dp[i][0] : i-2번째를 밟고 온 경우
# dp[i][1] : i-1번째를 밟고 온 경우
dp = [[0, 0] for _ in range(301)]
for i in range(1, n+1):
    arr[i] = int(input())
    # 1번째 칸에서 출발하는 경우
    if i == 1:
        dp[i][0] = arr[i]
    # 2번째 칸에서 출발하는 경우는 1번째칸을 밟고 왔을 경우와 1번째칸을 뛰어넘고 왔을 경우 총 2개다
    elif i == 2:
        dp[i][0] = arr[i]
        dp[i][1] = dp[i-1][0] + arr[i]
    else:
        dp[i][0] = max(dp[i-2]) + arr[i]
        dp[i][1] = dp[i-1][0] + arr[i]
print(max(dp[n]))

[백준 7662] 이중 우선순위 큐 - 힙

코드

import sys
import heapq
def solution(n):
    max_hq = []
    min_hq = []
    total_cnt = 0
    check = [False for _ in range(n)]
    for id in range(n):
        op, num = sys.stdin.readline().split()
        if op == 'I':
            # heap에 넣을 때 id를 같이 넣어줌
            heapq.heappush(max_hq, [int(num)*-1, id])
            heapq.heappush(min_hq, [int(num), id])
            total_cnt += 1
        elif op == 'D':
            if total_cnt == 0:
                continue
            elif num == '-1':
                while min_hq and check[min_hq[0][1]] != False:
                    heapq.heappop(min_hq)
                check[heapq.heappop(min_hq)[1]] = True
                total_cnt -= 1
            elif num == '1':
                while max_hq and check[max_hq[0][1]] != False:
                    heapq.heappop(max_hq)
                check[heapq.heappop(max_hq)[1]] = True
                total_cnt -= 1
    s = set()
    if total_cnt == 0:
        print('EMPTY')
    else:
        for num, id in min_hq:
            if check[id] == False:
                s.add(num)
        for num, id in max_hq:
            if check[id] == False:
                s.add(-num)
        print(max(s), min(s))

case = int(input())
for _ in range(case):
    n = int(sys.stdin.readline())
    solution(n)

[백준 1697] 숨바꼭질 - bfs

코드

  • 처음에는 dp로 접근했었는데 잘못된 접근방식이었다.
  • input이 10 19이면, 10 -> 20 -> 19 로 2가 나와야 하는데 dp로 접근하면 3이 나오게 된다(10 -> 9 -> 18 -> 19)
  • 이는 타겟이 되는 위치 n에 도달하기 위해 n+1에서 -1을 통해 돌아오는 경우가 고려되지 않기 때문이다.
from collections import deque

def solution(n, k):
    # 방문여부 체크 배열(방문시 True)
    visit = [False for _ in range(100001)]

    # 시작위치 방문 체크
    visit[n] = True

    # 시작위치를 거리 0과 함께 큐에 넣은 상태로 시작
    dq = deque([[n, 0]])

    # 목표위치가 큐의 맨 앞에 올때까지 반복
    while dq[0][0] != k:
        #타겟위치 지정
        front = dq[0]
        loc = front[0]
        dis = front[1]
        dq.popleft()
        # 방문하지 않았고, 0~10만 범위일 경우 타겟 위치의 -1, +1, x2를 큐에 푸시하고 방문 체크
        for i in (loc-1, loc+1, loc*2):
            if i >= 0 and i <= 100000 and visit[i] == False:
                visit[i] = True
                dq.append([i, dis+1])
    # 타겟 위치에 저장된 거리를 출력
    print(dq[0][1])


n, k = map(int, input().split())
solution(n, k)

[백준 16236] 아기 상어 - bfs, 그래프, 구현

실패한 접근방법

  • 같은 거리에 먹을 수 있는 물고기가 여러개 있으면, 위쪽을 최우선 왼쪽을 다음 우선순위로 먹어야 한다
  • 그래서 dir 방향을 위, 왼쪽을 주면 될줄 알았는데 아니었다
  • 예시는 아래 그림과 같이 5번까지 먹으면 크기가 4인 상태로 6번을 먹는다.

  • 다음으로는 이제 보라색 칸을 먹어야 하는데, dir로만 해결하려고 하면 왼쪽 아래([1][1])를 먹게된다.

  • 하지만 문제 조건을 보면, '위'에 있는걸 우선으로 먹어야 함으로, [1][1]이 아닌 [0][4]를 먹어야한다

코드(실패) - 예시4 를 넣으면 60이 나와야 하는데 58이 나오는 코드다

from collections import deque
import copy
def solution(arr, visit, loc, size):
    bfs(arr, visit, loc, size)

def bfs(arr, visit_origin, loc, size):
    # 먹은 물고기 개수
    eat = 0
    # 방향 : 위, 왼쪽 부터 써준다
    dir = [
        (-1, 0),
        (0, -1),
        (1, 0),
        (0, 1)
    ]
    visit = copy.deepcopy(visit_origin) 
    q = deque([loc])
    visit[q[0][0]][q[0][1]] = 1
    cnt = 0
    while q:
        cy, cx = q[0][0], q[0][1]
        q.popleft()
        # 위, 왼쪽, 아래, 오른쪽 방향으로 이동
        for i in range(4):
            ny, nx = cy+dir[i][0], cx+dir[i][1]
            # 방문하지 않았고, 현재 아기상어 크기보다 작거나 같으면 이동
            if 0 <= ny < len(arr) and 0 <= nx <len(arr) and visit[ny][nx] == 0 and arr[ny][nx] <= size:
                # 아기상어 보다 작으면 먹는다
                if 0 < arr[ny][nx] < size:
                    print('eat:', ny, nx)
                    eat += 1
                    visit[ny][nx] = visit[cy][cx] + 1
                    cnt += visit[ny][nx] -1
                    # 먹은 횟수가 아기상어 크기랑 같으면 size를 1 증가시키고 먹은 횟수를 0으로 초기화
                    if eat == size:
                        size += 1
                        eat = 0
                    # print('arr:')
                    # for a in arr:
                    #     print(a)
                    # print()
                    # print('visit:')
                    # for a in visit:
                    #     print(a)
                    # print()
                    # print()
                    # 먹고 나면 q에 넣고 다시 시작
                    q = deque([[ny, nx]])
                    arr[ny][nx] = 0
                    visit = copy.deepcopy(visit_origin)
                    visit[ny][nx] = 1
                    break
                # 아기상어 크기랑 같으면 그냥 지나간다
                else:
                    visit[ny][nx] = visit[cy][cx] + 1
                    q.append([ny, nx])
        
    print(cnt)

n = int(input())
# 상어 배열
arr = []
# 방문 체크 배열
visit = []
# 아기상어의 위치(9) 저장
loc = None
# 아기상어 크기
size = 2
for _ in range(n):
    arr.append(list(map(int, input().split())))
    visit.append([0 for _ in range(n)])
for j in range(n):
    for i in range(n):
        if arr[j][i] == 9:
            arr[j][i] = 0
            loc = [j, i]

solution(arr, visit, loc, size)

새로운 접근법

  • 배열 최대 길이가 20이므로 우선 시간복잡도를 고려하지 않으면
  • 먹을수 있는 좌표를 모두 저장한 뒤 가는데 걸리는 길이, y좌표, x좌표 순서로 정렬한 뒤 가장 작은걸 먹는다
  • 먹은 위치는 0으로 초기화 하고, 먹은 위치에서 다시 bfs를 시작한다
  • bfs 결과가 빈 배열을 반환하면, 먹을수 없는 물고기가 더이상 없으므로 이때 종료한다

코드(성공) 

from collections import deque
import copy
def bfs(arr, visit_origin, loc, size):
    # 먹을 수 있는 물고기들의 좌표 저장
    eatable = []
    # 방향 : 위, 왼쪽 부터 써준다
    dir = [
        (-1, 0),
        (0, -1),
        (1, 0),
        (0, 1)
    ]
    visit = copy.deepcopy(visit_origin) 
    q = deque([loc])
    visit[q[0][0]][q[0][1]] = 1
    while q:
        cy, cx = q[0][0], q[0][1]
        q.popleft()
        # 위, 왼쪽, 아래, 오른쪽 방향으로 이동
        for i in range(4):
            ny, nx = cy+dir[i][0], cx+dir[i][1]
            # 방문하지 않았고, 현재 아기상어 크기보다 작거나 같으면 이동
            if 0 <= ny < len(arr) and 0 <= nx <len(arr) and visit[ny][nx] == 0 and arr[ny][nx] <= size:
                # 아기상어 보다 작으면 eatable 배열에 저장한다
                if 0 < arr[ny][nx] < size:
                    visit[ny][nx] = visit[cy][cx] + 1
                    eatable.append([visit[ny][nx]-1, ny, nx])
                # 아기상어 크기랑 같으면 그냥 지나간다
                else:
                    visit[ny][nx] = visit[cy][cx] + 1
                    q.append([ny, nx])
    if len(eatable) != 0:
        eatable.sort(key=lambda x: (x[0], x[1], x[2]))
        return eatable[0]
    else:
        return -1

def solution(arr, visit, loc, size):
    # 이동한 거리
    move = 0
    # 먹은 물고기 개수
    cnt = 0
    while True:
        # bfs_result : 거리, y, x
        bfs_result = bfs(arr, copy.deepcopy(visit), loc, size)
        if bfs_result == -1:
            break
        else:
            cnt += 1
            move += bfs_result[0]
            arr[bfs_result[1]][bfs_result[2]] = 0
            if cnt == size:
                size += 1
                cnt = 0
            loc = [bfs_result[1], bfs_result[2]]
    print(move)

n = int(input())
# 상어 배열
arr = []
# 방문 체크 배열
visit = []
# 아기상어의 위치(9) 저장
loc = None
# 아기상어 크기
size = 2
for _ in range(n):
    arr.append(list(map(int, input().split())))
    visit.append([0 for _ in range(n)])
for j in range(n):
    for i in range(n):
        if arr[j][i] == 9:
            arr[j][i] = 0
            loc = [j, i]

solution(arr, visit, loc, size)

[백준 5525] IOIOI - 구현

코드

def solution(l, string):
    string = list(string)
    cnt = 0
    i = 0
    answer = []
    # i, i+1, i+2 씩 검사하므로 string의 길이 -2 까지 반복
    while i < len(string)-2:
        if string[i] == 'I':
            # i번째 문자가 I 이면, IOI 패턴이 되는지 확인
            if string[i+1] == 'O' and string[i+2] == 'I':
                # 패턴이 맞으면 cnt를 1증가 (1이면 IOI, 2이면 IOIOI)
                cnt += 1
                # i+2 까지 검사했으므로 인덱스를 +2
                i = i+2
            # i번째 문자가 O 이면, 현재까지 저장한 패턴(cnt)을 저장
            else:
                if cnt > 0:
                    answer.append(cnt) 
                cnt = 0
                i = i+1
        else:
            i = i+1
    # 마지막에 카운트되지 않은 패턴이 있다면 예외처리(answer에 추가)
    cnt_sum = 0
    if cnt != 0:
        answer.append(cnt)

    # 패턴길이에서 카운트해야할 패턴길이를 뺀 길이를 전부 더하여 출력
    for cnt in answer:
        if cnt - l >= 0:
            cnt_sum += cnt - l + 1
    print(cnt_sum)

l = int(input())
input()
string = input()

solution(l, string)

[백준 5430] AC - deque(덱)

설명

  • deque를 사용했는데, 문자열 파싱하는게 더 오래걸렸던 문제

코드

from collections import deque

def solution(p, arr):
    answer = []
    
    sts = 'L'
    for f in p:
        # 'R'이나오면 'L', 'R'로 변경
        if f == 'R':
            if sts == 'L':
                sts = 'R'
            elif sts == 'R':
                sts = 'L'
        # 배열이 비어있는데 'D'면 error 출력하고 끝
        elif f == 'D' and len(arr) == 0:
            print('error')
            return
        # 'D'가 나오고 현재 상태가 'L'이면 왼쪽에서 pop, 'R' 이면 오른쪽에서 pop
        elif f == 'D' and len(arr) != 0:
            if sts == 'L':
                arr.popleft()
            elif sts == 'R':
                arr.pop()

    if sts == 'L':
        for num in arr:
            answer.append(num)
    elif sts == 'R':
        arr = list(arr)[::-1]
        for num in arr:
            answer.append(num)
    print('[',end='')
    for i, num in enumerate(answer):
        if i == len(answer)-1:
            print(num, end='')
        else:
            print(str(num)+',', end='')
    print(']')

t = int(input())
for _ in range(t):
    p = list(input())
    input()
    string = input()
    arr = []
    if string != '[]':
        arr = deque(map(int, string[1:-1].split(',')))
    else:
        arr = deque()
    solution(p, arr)

[백준 18870] 좌표 압축 - 정렬 sort, dict, set

설명

  • 압축된 좌표는 좌표값이 최소값부터 0이다. (-10, -9, 2, 4, 4 => 0, 1, 2, 3, 3)
  • 이를 구하기 위해 입력으로 들어오는 배열을 set을 이용해 중복을 제거해 준 뒤, 정렬해준다.
  • -10, -9, 2, 4를 dict에 차례대로 넣어준다. 이때, 최소값 0부터 1씩 증가시키면 저장한다.

코드

def solution(arr):
    # 중복제거 후 오름차순으로 정렬(-10, -9, 2, 4, 4)
    s = sorted(set(arr))
    d = dict()
    cnt = 0
    # 0부터 1씩 증가시키면서 중복제거한 배열의 수를 차례대로 저장
    for x in s:
        d[x] = cnt
        cnt += 1
    # 배열의 값과 key를 매칭시켜서 cnt로 변경
    for i, num in enumerate(arr):
        arr[i] = d[num]

    # 출력
    for num in arr:
        print(num, end=' ')


input()
arr = list(map(int, input().split()))
solution(arr)

[백준 11659] 구간 합 구하기 4

설명

  • 배열의 길이가 100,000(십만)이고, 입력도 100,000(십만) 이다.
  • N = 100,000, M = 100,000 이고 입력되는 구간이 100,000개 루프동안 1~100,000 이라고 가정하면
  • 100,000 x 100,000 = 100억이므로 시간초과가 된다.
  • 0번 index 부터 각 index까지의 구간합을 구하고, arr[j]에서 arr[i-1]를 빼주면 i~j 구간의 합을 바로 구할수 있다
  • 5, 4, 3, 2, 1을 각 index마다 구간합을 구하면 5, 9, 12, 14, 15이 된다. 입력이 1, 3이면 arr[2] - arr[1-1] = 12 - 0 = 12
  • 편의성을 위해 맨 앞에 0을 하나 넣어줬다

코드

import sys
input = sys.stdin.readline
def solution(arr, m):
    save = [0 for _ in range(len(arr))]
    save_sum = 0
    for i in range(1, len(arr)):
        save_sum += arr[i]
        save[i] = save_sum

    for _ in range(m):
        i, j = map(int, input().split())
        print(save[j]-save[i-1])

n, m = map(int, input().split())
arr = [0]
arr += list(map(int, input().split()))
solution(arr, m)

[백준 9461] 파도반 수열 - dp

코드

def solution(n):
    # ex) 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21
    # arr[i] = arr[i-1] + arr[i-5]
    arr = [0, 1, 1, 1, 2]
    if n <= 4:
        print(arr[n])
    else:
        for i in range(5, n+1):
            arr.append(arr[i-1]+arr[i-5])
        print(arr[n])

t = int(input())
for _ in range(t):
    n = int(input())
    solution(n)

[백준 17626] Four Squares - dp

접근법

  • 1부터 12까지의 n을 제곱수 끼리 더할 수 있는 수를 적어보고 이를 dp[i] 배열로 보자
1 = 1 (1)
2 = 2 (1+1)
3 = 3 (1+1+1)
4 = 1 (2의 제곱)
5 = 2 (4 + 1)
6 = 3 (4 + 1 + 1)
7 = 4 (4 + 1 + 1 + 1)
8 = 2 (4 + 4)
9 = 1 (3의 제곱)
10 = 2 (9 + 1)
11 = 3 (9 + 1 + 1)
12 = 3 (4 + 4 + 4)
  • n이 특정 수의 제곱이면 1이다
  • dp[1]=1, dp[2]=2 이고 dp[3] 은 dp[1]+dp[2] 이다
  • dp[4] 는 2의 제곱이므로 1이다
  • dp[5] 는 dp[1]+d[4] 이다. 이렇게 나가다보면 dp[i]는 dp[1]+dp[i-1], dp[2]+dp[i-2], dp[3]+dp[i-3] ... 중에서 최소값이다. 물론 dp[i]가 어떤 수의 제곱이면 1이다. 이런 방식으로 찾을 수 있는데, 이러면 시간 복잡도가 5만 x 5만 x 5만이 된다.

코드 - 시간초과

n = int(input())
arr = [0 for _ in range(n+1)]

for i in range(1, n+1):
    if i == 1:
        arr[i] = 1
    elif i == 2:
        arr[i] = 2
    elif i**(1/2)%1 == 0:
        arr[i] = 1
    else:
        arr[i] = 1e9
        for j in range(1, i//2+1):
            #print(arr[j], arr[n-j])
            arr[i] = min(arr[i], arr[j]+arr[i-j])
        #     print(j, i-j)
        # print()

print(arr[n])

 

[백준 9375] 패션왕 신해빈 - 조합, 해쉬, dict

설명

  • 의상 이름과 의상 종류가 주어진다.
  • 의상 이름은 중복되지 않으므로 고려하지 않으므로 의상 종류만 카운트해서 dict에 저장한다.
  • 조합을 적용하여 각 의상 종류마다 +1(아무것도 입지 않은 경우)을 해줘서 곱한다.
  • 맨 마지막에 아무것도 입지 않을 경우는 제외해야 하므로 -1을 해준다.

코드

from collections import defaultdict
def solution(n):
    d = defaultdict(int)
    for _ in range(n):
        name, category = input().split()
        d[category] += 1
    answer = 1
    for cnt in d.values():
        answer *= cnt+1
    print(answer-1)


t = int(input())
for _ in range(t):
    n = int(input())
    solution(n)

[백준 1541] 잃어버린 괄호

코드

arr = list(input())

flag = '+'
tmp = ''
answer = 0
for c in arr:
    if c != '+' and c != '-':
        tmp += c
    else:
        if flag == '+':
            answer += int(tmp)
            tmp = ''
        elif flag == '-':
            answer -= int(tmp)
            tmp = ''
            
        if flag == '+' and c == '-':
            flag = '-'
if flag == '+':
    print(answer+int(tmp))
else:
    print(answer-int(tmp))

[백준 6064] 카잉 달력

접근1

  • <x:y>가 <1:1>에서 <x:y>까지 증가한다.
  • 여기서, 1 1에서 x y(마지막 해)가 될때까지 걸리는 해는 x와 y의 최소공배수이다
  • 0<M, N<40,001 이라서 하나씩 증가시키면 시간 초과가 안날것 같지만 시간초과가 난다. M:39,999, N:40,000일 경우 대략 40만x40만 = 1억 6천만(?) 이게 맞는진 모르겠지만 시간 초과 날듯하다

접근2

  • 10:12 가 3:9가 되는 과정을 보면,
  • 1:1(첫 번째) 에서 9:9(아홉 번째) > x = 9, y = 9
  • 9:9(아홉 번째) 에서 1:9(21 번째) > x = 1, y = 21
  • 1:9(21 번째) 에서 3:9(33 번째) > x = 3, y = 33
  • 1:1에서 x:y 까지 증가하는 수 n:m 중에 m을 N씩 증가시키면서 cnt에 N을 더한다
  • 이때 cnt가 M, N의 최소 공배수 보다 커지기 전에 cnt%M이 x면 cnt 출력. cnt보다 커지기전에 x가 안나오면 false

예외처리

  • 4 8 4 4 가 input이면 정답이 4여야 한다 (1 1, 2 2, 3 3, 4 4)
  • 조건을 if y%n == x: 이런식으로 잡아버리면, 4 % 4 는 0이므로 4인 x로 판단되지 않게된다
  • 그래서 (y-1)%n +1 로 처리하여 (4-1)%4 + 1 = 4가 되도로 한다(출처 감사합니다)

코드

from math import lcm

def solution():
    n, m, x, y = map(int, input().split())
    if n==x and m==y:
        print(1)
        return
    flag = True
    lcm_n_m = lcm(n, m)
    while y <= lcm_n_m:
        if y % n == x:
            print(y)
            flag = False
            break
        y += m

    if flag:
        print(-1)

t = int(input())
for _ in range(t):
    solution()

 

저작자표시

'알고리즘' 카테고리의 다른 글

class 4  (0) 2022.05.04
Tip  (0) 2022.02.27
[백준 18111] 마인크래프트 - 브루트포스  (0) 2022.01.20
[백준 1874] 스택 수열 - 스택  (0) 2022.01.19
[백준 1966] 프린터 큐 - 큐  (0) 2022.01.18
'알고리즘' Related Articles more
Comments