백준 1463 1로 만들기 파이썬 - 다이나믹 프로그래밍(DP), 동적 계획법

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 (동적 계획법) 다이나믹 프로그래밍이란, 한 번 계산한 부분을 메모리에 저장해두어 일일이 다시 계산하지 않고, 필요할 때마다 불러오면서 계산을 빠르게 할 수 있는 알고리즘이다. 1로 만들기 점화식 dp[N] = min(dp[N-1], dp[N//2], dp[N//3]) + 1 # 1로 만들기 N = int(input()) dp = [0] * (N+4) dp[1] = 0 dp[2] = 1 dp[3] = 1 # 점화식 dp[N] = min(dp[N-1], dp[N//2], dp[N//3]) + ..

• format_list_bulleted 공부하자!/알고리즘
• · 2022. 2. 26.
• textsms

백준 14502 연구소 파이썬 - DFS, BFS

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하..

• format_list_bulleted 공부하자!/알고리즘
• · 2022. 2. 19.
• textsms

백준 5397 키로거 파이썬

문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 1차 시도) 왼쪽에 값이 없고 이 들어왔을 때의 처리를 잘못해줘서 런타임 에러 발생. elif j not in {'', '-'}: left.append(j) 이걸 추가해서 처리해주었다. 2차 시도) 계속 런타임 에러만 뜨다가 시간 초과가 떴는데, 리스트에서 자꾸 뭘 움직이고 넣고 하는 것 때문이었다. 스택으로 바꿔주면서 해결! 최종) 왼쪽, 오른쪽 스택을 만들어서 커서가 있다고 가정하고 시작 문자가 들어오면..

• format_list_bulleted 카테고리 없음
• · 2021. 11. 4.
• textsms

백준 2309 일곱 난쟁이 파이썬

문제 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 괜히 조합 combination 이런거 쓰려고 했다가 오히려 망한 케이스.. 그냥 쉽게 생각해서, 9명 중 2명을 제외했을 때 합이 100이면 그걸 출력하면 된다! nlist = [] for _ in range(9): nlist.append(int(input())) num1 = 0 num2 = 0 for i in range(8): for j in range(i+1, 9): if sum(nlist) - (nlist[i] + nlist[j]) == 100: num1 =..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 11. 4.
• textsms

프로그래머스 | 거리두기 확인하기

문제 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr dr = [-1, 1, 0, 0, -1, 1, -1, 1, -2, 2, 0, 0] dc = [0, 0, -1, 1, -1, -1, 1, 1, 0, 0, -2, 2] def solution..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 9. 10.
• textsms

백준 4963 섬의 개수 파이썬 - bfs

문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net from collections import deque import sys dr = [-1, 1, 0, 0, -1, 1, -1, 1] dc = [0, 0, -1, 1, -1, 1, 1, -1] def bfs(x, y): queue.append((x, y)) m[x][y] = cnt while queue: x, y = queue.popleft() for i in range(8): nx = x + dr[i] ny = y + dc[i] if 0

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 9. 9.
• textsms

백준 7576번 토마토 파이썬 - bfs

문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net from collections import deque import sys m, n = map(int, sys.stdin.readline().split()) t = [[0] * m for i in range(n)] queue = deque() dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1] for i in range(n): line = list(map(int, sys.stdin.readline().split())) for ..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 9. 9.
• textsms

백준 1012번 유기농 배추 파이썬 - bfs

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net from collections import deque import sys t = int(input()) dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1] def bfs(x, y, f): queue = deque() queue.append((x, y)) f[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dr[i] ny = y + dc[i] if 0

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 9. 9.
• textsms

백준 2178번 미로 탐색 파이썬 - bfs

from collections import deque import sys n, m = map(int, sys.stdin.readline().split()) X = [[0] * m for i in range(n)] for i in range(n): line = sys.stdin.readline() for j in range(m): X[i][j] = int(line[j]) dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1] queue = deque() queue.append((0, 0)) while queue: x, y = queue.popleft() for i in range(4): nx = x + dr[i] ny = y + dc[i] if 0

• format_list_bulleted 카테고리 없음
• · 2021. 9. 9.
• textsms

백준 2667번 단지번호붙이기 파이썬

from collections import deque import sys N = int(input()) M = [[0] * N for _ in range(N)] for i in range(N): line = sys.stdin.readline() for j in range(N): M[i][j] = int(line[j]) dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1] def bfs(x, y): queue = deque() queue.append((x, y)) M[x][y] = 0 cnt = 1 global num num += 1 while queue: x, y = queue.popleft() for i in range(4): nx = x + dr[i] ny = y + dc[i] if n..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 9. 7.
• textsms