blog...

7.1 Brackets 괄호 def solution(S): reverse_c = {')': '(', ']':'[', '}':'{'} stacks = [] for s in S: s_ = reverse_c.get(s, -1) if s_ == -1: # open stacks.append(s) else: # close if len(stacks) == 0 or s_ != stacks[-1]: return 0 else: stacks.pop(len(stacks)-1) return int(len(stacks) == 0) 7.2 Fish You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracio..

6.1 Distinct Write a function that, given an array A consisting of N integers, returns the number of distinct values in array A. N개의 정수로 구성된 배열 A가 주어지면 배열 A의 고유한 값의 수를 반환하는 함수를 작성합니다. def solution(A): if len(A) == 0: return 0 A.sort() cnt = 1 for i in range(1, len(A)): if A[i] != A[i-1]: cnt+=1 return cnt 6.2 MaxProductOfThree A non-empty array A consisting of N integers is given. The product of..

5.1 PassingCars A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: - 0 represents a car traveling east, - 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is ..

4.1 FrogRiverOne A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river. You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, meas..

3.1 FrogJmp A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target. Write a function that, given three integers X, Y and D, returns the minimal number of jum..

2.1 CyclicRotation An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times. Write a function that, given an array A consisting of N integers and an integer K, return..

1.1 BinaryGap A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. Write a function that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap. 양의 정수 N 내의 이진 갭은 N의 이진 표현에서 양쪽 끝에 하나로 둘러싸인 연속적인 0의 최대 시퀀스입니다. ..

Dijkstra 다익스트라 출발점으로부터 각 정점까지의 최단거리 및 경로 계산 Prim-MST 알고리즘과 유사. 차이점은 Dijkstra-최단경로는 출발점이 주어진다는 것, D의 원소에 출발점부터의 경로의 길이가 저장된다는 것! Prim→어느 정점에서 시작해도 같은 그래프를 도출 / D의 원소에 자신과 연결된 간선의 가중치를 저장 Dijkstra→특정 정점으로부터의 최단 경로를 구하기 때문에 시작 정점이 바뀔 때마다 최단 경로 그래프가 다르게 도출 / D의 원소에 출발점부터의 경로의 길이를 저장 for k in range(N): m=-1 # m:min_vertex min_value=sys.maxsize # 가장 가까운 정점찾기 for j in range(N): if not visited[j] and D[j]

최소신장트리 MST 하나의 연결성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치 합이 최소인 신장트리 ※ 신장트리란(Spanning Tree)? → 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분그래프 MST 알고리즘에는 Kruskal, Prim, Sollin이 있음→Greedy Kruskal 알고리즘 가장 작은 가중치 순서대로 선택 (가중치1→2→3 이런식으로) 사이클 만들면 버리기 n-1개 간선 선택되면 종료 주요코드(일부) weights=[(0,1,9),(0,2,10)...(5,6,6)] # u,v,wt 순 #kruskal은 가중치를 기준으로 정렬해야함! weights.sort(key=lambda t:t[2]) # find함수 : u가..

그래프 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 용어 정점(vertex)과 간선(edge) 방향그래프: a→b 무방향그래프: a↔b (a, b) 차수(Degree): 정점에 인접한 정점의 수 (진입차수, 진출차수) 경로: 시작정점부터 도착점까지의 정점들을 나열 단순경로: 경로상의 정점들이 모두다름 일반적인경로: 중복하여 방문하는 경우도 포함 싸이클: 시작점과 도착점이 같은 단순경로 (트리는 사이클 안됨) 연결성분: 그래프에서 정점들이 서로 연결되어 있는 부분 가중치 그래프: 가중치 부여된 그래프, 음수가중치도 있음 부분그래프 트리: 싸이클이 없는 그래프 신장트리(spanning tree): 하나의 연결성분, 모든 정점들을 싸이클 없이 연결하는 부분그래프 네트워크: 간선에 비용or가중치가 ..