notty

그래프 (Grpah) 함수 그래프 != 그래프 이론의 그래프 함수 그래프 : x(정의역), y(치역)에 해당하는 값을 좌표 상에 표시하는것 그래프 이론의 그래프 : *꼭짓점(Vertex)과 간선(Edge)으로 구성, G = (V, E) *꼭짓점(Vertex) == 노드(Node) +추가 - 그래프에는 간선이 화살표 => 단방향, 실선인 경우 => 양방향 그래프 - 간선에 가중치를 주는 경우도 있음, 아무것도 쓰여있지 않으면 모두 1이거나 같은 가중치 너비 우선 탐색 (BFS, Breadth-forst Search) : 연결되어있는(인접한) 노드를 우선적으로 탐색하는 것이다. 자료구조 *큐(queue) 를 사용하여 구현할 수 있으며 과정은 현재 노드와 연결된 노드를 큐에 append 후 큐의 가장 처음 노..

그래프 (Grpah) 함수 그래프 != 그래프 이론의 그래프 함수 그래프 : x(정의역), y(치역)에 해당하는 값을 좌표 상에 표시하는것 그래프 이론의 그래프 : *꼭짓점(Vertex)과 간선(Edge)으로 구성, G = (V, E) *꼭짓점(Vertex) == 노드(Node) +추가 - 그래프에는 간선이 화살표 => 단방향, 실선인 경우 => 양방향 그래프 - 간선에 가중치를 주는 경우도 있음, 아무것도 쓰여있지 않으면 모두 1이거나 같은 가중치 깊이 우선 탐색 (DFS, Depth-first Search) : 말 그대로 상위 레벨의 노드 --> 하위 레벨의 노드를 우선적으로 탐색하는 것이다. 하지만 이미 방문했던 노드는 다시 방문하지 못하며 더이상 탐색할 노드가 없을 시 이전 노드로 옮겨서 방문하지..

스택(Stack) stack : 쌓다 Last In First Out (LIFO) - 후입 선출 (== First In Last Out, 선입 후출) push : 가장 마지막에 쌓는다 pop : 가장 마지막에 들어간 것을 뺀다 python 구현 - push : append()를 사용하여 수행 (시간복잡도 == O(1)) - pop : pop()을 사용하여 수행 (시간복잡도 == O(1)) arr = [1,2,3,4] arr.append(5) #arr에 5를 push print(arr) #output : [1,2,3,4,5] arr.pop() #arr의 마지막 원소를 pop print(arr) #output : [1,2,3,4] 큐 (Queue) queue : 줄 First In First Out (FIF..

그리디 알고리즘 (Greedy Algorithm) Greedy : 탐욕스러운 각 단계에서 최적의 선택을 하는 방식(=Greedy) 으로 최종 답에 도달하는 알고리즘을 말한다. 단, 항상 최적의 해를 구할 수 있는 것이 아니고 특정한 경우에만 그리디 알고리즘으로 최적의 해에 도달할 수 있다. **특정한 경우 == 최적의 해를 보장할 수 있는 경우 예시) 백준 11399 ATM (Python) 줄 선 사람들이 돈을 인출하는데 걸리는 시간의 합의 최솟값을 구해야한다. 각 사람이 소요되는 시간은 이전 사람들이 걸리는 시간 + 내가 걸리는 시간 이다. 각 단계의에서 최적의 선택을 하여 최종 해에 도달 할 수 있다는 것을 보장할 수 있는가? 이 경우 입력받은 걸리는 시간들을 오름차순 정렬하여 각 단계에서 (앞사람들..

1. Lower bound - 배열에 해당 값이 두개 이상 존재하는 경우 가장 앞선 인덱스를 반환하도록 한다. def binary_search_lo(given_data,target): start = 0 end = len(given_data)-1 while start

최대공약수 -정수들의 공통된 약수중 가장 큰 약수 방법1: 전체 순회 1) 정수들 중 가장 작은 정수를 찾눈다 2) 정수의 값을 하나씩 줄여 나가면서(i) 두 정수를 나눈다 3) 둘 다 0으로 나누어 떨어질 때의 i 가 최대공약수가 된다 N, M = map(int, input().split()) lst = [] minimum = min(N,M) for i in range(1,minimum+1): if (N % i == 0) and (M % i == 0): lst.append(i) else: continue print(lst[-1]) 방법 2 : 유클리드 알고리즘 - a>b, a와 b의 최대공약수는 b와 a%b와 같다 (gcd(a, b) == gcd(b, a%b)) 1) 정수 두개 중 작은값을 찾는다 2)..

배열을 정렬 중앙값을 찾는다 중앙값을 기준으로 찾을 값이 큰 값 -> 반의 오른쪽으로 중앙값을 기준으로 찾을 값이 작은 값 -> 반의 왼쪽으로 같다면 -> 찾은 값을 반환 -> break 오른쪽 왼쪽을 구분하기 위하여 start, end 값을 지정 start = 0 end = len(배열) 중앙값 (start + ) // 2 list_a = [1,2,3,4,5,6,7] def binary_search(target, data): start = 0 end = len(data) - 1 while start target: end = mid-1 print(data[start:end]) else: start = mid+1 print(data[start:end]) print('없다') binary_search(3, ..