본문 바로가기

🏃 algorithm/boj105

BOJ 2644 - 촌수계산 문제 백준 온라인 저지 - 2644번 풀이 과정 문제 조건을 통해 각 자식은 오직 하나의 부모만 주어지므로 사이클 없는 무방향 그래프로 나타낼 수 있습니다. 따라서 촌수를 계산하고 싶은 두 사람중 임의로 한명을 선택한 뒤 다른 한명에 도달하는 거리를 계산하면 답을 구할 수 있습니다. 이때, 도달 가능성 유무는 DFS 를 통해 계산된 거리값을 통해 알 수 있도록 하였습니다. 코드 import sys n = int(input()) target = list(map(int, sys.stdin.readline().split())) m = int(input()) adj = [[] for _ in range(n+1)] for _ in range(m): frm, to = list(map(int, sys.stdin.re.. 2021. 6. 9.

BOJ 10026 - 적록색약 문제 백준 온라인 저지 - 10026번 풀이 과정 입력된 board 의 크기가 크지 않으므로 DFS 탐색을 통해 모든 구간을 찾아줬습니다. 색맹이 있는 사람과 없는 사람은 탐색 제약조건이 다르기 때문에 각각 visit 배열을 만들어서 따로 탐색을 수행했습니다. 2번의 DFS 를 수행해도 총 시간 복잡도가 O(2n) 이기 때문에 시간 내에 수행이 가능했습니다. 코드 import sys sys.setrecursionlimit(10**6) N = int(input()) board = [] for _ in range(N): board.append(list(sys.stdin.readline()[:-1])) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def dfs(x, y, visit, d.. 2021. 6. 9.

BOJ 3135 - 라디오 문제 백준 온라인 저지 - 3135번 풀이 과정 라디오의 세 가지 버튼을 이용해서 목표 주파수에 도달하도록 하는 최소 버튼 입력 횟수를 구하는 문제입니다. 주파수의 최소 및 최대 지점이 서로 이어져있지 않기 때문에 단순하게 즐겨찾기 목록들의 주파수들과의 차이값과 A 에서 B 까지의 차이값 중 가장 작은 값을 찾으면 됩니다. 코드 import sys def solution(): min_value = 2e9 for freq in frequency: min_value = min(min_value, abs(freq - B)) return min(min_value + 1, abs(A - B)) if __name__ == '__main__': A, B = list(map(int, sys.stdin.r.. 2021. 6. 9.

BOJ 13410 - 거꾸로 구구단 문제 백준 온라인 저지 - 13410번 풀이 과정 구구단을 수행하되 그 결과를 뒤집었을 때의 최대 값을 구하는 문제입니다. 요구조건이 복잡하지 않고 입력값도 크지 않기 때문에 완전 탐색을 통해 답을 구할 수 있습니다. 코드 import sys def solution(N, K): max_value = 0 for i in range(1, K + 1): num = str(N * i)[::-1] max_value = max(max_value, int(num)) return max_value if __name__ == '__main__': N, K = list(map(int, sys.stdin.readline().split())) answer = solution(N, K) print(answer) 2021. 6. 8.

BOJ 2252 - 줄 세우기 문제 백준 온라인 저지 - 2252번 풀이 과정 위상 정렬 을 활용한 해법으로 해결할 수 있는 문제입니다. 다양한 방법이 있지만 DFS 를 활용해 위상 정렬 을 구현하는 것이 가장 간단해서 이 방법을 사용했습니다. 코드 import sys n, m = list(map(int, sys.stdin.readline().split())) adj = [[] for _ in range(n+1)] for _ in range(m): frm, to = list(map(int, sys.stdin.readline().split())) adj[frm].append(to) def dfs(here, visit, ans): visit[here] = 1 for there in adj[here]: if not visit[there]:.. 2021. 6. 7.

BOJ 2231 - 분해합 문제 백준 온라인 저지 - 2231번 풀이 과정 어떤 분해합 결과가 자연수 N일때 이에 대한 생성자는 N보다 절대 클 수 없다는 점을 이용해 브루트 포스로 해결할 수 있는 문제입니다. 이는 한 자연수와 그 자릿수들의 합으로 N을 만들어야하기 때문입니다. 따라서 가능한 모든 수를 탐색하면서 가장 처음 발견되는 생성자를 반환해주면 됩니다. 코드 import sys N = int(input()) def separate_sum(N): temp = 0 for c in str(N): temp += int(c) return N + temp def solution(): answer = 0 for num in range(N): if N == separate_sum(num): answer = num break return.. 2021. 6. 7.

이전 1 2 3 4 5 6 ··· 18 다음

티스토리툴바