MintPsycho's Blog

오늘은 Beutiful Soup 과 Selenium 을 통해 뉴스 헤드라인, url > 작성 날짜, 작성 기자, 뉴스 기사 를 크롤링 해 볼 것이다. +) 뉴스 기사는 기자 및 출판사에 저작물 등록이 되어있으므로 상업적 용도로 사용 불가능하다. 또한 크롤링도 해당 사이트의 robots.txt 가 허용되는지 확인 후 크롤링 하도록 하자. 먼저 Selenium 을 추가적으로 사용하는 이유는 뉴스 페이지들의 동작 방식 때문인데, 반응형 웹페이지 같은 동적 페이지에서는 Beutiful soup의 selector 가 제 기능을 못하기 때문이다. 첫번째로, 환경 세팅을 해보자! 사용할 라이브러리, ChromeDriver들을 다운 받아준다. pip install bs4 pip install selenium . (중요..

Hash function 이란? 해시함수(hash function) : 먼저, 해시함수는 해시테이블 에서 index 값으로 사용된다. key-value 쌍을 저장할 때, 고유한 key를 hash code로 변환시킨다. 이 때의 결과값은 데이터 고유의 index로 사용되기때문에 다른 값들과 같아선 안된다. 이를 위한 알고리즘이 바로 해시함수(hash function) 이다. hash function을 무조건 1:1 (key --> hash code) 로 만들게 되면, 결국 array와 다를바 없고 메모리를 너무 차지하게 된다. 따라서, 일반적으로 좋은 hash function은 키 전체를 참조하여 해쉬값을 만들어 낸다. hash function는 다음의 4가지 대표적 특성을 가진다. 압축 및 일관성 -> ..

#TODO : Count sort / Radix sort 버블 정렬(Bubble sort) 이란? 옆에 있는 값과 비교하여 더 큰 값을 반복적으로 뒤로 보내는 정렬 알고리즘. 시간복잡도 O(N^2) Process 한 칸씩 인접한 자료값을 비교하여, 큰 값이 뒤로 가도록 교환한다. 한번 끝까지 자료 탐색이 되면, 현재 iteration 에서 가장 큰 값이 맨뒤로 이동된다. 더이상 정렬할 것이 없을 때 까지 반복한다. 선택 정렬(Selection sort) 이란? 각 배열 위치에 순차적으로 어떤 원소를 넣을지 선택하여 정렬하는 알고리즘. 시간복잡도 O(N^2) Process 주어진 배열 중에서 최솟값을 찾는다. 해당 최솟값을 맨 앞에 위치한 값과 교체한다. 처음 위치를 제외한 나머지 리스트 요소들을 같은 방..

위상 정렬(topological sorting)이란? 비순환 유향 그래프 (싸이클이 없고 방향이 있는 그래프, DAG : directed acyclic graph)의 꼭짓점들(vertex)을 변의 방향(edge)을 거스르지 않도록 나열하는 것을 의미한다. 시간복잡도 O(|V| + |E|) Process 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다. from collections import deque # 노드의 개수 v와 DAG v= 7 adj_list = [[1, 2], [1, 5], [2, 3], [2, 6], [3, 4], [4, 7], [..

list 순서가 있는 수정가능한 객체의 집합. 수정, 삭제, 추가가 가능합니다. list 는 [] 대괄호로 선언되어지며, 내부 원소는 ,로 구분됩니다. import copy ## List init ## list = [] list = list() ## Append ## -- O(1) list.append(3) list.append(5) ## Extend ## -- O(k) list.extend([8,7,4,1,2,6]) ## Delete ## -- O(n) del list[1] list.remove(1) ## Sort ## -- O(nlogn) list.sort() #오름차순 list.sort(reverse=True) #내림차순 res = sorted(list) ## Pop ## list.pop() #가장..

Stack 알고리즘에서 O(1) 시간복잡도로 최솟값을 반환하는 방법 1. Stack 을 push 할 때, [원소 x, 현재까지 스택에 저장된 원소 중 최솟값] 저장하면 된다. class minimum_Stack(): def __init__(self): self.Stack = [] #파이썬은 리스트를 스택으로 사용가능 def push(self, element): # 스택 push if not self.Stack: self.Stack.append([element, element]) else: # 현재 스택의 최솟값(top.second)과 입력값을 비교하여 추가시킴. self.Stack.append([element, min(element, self.Stack[-1][1])]) def pop(self): ret..

Hash : Hash Table에 존재하는 해시함수의 결과물이다. 저장소에서 value와 매칭되어 저장된다. Hash Table : key 와 value 가 한 쌍 으로 존재하는 자료형. (연관배열 구조) 키(key), 해시함수(hash function), 해시(hash), 저장소(buckets), 값(value)로 이루어져 있다. 파이썬의 dictionary. 키 값이 배열의 인덱스로 변환되기 때문에, 검색과 저장의 평균 시간복잡도가 O(1)에 수렴한다.

자료구조 Q. (Python)Dictionary 의 정렬, 정렬이 가능한지 Q. Stack / Queue / Heap / Tree / Graph 개념 Q. Minimum Stack, Queue : O(1) 시간복잡도로 최솟값을 반환하는 함수를 구현하라. Q. 배열 하나로 스택 3개를 어떻게 구현할 지 설명하라. Q. B tree / B+ Tree Q. Binary Search Tree / Binary Heap Q. Binary Tree 의 종류 Q. Spanning Tree / Minimum Spanning Tree Q. Hash 란? Hash Table 이란? Q. Hash 충돌과 이를 회피하기위한 기법 정렬 Q. 위상 정렬이란? Q. 힙 정렬이란? Q. 대부분의 요소가 정렬되어있을때, 사용하기 적합한..

Spanning Tree란, 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프 이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 : DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. (사이클 포함x, 모든 정점 방문o) 탐색 도중에 사용된 간선만 모으면 만들 수 있다. (n-1개의 간선으로 형성) 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Minimum Spanning Tree란, 위에서 정의한 Spanning Tree 중에서 사용된 간선들의 가중치 ..

Pillow(PIL)은 이미지를 불러올때, RGB 순서를 사용하고 OpenCV는 BGR 순서을 사용한다는 점을 알고 있자. 또한 파이썬에서 openCV Mat 은 numpy.ndarray 형식을 띈다. To convert from PIL image to OpenCV use: import cv2 import numpy as np from PIL import Image pil_src =Image.open("test.jpg") # open image using PIL # use numpy to convert the pil_image into a numpy array numpy_src=numpy.array(pil_src) # convert to a openCV2 image, notice the COLOR_RGB..