문제 공항에는 G개의 탑승구가 있다. (1~G), 공항에는 P개의 비행기가 도착할 예정이며 i번째 비행기는 1번부터 g번째(1이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있다. 또한, P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지한다. 최대한 많은 비행기를 공항에 도킹하고자 할 때, 최대 몇대의 비행기를 도킹할 수 있는지 출력하는 프로그램을 작성하시오.입력첫째 줄에는 G, 둘째 줄에는 P, 다음 P개의 줄에는 g가 주어짐출력도킹할 수 있는 비행기의 최대 개수를 출력parent 리스트의 원소를 기둥으로 생각하면, 두 원소가 union된 경우 그 사이의 gate에 비행기가 들어온 것으로 간주할 수 있다.가장 우..

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례로 수행해야 할 때 사용할 수 있는 알고리즘으로, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.위상 정렬 알고리즘에서는 진입 차수라는 개념이 필요한데, 진입 차수란 특정한 노드로 들어오는 간선의 개수를 의미한다.위상 정렬 알고리즘 1. 진입 차수가 0인 노드를 큐에 넣는다.2. 큐가 빌 때까지 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입 차수가 0이된 노드를 큐에 넣는다.# 위상 정렬 알고리즘import sysclass queue: def __init__(self): self.queue = [] self.size = 0 def enqueue(sel..

서로소 집합 자료구조는 union과 find 2개의 연산을 활용하므로 union-find 자료구조라고 불리기도 한다.union 연산은 2개의 집합을 하나의 집합으로 합치는 연산이다.find 연산은 특정 원소가 속한 집단이 어떤 집합인지 알려주는 연산이다.서로소 집합 자료구조는 원소들 사이의 관계를 나타내기 위해 parent 리스트를 선언하여 이용하는데, 초기 parent 값은 자기 자신으로 설정한다. parent = [x for x in range(v+1)]기본적으로 두 노드를 하나의 집합으로 합칠 때는 큰 노드가 작은 노드를 가리키도록 한다. (값이 더 작은 원소를 가지는 노드가 루트 노드가 되도록 함) union(a, b): # a의 루트 노드를 x, b의 루트 노드를 y라고 가정(x는 a이며, y는..

DFS : 재귀함수(스택)로 구현재귀 함수 실행 시 방문처리 & 값 이용연결된 노드 재귀함수 호출 # DFS# 동작 원리 : 스택# 구현 방법 : 재귀 함수 이용# 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간 소모됨# visited 리스트가 dfs 함수 안에 있으면, dfs 함수가 재귀적으로 호출되면서 계속 리스트가 초기화되기 때문에 안됨# vertex : 정점, edge : 간선graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]visited = [0 for _ in range(len(graph))]def dfs(graph, visited, v): if visited[v] == ..

유클리드 호제법 (Euclidean algorithm)2개의 자연수의 최대 공약수를 구하는 알고리즘으로 명시적으로 기술된 가장 오래된 알고리즘이다.a > b 이고 a % b = r 이라 할 때, a와 b의 최대 공약수는 b 와 r의 최대 공약수와 같고 이와 같은 과정을 하나의 수가 0이 될 때까지 반복하면 나머지 한 수가 최대 공약수가 된다는 법칙. def gcd(a,b): while a != 0 and b != 0: if a > b: a %= b elif a 재귀를 활용하여 gcd 함수 구현하기def gcd(a,b): if a == 0 or b == 0: return a+b elif a > b: return gcd(a-b,b) else:..

입력받은 정수 n이 소수(Prime Number)인지 아닌지를 판별하는 방법 방법 1for문을 돌리면서 1부터 n까지를 k에 넣고 n이 k로 나누어 떨어지는 경우에 cnt를 1씩 증가시킨다.for문이 종료되었을 때 cnt 값이 2일 경우 소수이고 아닐 경우 소수가 아님 def prime(number): cnt = 0 for n in range(1,number+1): if number % n == 0: cnt += 1 if cnt == 2: return 1 else: return 0 def is_prime(n): for k in range(2,n): # 2부터 n-1까지 나누어지지 않는 것만 확인하므로 더 간결한 코드임 if ..