codinging

NumPy(Numerical Python) NumPy는 행렬이나 일반적으로 대규모 다차원 배열을 쉽게 처리할 수 있도록 지원하는 파이썬의 라이브러리이다. NumPy Tutorials https://numpy.org/devdocs/user/quickstart.html 예시 배열 출력 차원별 출력 >>> a = np.arange(6) # 1d array >>> print(a) [0 1 2 3 4 5] >>> b = np.arange(12).reshape(4, 3) # 2d array >>> print(b) [[ 0 1 2] [ 3 4 5] [ 6 7 8] [ 9 10 11]] >>> c = np.arange(24).reshape(2, 3, 4) # 3d array >>> print(c) [[[ 0 1 2 3..

NumPy(Numerical Python) NumPy는 행렬이나 일반적으로 대규모 다차원 배열을 쉽게 처리할 수 있도록 지원하는 파이썬의 라이브러리이다. NumPy Tutorials https://numpy.org/devdocs/user/quickstart.html NumPy기본 ndarray.ndim - 배열의 축(차원) 수 ndarray.shape - 배열의 n행과 m열을 (n, m) 으로 표현 ndarray.size - 배열의 총 요소 수 ndarray.dtype - 배열의 요소 유형을 설명하는 객체 ndarray.itemsize - 배열의 각 요소의 크기 >>> import numpy as np >>> a = np.arange(15).reshape(3, 5) >>> a array([[ 0, 1, ..

최단 경로 알고리즘 최단 경로 알고리즘이란 가중치가 주어진 그래프에서 두 노드의 경로중 간선의 가중치의 합이 최소가 되는 경로를 찾는 알고리즘이다. 다익스트라 : 특정 한 노드에서 모든 노드 까지의 최단거리(음수 x)벨만-포드 : 다익스트라의 음의 가중치가 사이클을 형성해 무한히 작아지는걸 보안하기 위해 나옴플로이드-위셜 : 모든 노드간 최단거리 🦝 다익스트라 특정 한 노드에서 모든 노드 까지의 최단 거리를 구하는 알고리즘이다. (간선의 가중치가 음수이면 안된다는 조건이 있다.) 방문 하지 않은 경로중 가중치가 최소인 노드를 선택해 거리를 확정 해 나가는 형식이다. 0. Dist 의 값을 INF로 초기화 시켜준다. 1. 방문한 노드와 연결 된 노드의 Dist를 비교해 업데이트를 시켜주고, 현재 방문 노드..

MST Spanning Tree 란 모든 노드를 포함하는 부분 그래프이다. Minimum이 추가된 Minimum Spanning Tree 는 간선의 합이 가장 작고 모든 노드를 지나는 부분 그래프를 말한다. Minimum Spanning Tree를 구하는 알고리즘은 Kruskal , Prim 알고리즘이 있다. 백준 1197 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net Kruskal Algorit..

Union Find 유니온 파인드란 그래프의 관점에서 두 노드가 같은 그래프에 속하는지 빠르게 판별하는 알고리즘이다. 집합에서의 관점으로는 두 요소가 같은 집합에 속하는지 판별한다. union find 알고리즘은 두 노드가 속하는 집합을 합치는 union 과 두 노드가 같은 집합인지 확인하는 find 연산이 있다. 설명 6개의 노드로 union find 의 예시를 들어보겠다. 부모를 알 수 있는 배열을 만드는데, 각 노드는 아직 아무 연결도 되어있지 않으므로 아직 자기자신이 부모이다. 1,2를 한 집합으로 4,5,6을 한 집합으로 묶고자 한다. 먼저 위의 예시는 잘못된 예시이다. 만약, 이런식으로 부모 노드를 연결한다면 문제가 생길 것 이다. 모든 노드를 연결 한다고 가정했을때 위와 같은 방식으로 부모노..

강한 연결 요소 그래프에서 강하게 연결 되어있는 집합이다. 같은 SCC집합에 속해있는 정점끼리는 도달가능하다는 특징을 가지고 있다. 집합내 모든 두 점이 서로 도달 가능할때 강하게 연결 되어있다고 한다. 위의 그림과 같은 그래프로 설명을 할 것 이다. 위의 그래프에서의 SCC는 다음 그림과 같은 집합으로 나타낼 수 있다. 같은 집합내의 원소들은 서로 도달가능하다. 예를들어 2와 4 를 보면 2는 4로 도달이 가능하지만 4는 2로 도달할 수 없기 때문에 2, 4는 같은 SCC가 아니다. 반면에, {1,2,3} 을 보면 1에서 2, 1에서 3 / 2에서 1 ,2에서 3/ 3에서 1, 3에서 2 어떤 두 정점을 잡아도 해당 노드로 이동이 가능하기 때문에 같은 SCC에 속한다고 보면 된다. 이제 SCC의 원소를..

우선순위 큐 우선순위 속성을 가지는 큐 우선순위 큐는 배열, 연결 리스트, 힙으로 구현 할 수 있다. 힙 구현 방식이 시간 복잡도가 가장 낮기 때문에 힙으로 구현한다.(O(logN)) 힙 힙 순서 속성을 가지는 완전 이진 트리(자유 저장소 힙이 아님) 힙의 삽입 연산 🐬 1 : 힙의 최고 깊이 가장 우측에 새 노드 추가.(완전 이진 트리 유지) 🐬 2 : 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 맞는 위치니 연산 종료. 🐬 3 : 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 교환. 교환 후 2번 - 3번 반복 예시 다음 힙에 값이 7인 노드를 삽입하는 예시다. 값이 7인 노드를 힙의 마지막에 추가하고 부모 노드와 비교한다. 7은 31보다 작으므로 이..

LCS 알고리즘 두 수열 사이에 공통적으로 존재하는 가장 긴 부분 수열을 말한다. 예를 들면 ABCDEF 와 EBDEAF 의 가장 긴 부분수열은 BDEF 이다. 설명 문자열 X[i] = {x1, x2, x3 . . .xi} , Y[j] = {y1, y2, y3 . . .yj} 인 두 문자열이 있다, 그리고 이 두 문자열의 LCS의 길이를 구하는 함수를 LCS_LEN(X[i], Y[j]) 라고 하자 🐧첫번째 경우( i == 0 ) 만약 i == 0 이라면 문자열의 길이가 0이라는 뜻이니 LCS_LEN(X[i], Y[j]) == 0 이다. 🐧두번째 경우( xi == yj ) X[i] 문자열의 i번째 문자 xi 와 Y[i] 문자열의 j번째 문자 yj 가 같다( xi == yj ) 라면 다음과 같은 식이 성립한..