이분 탐색 문제https://www.acmicpc.net/problem/2110문제 이해1. 요점문제의 요점은 다음과 같다.각 공유기 사이의 거리 및 간격이 최대가 되게끔 공유기 C개를 배치하라.즉, 공유기 C개를 각각 최대한 멀리 떨어뜨려라.이때 공유기 사이의 거리 및 간격이 각각 달라도 된다. 최대가 되게 공유기를 배치 후 이 중에서 최소값을 출력한다.결론적으로는 공유기들이 각각 최대한 멀리 떨어져 있어야 한다. 2. 예시9 31 2 3 4 5 6 7 8 100정답 : 7 (1 8 100)9 410 20 30 40 48 60 70 80 81정답 : 20 (10 30 60 80)9 41 2 3 4 5 6 7 15 100정답 : 6 (1 7 15 100)10 41 2 3 4 5 6 7 8 9 10정답 :..

이분 탐색 문제https://www.acmicpc.net/problem/1654💡 풀이코드 (성공)import sys K, N = map(int, sys.stdin.readline().split())lans = []for _ in range(K): lan = int(sys.stdin.readline()) lans.append(lan)def binary_search(K, N, lans): start = 1 end = max(lans) answer = 0 while start = N: start = mid + 1 answer = mid else: end = mid - 1 return answer..

누적합, 소수 판정, 에라토스테네스의 체 문제https://www.acmicpc.net/problem/17425 문제 설명1 = 1 (1)2 = 1, 2 (3)3 = 1, 3 (4)4 = 1, 2, 4 (7)5 = 1, 5 (6)6 = 1, 2, 3, 6 (12)7 = 1, 7 (8)8 = 1, 2, 4, 8 (15)9 = 1, 3, 9 (13)10 = 1, 2, 5, 10 (18)11 = 1, 11 (12)12 = 1, 2, 3, 4, 6, 12 (28)1 2 3 4 5 6 7 8 9 10 11 12 13 141 4 8 15 21 33 41 56 69 87 99 127 입력첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며..

이진탐색이란?이진탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾거나, 그 값이 위치할 수 있는 인덱스를 찾는 데 매우 효율적인 알고리즘이다.즉, 최적의 값이나 인덱스의 위치를 찾는데 유용하다.이진탐색의 종류 1. 값이 삽입될 인덱스를 이진탐색하는 경우목적: 특정 값이 위치할 수 있는 배열의 인덱스를 찾는 것.방법: 배열에서 중간 인덱스를 선택하고, 찾고자 하는 값과 중간 인덱스의 값을 비교한다. 찾고자 하는 값이 중간 인덱스 값보다 작다면, 배열의 왼쪽 절반을 검색하고, 크다면 오른쪽 절반을 검색한다. 이 과정을 반복하여 값을 찾거나, 값을 찾지 못하는 경우 해당 값이 위치할 수 있는 인덱스를 반환한다.def binary_search_index(arr, target): left, r..

위상정렬 문제https://www.acmicpc.net/problem/2252💡 풀이코드 (성공)import sys from collections import deque V, E = map(int, sys.stdin.readline().split())graph = [[] for _ in range(V + 1)]degree = [0] * (V + 1)for i in range(E): v1, v2 = map(int, sys.stdin.readline().split()) graph[v1].append(v2) degree[v2] += 1def topological_sort(V, E, graph, degree): queue = deque() result = [] for i in ..

위상 정렬 (Topological Sorting)이란?정렬 알고리즘의 일종으로, 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.사이클이 없는 방향 그래프(DAG)의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다. 예시그림과 같이 총 3개의 과목이 있다고 가정하자.세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야한다.만약 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다. 진입차수와 진출차수위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 진입차수 (Indegree) : 특정한..