study

그래프 탐색 - DFS / BFS 1. 깊이 우선 탐색 (DFS) 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색하는 방법. 최대 깊이까지 도달했다면 방문한 정점들을 역순으로 재방문하며 탐색 가능한 정점이 있는지 확인한다. 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행한다. 스택 또는 재귀로 구현할 수 있다. 아래 그림의 그래프를 DFS로 탐색하는 과정은 다음과 같다. 1번 노드에서 탐색을 시작한다. 스택에 1번 노드를 삽입한다. ([1]) 1번에서 탐색 가능한 노드는 2번과 4번이 있다. 2번을 스택에 삽입한다. ([1, 2]) 2번에서 탐색 가능한 노드는 3번과 4번이 있다. 3번을 스택에 삽입한다.([1, 2, 3]) 3번에서 탐색 가능한 노드는 2번과 4번이 ..

1. 그래프(Graph) 1) 그래프의 구성 요소 정점(Node / Vertex) 특별한 하나의 객체 간선(Edge) 정점을 연결하는 선. 두 노드 간의 관계를 나타냄. 방향이나 비중을 나타낼수있음. 그래프(Graph) 정점과 간선의 집합으로 이루어진 구조. 2) 그래프 관련 용어 인접(adjacent) : 두 정점이 간선으로 연결되어 있는 경우 차수(degree) : 정점에 연결된 간선의 수 진입 차수(in-degree) : 해당 정점으로 향하는 간선의 수 진출 차수(out-degree) : 해당 정점에서 나가는 간선의 수 경로(path) : 한 정점에서 다른 정점으로 이어지는 정점들의 리스트 경로 길이(path length) : 경로를 구성하는 간선의 수 단순 경로(simple path) : 모두 다..

# 이진탐색 # 가장 인접한 두 공유기 사이의 거리를 최대로 하는 # 공유기의 거리를 이진탐색으로 찾는다. # 설정한 공유기의 거리를 통해 공유기를 몇대 설치할 수 있는지 확인 import sys n, c = map(int, input().split()) x = sorted(int(sys.stdin.readline()) for _ in range(n)) # 이진탐색을 위해 오름차순 정렬 start = 1 # 시작지점 end = x[-1] - x[0] # 최대 거리 result = 0 # 결과값 while start = current + mid: # 다음 좌표가 현재 좌표 + 중간값과 같거나 크다면 = 공유기 거리의 최대값 + 위치보다 크다면 count += 1 # 공유기 설치 current = x[i] ..

# 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액 찾기 # x + y가 0에 가장 가까운 수가 되는 두개의 수 찾기. 오름차순 정렬. # 0에 가장 가까운 수를 만들어내는 방법? => 절대값이 비슷한 음수와 양수를 합치기 # 투포인터 문제. 배열을 정렬한 후 양쪽 끝에서부터 비교 n = int(input()) liquid = list(map(int, input().split())) # 용액들의 리스트 liquid.sort() # 오름차순 정렬 left = 0 # 포인터. 왼쪽 끝에 위치 right = n-1 # 포인터. 오른쪽 끝에 위치. result = abs(liquid[left] + liquid[right]) # 초기값은 첫값과 마지막 값의 합의 절댓값 final ..

# 이분탐색 # 심사대 n개 사람수 m명 시간 t # 탐색 범위는 심사에 걸리는 시간. t의 최소값 / 최대값 * 인원수 import sys n, m = map(int, input().split()) t = [int(sys.stdin.readline()) for _ in range(n)] start, end = min(t), max(t) * m result = end # 탐색을 진행하며 더 작은 값을 찾아가기때문에 현재 최대값으로 초기화해줌 while start = m: # 만약 심사할수있는 사람이 m보다 크다면 = 탐색할 범위의 값을 줄여야함 end = mid - 1 result = mid # 중간값을 결과에 갱신 else: # 심사할 수 있는 사람이 m보다 작다면 = 탐색 범위의 값을 늘려야함 sta..

# 2017481620 # 정렬 사용. # 좌표 압축 -> 주어진 x들의 값을 오름차순으로 정렬했을때의 인덱스값. # 같은 숫자가 있을 수 있으니 셋으로 정리 n = int(input()) numbers = list(map(int, input().split())) sort_nums = sorted(set(numbers)) dict = {sort_nums[i] : i for i in range(len(sort_nums))} # key : numbers의 각 값, value : 오름차순 정렬시 각 값의 인덱스 for j in range(len(numbers)): numbers[j] = dict[numbers[j]] print(' '.join(map(str, numbers))) https://www.acmic..

# 이분탐색. m만큼 자르는데 필요한 높이를 이분탐색으로 찾기 # 필요한 높이의 최소값은 1 최대값은 제일 높은 나무의 높이 # 나무의 높이가 중간값보다 크다면 값을 빼주고 총합을 구함. # 총합이 m과 같다면 중간값이 결과값. n, m = map(int, input().split()) trees = sorted(list(map(int, input().split()))) start, end = 1, max(trees) # 나무 높이를 이진 탐색하기 위해 정한 범위 while start = mid: # 나무 높이가 벌목 높이보다 높다면 temp += i - mid # 잘라낸 길이만큼 temp에 더함 if temp >= m: #잘라낸 길이가 m보다 크다 = 벌목 높이를 높여야함 start = mid + 1 ..

# 총 시간의 최소값을 구해야함 # 2번이 필요한 시간 = 1번 시간 + 2번 시간. 3번은 1번 + 2번 + 3번 ... # 오름차순으로 정렬 후 0번부터 현재값까지의 합을 결과값에 더해줌 n = int(input()) times = sorted(list(map(int, input().split()))) result = 0 for i in range(len(times)): result += sum(times[0:i+1]) print(result) 정렬을 활용하는 간단한 문제! 더해줘야하는 값은 sum과 슬라이싱을 사용해주었다. https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 ..

1. 이분 탐색(Binary Search) 정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 방법. 탐색 범위를 절반씩 줄여나가면서 탐색 범위가 1이 될때까지 진행한다. 시간 복잡도는 O(log n). 이진 탐색이라고도 한다. 이분 탐색 예시 코드 # 백준 2110번 : 공유기 설치 n, m = map(int, input().split()) trees = sorted(list(map(int, input().split()))) # 오름차순으로 정렬(필수) start, end = 1, max(trees) # 시작 위치와 끝 위치 지정 while start = mid: temp += i - mid if temp >= m: start = mid + 1 else: end = mid - 1 print(end) 예를 들..

from heapq import * n = int(input()) heap = [int(input()) for _ in range(n)] # 요소들 힙에 추가 heapify(heap) result = 0 while len(heap) > 1: # 힙에 더이상 더할 요소가 남지 않을때까지 x = heappop(heap) # 첫번째 작은 값 y = heappop(heap) # 두번째 작은 값 heappush(heap, x + y) # x + y 의 합을 다시 힙에 추가 result += x + y print(result) 문제 그대로 코드를 썼다. 최소값 순으로 두 값을 더하고 그 합을 남은 값과 다시 더하는 방식으로 구현했다. 힙에 더이상 더할 값이 없을때까지 반복문을 돌리게 하고 첫번째로 작은 값과 두번째..