ehdbs0903 ehdbs0903

깊이 우선 탐색 / DFS (Depth-First Search) 알고리즘이란?그래프에서 모든 노드를 방문하는 알고리즘 중 하나이다.알고리즘의 기본 아이디어는 한 방향으로 갈 수 있는 한 최대한 깊게 그래프를 탐색하는 것이다.   시간복잡도DFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라진다. 1. 인접 리스트 사용 시:각 노드에 대해 모든 인접한 노드를 방문해야 한다.각 노드는 한 번씩 방문하며, 각 노드의 모든 인접한 노드를 확인하는 데 걸리는 시간은 인접한 노드의 개수에 비례한다.따라서 시간 복잡도는 O(V + E) 이다.  (* V = 정점의 수, E = 간선의 수){ 'A': ['B', 'C', 'D'], 'B': ['A'], 'C': ['A', 'D'], 'D': ['A', 'C',..

이진 탐색 / 이분 탐색 (Binary Search) 알고리즘이란?배열에서 특정한 값을 효율적으로 찾기 위한 알고리즘이다.알고리즘의 기본 아이디어는 탐색 범위를 반으로 줄여가면서 원하는 값을 찾는 것이다. 정렬된 상태의 배열에서만 사용할 수 있다.  시간복잡도O(log n)  이분 탐색의 기본 원리초기화:start (시작점)를 배열의 첫 번째 인덱스로, end (끝점)를 배열의 마지막 인덱스로 설정한다.반복 조건:start가 end보다 작거나 같은 동안 반복한다. (start가 end를 초과하면 찾고자 하는 값이 배열에 없다는 것을 의미)중간점 찾기:배열의 중간 지점 mid를 (start + end) / 2로 계산한다.탐색 로직:찾고자 하는 값 targe..

문제https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그www.acmicpc.net  코드import sysinput = sys.stdin.readlinek, n = map(int, input().split())cables = [int(input()) for _ in range(k)]# 이진 탐색을 위한 시작과 끝 지점 설정start, end = 1, max(cables)# 이진 탐색 실행while start..

문제https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워www.acmicpc.net  코드# 사용자로부터 찾고자 하는 '666'이 포함된 순서를 입력받음n = int(input())# 현재까지 발견된 '666'이 포함된 숫자의 개수를 세기 위한 카운터cnt = 0# 처음 검사할 숫자를 666으로 설정i = 666# 무한 반복문을 통해 '666'을 포함하는 숫자를 찾음while True: # 현재 숫자 i를 문자열로 변환하고 '666..

문제https://www.acmicpc.net/problem/1167 1167번: 트리의 지름트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지www.acmicpc.net  코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10001)def dfs(v, w): global distance, farthest_node visited[v] = True if distance   풀이1967번 트리의 지름과 같은 문제로, 입력 받는 부분만 다르다. https://ehdbs0903.tis..

문제https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net  코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10001)def dfs(v, w): global distance, farthest_node visited[v] = True # 현재 노드를 방문한 것으로 표시 # 현재 거리가 더 길 경우 가장 먼 거리와 노드..

문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 코드 import sys # 입력 받기 input = sys.stdin.readline # 백트래킹 함수 정의 def backtracking(x, y, cnt): global alphabet global ans ans = max(ans, cnt) # 현재 경로 길이와 최대 길이 비교 및 업데이트 # 상, 하, 좌, 우 네 방향으로 이동 시도 for i in range(4): nx..

문제https://www.acmicpc.net/problem/9019 9019번: DSLR네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에www.acmicpc.net  코드import sysfrom collections import dequeinput = sys.stdin.readlinedef operation_d(n): return 2 * n % 10000def operation_s(n): return (n - 1) % 10000def operation_l(n): return (n % ..