본문 바로가기

Algorithm202

BOJ 2096 - 내려가기 문제 백준 온라인 저지 - 2096번 풀이 과정 전형적인 DP 문제이지만 메모리 제한이 빡셉니다. 슬라이딩 윈도우 를 활용해서 memo 2차원 배열을 2 * 3 의 크기로 지정해서 값을 구하면 되는데 문제는 처음에 top-down 방식으로 접근했다가 board 배열의 크기를 줄일 방법이 없어서 계속 메모리 초과가 발생했습니다. 대신에 bottom-up 방식으로 변경하고 board 를 미리 입력 받는 것이 아니라 한 줄씩 입력 받아서 사용하는 것으로 변경하여 문제를 해결할 수 있었습니다. 코드 import sys N = int(input()) def solution(): min_memo = [[-1] * 3 for _ in range(2)] max_memo = [[-1] * 3 for _ in range(.. 2021. 3. 18.
BOJ 14716 - 현수막 문제 백준 온라인 저지 - 14716번 풀이 과정 현수막 내부에서 인접한 1 을 탐색해 모든 글자들의 개수를 찾는 BFS 문제입니다. 복잡한 규칙 없이 각 좌표를 탐색하며 아직 방문하지 않은 1 이 발견되면 BFS 를 수행하고 글자 수를 증가시키면 됩니다. 코드 import sys from collections import deque M, N = list(map(int, sys.stdin.readline().split())) board = [list(map(int, sys.stdin.readline().split())) for _ in range(M)] dx = [-1, -1, -1, 0, 1, 1, 1, 0] dy = [-1, 0, 1, 1, 1, 0, -1, -1] def bfs(x, y, visit.. 2021. 3. 18.
BOJ 14923 - 미로 탈출 문제 백준 온라인 저지 - 14923번 풀이 과정 시작 지점에서 목표 지점에 도달하는 최단 경로를 찾는 BFS 문제입니다. 단 벽이 존재할 경우 1회에 한해서 벽을 부수고 이동할 수 있기 때문에 상태 공간을 다음과 같이 정의합니다. visit[x][y][magic] : (x, y) 지점에 남은 마법의 횟수 magic 을 이용하여 도달 한 경우가 있는지 이후 목표 지점에 도달하면 거리 바용을 반환하면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) Hx, Hy = list(map(int, sys.stdin.readline().split())) Ex, Ey = list(map(.. 2021. 3. 18.
BOJ 17406 - 배열 돌리기 4 문제 백준 온라인 저지 - 17406번 풀이 과정 주어진 조건대로 배열 A 를 돌리며 배열의 최소값을 찾는 브루트포스 문제입니다. 회전 연산의 개수 K 가 크지 않기 때문에 순열을 생성하고 모든 경우에 대응해서 최소값을 찾으면 됩니다. 코드 import sys import copy from itertools import permutations N, M, K = list(map(int, sys.stdin.readline().split())) board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] operation = [list(map(int, sys.stdin.readline().split())) for _ in range(K)] .. 2021. 3. 18.
BOJ 1543 - 문서 검색 문제 백준 온라인 저지 - 1543번 풀이 과정 주어진 문자열에서 해당하는 단어가 몇 개 존재하는지 찾는 완전 탐색 문제입니다. 속도를 높이기 위해 문자열 비교 알고리즘을 함께 활용할 수도 있을 것 같은데 입력이 크지 않기 때문에 O(N^2) 의 시간 복잡도로 해결할 수 있습니다. 코드 import sys documents = sys.stdin.readline().strip() word = sys.stdin.readline().strip() def solution(): answer, idx = 0, 0 while idx 2021. 3. 18.
BOJ 11403 - 경로 찾기 문제 백준 온라인 저지 - 11403번 풀이 과정 임의의 한 정점에서 다른 모든 정점까지의 도달 가능성을 판단하는 문제입니다. 다대다 관계의 도달 가능성이기 때문에 각각의 정점에서 DFS 를 수행하는 방법도 있지만 플로이드 와샬 을 사용해서 구할수도 있습니다. 코드 import sys N = int(input()) graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] def floyd(): global graph for k in range(N): for u in range(N): for v in range(N): graph[u][v] = graph[u][v] or (graph[u][k] and graph[k][v]) def so.. 2021. 3. 18.

티스토리툴바