👨💻📱✍️🎢314 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. BOJ 1303 - 전쟁 - 전투 문제 백준 온라인 저지 - 1303번 풀이 과정 두 세력간의 규모를 측정하는 BFS 문제입니다. W 와 B 로 나누어진 컴포넌트의 크기를 구하면 되는데 이때 BFS 를 활용하고 각 컴포넌트의 크기를 구할때마다 제곱한 값을 세력 규모에 더해주면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) board = [list(sys.stdin.readline().strip()) for _ in range(M)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def in_range(x, y): return 0 2021. 3. 18. BOJ 1260 - DFS와 BFS 문제 백준 온라인 저지 - 1260번 풀이 과정 DFS 와 BFS 연산을 구현하는 간단한 문제입니다. 먼저 입력으로 받은 간선 정보로 그래프를 생성하고 이후 DFS 와 BFS 함수를 통해 탐색을 수행합니다. 코드 import sys from collections import deque sys.setrecursionlimit(10 ** 6) def bfs(graph, start): q = deque() visit = [0] * (N + 1) order = [] q.append(start) visit[start] = 1 while q: here = q.popleft() order.append(here) for there in sorted(graph[here]): if not visit[there]: visi.. 2021. 3. 18. BOJ 6550 - 부분 문자열 문제 백준 온라인 저지 - 6550번 풀이 과정 두 개의 문자열이 주어질 때 한 문자열이 다른 문자열에 포함되는지 판단하는 문제입니다. 문자가 연속으로 나타나야한다는 조건이 없기 때문에 검사할 조건이 되는 문자열의 인덱스를 하나씩 증가시키면서 다른 문자열에 해당 인덱스에 해당하는 문자가 존재하는지 판단하면 됩니다. 코드 import sys def solution(s, t): si = 0 for ti in range(len(t)): if t[ti] == s[si]: si += 1 if si == len(s): return 'Yes' return 'No' if __name__ == '__main__': while True: line = sys.stdin.readli.. 2021. 3. 18. 이전 1 ··· 23 24 25 26 27 28 29 ··· 53 다음
