본문 바로가기

Algorithm202

BOJ 6593 - 상범 빌딩 문제 백준 온라인 저지 - 6593번 풀이 과정 시작 지점에서 목표 지점에 도달하기 위한 최단 거리를 구하는 BFS 문제입니다. 빌딩이 3차원이기 때문에 상태공간을 다음과 같이 정의해줍니다. visit[z][x][y] = z 층의 (x, y) 지점에 방문했는지 유무를 저장 여기서 z 축 을 첫번째 인덱스로 지정한 것은 구현상의 편의를 위한 것입니다. 각 지점들을 방문할 때 동서남북 및 위층, 아래층 까지 같이 탐색을 수행하며 도달 여부를 판단해주면 됩니다. 코드 import sys from collections import deque L, R, C = 0, 0, 0 building = [] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] dz = [1, -1] def bfs(start.. 2021. 3. 18.
BOJ 16397 - 탈출 문제 백준 온라인 저지 - 16397번 풀이 과정 BFS 를 통해 목표 숫자에 도달하기 위한 최소 버튼 횟수를 구하는 문제입니다. 각각의 버튼을 누를 수 있는 조건이 주어져 있으므로 이를 기준으로 탐색을 수행하면됩니다. 숫자에 대한 연산(맨 앞자리 감소)은 Python의 슬라이싱을 활용하면 쉽게 구현할 수 있습니다. 코드 import sys from collections import deque N, T, G = list(map(int, sys.stdin.readline().split())) INF = 100000 def bfs(start): q = deque() visit = [0 for _ in range(INF)] q.append((start, 0)) visit[start] = 1 while q: h.. 2021. 3. 18.
BOJ 2563 - 색종이 문제 백준 온라인 저지 - 2563번 풀이 과정 색종이의 좌표값을 이용해서 겹친 부분의 넓이를 구하는 구현 문제입니다. 색종이를 놓을 도화지를 board 로 정의하고 각각의 색종이로 인해 덮인 부분을 1로 표기하면 겹치는 부분을 포함한 넓이를 쉽게 구할 수 있습니다. 코드 import sys N = int(input()) papers = [] for _ in range(N): papers.append(list(map(int, sys.stdin.readline().split()))) def solution(): board = [[0]*100 for _ in range(100)] # 색종이 채우기 for r, c in papers: for row in range(r, r+10): for col in rang.. 2021. 3. 18.
BOJ 1963 - 소수 경로 문제 백준 온라인 저지 - 1963번 풀이 과정 목표 지점에 도달하기 위한 최단 경로를 구하는 문제이므로 BFS 를 통해 답을 구했습니다. 우선 현재 숫자에서 변경 가능한 자리수는 총 4개이므로 각 자리수에 0~9의 숫자를 하나씩 넣어보며 그로 인해 생성된 숫자가 소수일 경우 큐에 넣어줬습니다. 이때 소수인지 판별하는 알고리즘은 O(root(N)) 의 시간 복잡도를 가지므로 주어진 제한 시간내에 충분히 수행 가능합니다. 코드 import sys from collections import deque def is_prime(n): if n 2021. 3. 18.
BOJ 4195 - 친구 네트워크 문제 백준 온라인 저지 - 4195번 풀이 과정 친구 관계를 갱신하면서 친구 네트워크에 몇 명이 있는지 구하는 문제입니다. 이는 직관적으로 유니온 파인드 자료구조를 사용해서 해결할 수 있다는 것을 알 수 있습니다. 친구 관계가 추가될 때마다 그 둘을 union 해준 뒤 생성된 집합의 크기를 반환해주면 됩니다. 이때 입력으로 문자열이 주어지므로 해싱 을 통해 접근할 수 있도록 딕셔너리 자료형을 사용한 것에 유의합니다. 코드 import sys def union(u, v): u, v = find(u), find(v) if u == v: return if rank[u] > rank[v]: u, v = v, u parent[u] = v if rank[u] == rank[v]: rank[v] += 1 size[v.. 2021. 3. 18.
BOJ 17626 - Four Squares 문제 백준 온라인 저지 - 17626번 풀이 과정 특정 수를 만들기 위한 최소 제곱수의 개수를 구하는 문제입니다. 만약 N 의 제곱수를 구하기 위해서는 최대 N**0.5 까지만 검사해보면 됩니다. 때문에 모든 경우의 수를 완전 탐색 하는 방법도 있을 수 있지만 이 경우 중복 검사로 인해 시간초과를 피하지 못하며 따라서 이를 최적화하기 위해 동적 계획법 을 사용해야합니다. dp(n): n을 나타내기 위한 최소 제곱수의 개수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. do(n) = min(dp(n - k^2), dp(n - (k - 1)^2), ... dp(n - 1)) + 1 코드 import sys N = int(input()) def solution(): dp = [-1] * (N + 1.. 2021. 3. 18.

티스토리툴바