알고리즘 공부20 트리와 그래프 내용 정리 트리와 그래프 그래프란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. 그래프의 종류 무방향 그래프 간선에 방향이 존재하지 않아 양방향으로 이동이 가능하다. (A,B), (B,A)는 동일한 간선이다 방향 그래프 간선에 방향이 존재하는 그래프로 지정된 방향으로만 이동이 가능하다. A->B로 가는 간선은 로 표시하며 와는 다른 간선이다. 가중치 그래프 간선에 비용이나 가중치가 할당된 그래프이다. 완전 그래프 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프 단순 그래프 두 정점 사이의 연결선이 최대 한 개인 그래프 부분 그래프 원래의 그래프에서 일부 정점이나 간선을 제거해 만든 그래프 그래프 구현 방.. 2021. 12. 5. 이분 탐색 정리 이분 탐색 이분 탐색이란? 정렬되어 있는 배열에서 탐색을 할 때, 탐색 범위를 반씩 나누어 탐색하는 방법 장단점 장점 : 하나하나 살펴보는 기존 탐색에 비해 훨씬 빠르다. 단점 : 정렬이 된 상태에서만 사용할 수 있어 사용하기 까다롭다. 이분 탐색 방법 데이터 배열을 정렬해준다. 정렬된 배열에서 왼쪽 끝 인덱스 : left, 오른쪽 끝 인덱스 : right를 이용해 중앙값 : mid를 찾는다. mid와 배열에서 찾고자 하는 값(target)을 비교한다. target이 나올 때까지 아래와 같은 탐색 과정을 반복한다 mid target : right를 mid-1로 이동시켜 왼쪽 구간 탐색 (left.. 2021. 11. 26. [python] 11047번 - 동전 0 문제 파이썬 문제 풀이 동전의 개수를 최소로 하기 위해서는 가장 비싼 동전으로 최대한 바꾸고, 나머지에 대해 그다음 비싼 동전으로 바꿔가면서 나머지가 0이 되도록 하는 방법을 사용한다. import sys input = sys.stdin.readline N, K = list(map(int, input().rstrip().split())) coin = [] for i in range(N) : coin.append(int(input().rstrip())) coin.reverse() count = 0 for i in coin: if K == 0 : break count += (K // i) K %= i print(count) 가장 비싼 동전부터 접근하기 위해 오름차순으로 입력받은 동전을 reverse해줘 내림.. 2021. 11. 24. [python] 13305번 - 주유소 문제 파이썬 풀이 기름 값의 최소 비용을 구하는 문제이다. 최소 비용을 저장해두는 변수를 하나 선언한 뒤 이보다 작은 기름 값이 나오면 최소 비용을 갱신한다. 따라서 최소 비용이 갱신되기 전까지는 이전까지의 최소 비용을 이용해 이동을 하고 새로운 최소 비용이 갱신되면 해당 비용으로 이동을 진행하면 된다. import sys from typing import Mapping input = sys.stdin.readline N = int(input().rstrip()) road_length = list(map(int, input().rstrip().split())) oil_price = list(map(int, input().rstrip().split())) result = 0 min_price = oil_p.. 2021. 11. 24. 이전 1 2 3 4 5 다음
