오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Max Flow Ford-Fulkerson 알고리즘 Min cut Maxflow-mincut - baseball elimination ▶Max Flow Edge-weighted Digraph 간선의 weight : (거리 아닌) flow 흐를 수 있는 최대량 capacity를 나타낸다. (>= 0) flow의 출발지 s, 도착지 t Max Flow는 출발지에서 도착지로 흐를 수 있는 flow의 최대량 꼭 지켜야 하는 물리적 법칙 1. flow는 간선 방향 따라서 흐른다. 2. 0 > V라면 -> EU P의 mi..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.09 - [컴퓨터공학/알고리즘2] - [알고리즘2] Shortest Paths on Weighted Digraphs [알고리즘2] Shortest Paths on Weighted Digraphs 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶Seam Carving 이미지의 크기 조절 시 중요한 부분 자동 인식해 최대한 보존하며 ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents 최단경로 Bellman-Ford algorithm Dijkstra algorithm Acyclic Shortest Path Seam Carving ▶Shortest Path(Edge-Weighted Digraph) 간선에 weight가 있는 directed graph G s에서 t까지 연결하는 경로 중 (연결된 간선의 집합) 간선의 weight 합이 최소인 경로 weight 합이 0보다 작은 사이클이 있는 그래프는 최단 경로로 존재하지 않는다. 사이클이 있어도 최단 경로는 존재한다. weight가 0보다 작은 ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.08 - [컴퓨터공학/알고리즘2] - [알고리즘2] Minimum Spanning Tree(MST) [알고리즘2] Minimum Spanning Tree(MST) 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶구현 API 정리 # 이미 구현된 기능 class Edge: # Weight 있는 방향성 없는 간선 나타내는 클래스 (예..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents MST Greedy algorithm Kruskal's algorithm Prim's algorithm lazy version Prim's algorithm eager version ▶MST Minimum Spanning Tree : Wegiht 합이 최소인 spanning tree 1. Tree (connected and acyclic subgraph of G) 2. Spanning tree (모든 정점 포함) 3. 간선의 weight 합이 최소 Brute-force 알고리즘 : 모든 가능한 spannign ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents WordNet Outcase SCA & SAP WordNet과 outcaset 탐지 구현 ▶WordNet 정점(synset) : 유사어(synonym)의 집합(set) v -> w 간선 : v is a w 관계 (hyponym -> hypernym) 'apple' is an edible fruit 'banana' is an edible fruit WordNet의 특성 Cycle이 없다. (DAG, Directed Acyclic Graph) Root는 하나이다. (entity) 부모가 둘 이상인 경우도 있고, 자..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.11.22 - [컴퓨터공학/알고리즘2] - [알고리즘2] Undirected and Directed Graphs [알고리즘2] Undirected and Directed Graphs 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶구현된 API 정리 class Digraph: # Digraph 객체를 저장하는 클래스 def revers..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Undirected Graph Directed Graph Web Crawling Topological Sort Strongly-Connected Component ▶Undirected Graph 간선에 방향성이 없는 그래프이다. 특정 조건을 만족하는 (모든 간선이 양방향) Digraph의 집합이다. 따라서 Digraph의 부분 집합이다. Undirected Graph 알고리즘 조건에 맞는 일부 경우에만 동작하는 알고리즘이므로 상대적으로 간단하다. ex. connected components 구하는데 DFS를 그..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. import copy import random from queue import PriorityQueue class Board: def __init__(self, tiles): self.n = len(tiles) self.tiles = copy.deepcopy(tiles) self.twinBoard = None # Compute Hamming distance self.hammingDistance = 0 goal = 0 for rowId, row in enumerate(tiles): for colId, t in enumerate(r..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Binary Heap을 사용한 PQ의 구현 Priority Queue 사용 애플리케이션 공통적인 특성 Slider Puzzle and A* Search with PQ ▶Priority Queue insert() 1. complete binary tree 형태를 유지한다. 2. heap order를 유지한다. 3. ~logN 시간에 새 원소를 추가한다. insert(k)하는 새 값을 k라고 할 때, k를 tree 가장 마지막에(배열 끝에) 추가한다. k를 부모 노드와 비교해 heap-order(부모 >= 자식) ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Collinear Points 4개 이상 점 연결하는 maximal한 직선을 모두 찾는 코드이다. N개 점의 (x, y) 좌표가 입력으로 주어졌을 때, 4개 이상 점을 연결하는 maximal한 직선을 모두 찾으면 된다. ▶Collinear Points 탐지방법 하나하나 비교하면서 하는 Brute Force방식을 사용할 수 있다. 하지만 시간 복잡도 측면에서 좋지 못한 코드가 된다. 정렬을 활용한 더 효율적인 방법을 사용하면 된다. 각 점 p에 대해, p가 다른 모든 점과 이루는 기울기를 계산해, 기울기를 key로 정렬한다. 정..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Bottom-up Merge Sort Sorting Complexity Stability of Sorting Quick Select Duplicate Keys and 3-way Partitioning ▶Merge Sort 인접한 두 조각끼리 Merge(정렬된 순서로 병합)을 반복한다. 총 N개 원소를 병합한다면, 이들을 순서에 맞게 차례로 결과 배열에 옮겨 담으므로 ~N회 작업이 필요하다. 이러한 작업을 ~log(N)회 반복해야 한다. 입력 데이터 크기가 N이라면 결과를 옮겨 담을 ~N의 추가 공간도 필요하다...

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶프로그램 입출력 조건 xy 좌표계에 속한 점의 list(points)를 입력으로 받는 함수 정의 points는 tuple (x, y)의 리스트임 (예: [(3,2), (4,-1), (0,0), (-2,2)]) points에 속한 점은 모두 좌표가 서로 다름 def grahamScan(points): 위 함수는 Graham’s Scan을 사용해 convex hull에 속한 점의 좌표를 구한 후 입력과 같은 형식으로 반환 최초로 convex hull에 포함하는 점 p는 y 값이 가장 작은 점 중 x 값이 가장 큰 점 이후에 con..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Insertion Sort h-Sort Shell Sort Shuffle Sort Convex Hull (Tight boundarry 찾기 위해 정렬 방법 적용) ▶Insertion Sort 이미 정렬된 a[0] ~ a[i-1]에 a[i]를 적절한 위치 (정렬되었을 때의 위치) 찾아 추가한다. 그 결과 a[0] ~ a[i]까지 정렬된 상태가 된다. 입력 데이터의 상태 대소 비교 횟수 swap 횟수 (best case) 이미 정렬된 상태 N - 1 0 (worst case) 반대 방향으로 정렬된 상태 ~N^2 /..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Percolate N × N 개의 객체가 격자를 이룬다 (그림 참조) 각 객체는 두 상태(열림, 닫힘) 중 하나를 가질 수 있으며 가장 윗줄이 가장 아랫줄에 연결되었다면 (열린 격자 통해 이동 가능) 이 격자는 percolate 한다고 한다. ▶simulation 방법 개요 N × N 개의 객체를 닫힌 상태로 초기화 닫힌 객체 중 하나를 (임의로 선정해) 열린 상태로 바꾸고 percolate 하는지 확인 위 -> 아래로 percolate 할 때까지 반복 percolate 할 때 열려 있는 객체의 비율(=열린 객체 수 / (N ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Union Find Quick Find Quick Union ▶Union Find N개 객체가 주어진다. 0 ~ (N-1)까지 정점(vertex)으로 표현된다. 간선(edge)이 없는 상태에서 시작한다. 2개의 명령 수행이 필요하다. Union(a, b) : 점 a와 b를 간선으로 연결 Connected(a, b) : a와 b를 연결하는 경로 존재하는지 True/False로 응답한다. (Find라고도 한다.) 값이 Union 됨에 따라서 Connected(Find) 값이 달라진다. 한마디로 연결 상태가 동적으로..