목록파이썬 (40)
DevKim
[1] 합병 정렬 merge sort *서로 떨어져있는 원소를 교환하는 것이 아니므로, 안정적임 *merge : 정렬을 마친 두 배열을 비교하여 합침 O(n) *전체 시간 복잡도 = O(n log n) (1) sorted 함수 사용하기 -> 정렬을 마친 상태가 아니더라도 적용가능하지만, 빠르지 않음 c=list(sorted(a+b)) (2) heapq 모듈의 merge() 함수 사용하기 ->속도가 빠름 c=list(heapq.merge(a,b)) [2] 퀵 정렬 quick sort 퀵 정렬은 가장 잘 알려진 빠른 정렬 알고리즘이다. pivot을 이용하여 분할 정복 해나가는 알고리즘으로, pivot을 어떤 식으로 정할지가 성능에 크게 영향을 미친다. 평균 시간 복잡도는 O(NlogN) 이며, 만약 매번 1..
1> 단순 선택 정렬 O(n^2) : 말그대로 가장 작은 애 부터 선택해서 순서에 맞는 위치로 옮기며 작업 반복 def select_sort(List): n=len(List) for i in range(n-1 ): min=i for j in range(i,n): if List[min] > List[j]: min=j List[i],List[min]=List[min],List[i] return List List=list(map(int,input().split())) print(*select_sort(List)) 2> 단순 삽입 정렬 O(n^2) : 노드를 하나씩 선택해서 알맞은 위치에 삽입함 def insert_sort(List): k=0 n=len(List) for i in range(1,n): k=i f..
오픈 주소법은 충돌이 발생했을때 재해시 (rehashing) 를 통하여 빈 버킷을 찾아나서는 방법이다. 오픈 주소법은 빈 버킷이 나올때까지 해싱을 반복하기 때문에 선형 탐사법이라고 불리기도한다.. 암튼 주의해야할 점은 버킷에 따로 속성을 부여해줘야한다.! 1. 이 버킷이 데이터가 저장되어있는지 2. 이 버킷이 비어있는지 3. 원래는 뭔가 있었는데, 삭제 명령으로 삭제된 버킷인지 이렇게 총 3가지의 속성을 부여해줘야한다. *재해시 함수를 +1 한 후에 기존의 해시법을 적용하는 방법으로 가정하고 코드를 작성했다. from enum import Enum import hashlib #버킷의 속성지정 class status(Enum): OCCUPIED=0 #데이터가 저장되어있음 EMPTY=1 #버켓이 비어있음 D..
해시법 중에 충돌 대처하는 방법 중 하나인 체인법을 이용하여 구현해보았다. 체인법은 간단하게 해시값이 같은 원소를 연결리스트로 관리하는 방법이다. >> hashlib.sha256(str(key).encode()).hexdigest(),16 이 코드는 처음 알게된 부분이라 따로 etc 카테고리에 issue를 정리할 예정. import hashlib #노드 생성 class Node: #초기화 def __init__(self,key,value,next_v): self.key=key self.value=value self.next=next_v class chaining: def __init__(self,size): self.size=size #테이블의 사이즈 self.table=[None]*self.size #..
[ 개념 ] - 맨 앞부터 스캔하여 순서대로 검색하는 선형탐색과 달리, 이진탐색은 우선, data가 sorting 되어있다는 가정 하에 탐색을 진행한다. 원리는 간단하다. 중앙 값을 선정하여 탐색의 범위를 좁혀나가는 것. 탐색하고자하는 key값이 중앙값 보다 크면 left의 값을 중앙값+1로, key값이 중앙값보다 작으면 right를 중앙값-1로.. 이렇게 점차 탐색 범위를 줄여주는 것이다. [ 적용 기준 ] - 보통 어떤 x에 관해 함수 f(x)가 증가하거나 감소하는 함수일때 start,end를 x에 관한 최소값과 최대값으로 설정하여 이진 탐색으로 문제 해결 [ 코드 ] #검색 대상은 반드시 오름 차순 정렬 되어있어야함! #정렬 되어있다고 가정했을 때의 예제 from typing import Any,S..
python으로 Linked List 구현을 해보았다. c언어로 구현하다가 파이썬으로 구현하려니 헷갈리고 어색하다 1. Link에 대한 구현 class Node: def __init__(self,data): self.data=data self.next=None head=Node(3) next_node=Node(5) head.next=next_node 2. 단순 연결리스트 - 단순 연결리스트의 경우 head가 필요하므로 생성, 길이를 계산하는 것보단 길이를 가지고 있는게 좋을 것 같아서 길이를 추가하였다 * 성능 : O(n) < O(1) 이기 때문 class Node: def __init__(self,data): self.data=data self.next=None #입력받은 객체의 문자열 버전을 반환 d..
오늘은 네이버 실시간 검색순위를 가져오는 실습을 진행해보겠습니다. 1.라이브러리 import 먼저 저번에 설치한 BeautifulSoup 라이브러리와 requests 라이브러리를 import를 통해 불러와줍니다. * 만약 아래 코드를 실행했는데 아무런 변화도 없다면 성공적으로 설치가 완료된 것입니다 ㅎㅎ 2.실시간 네이버 검색순위 가져오기 코드는 이게 전부입니다. 간단하죠 ?? 코드를 하나하나 설명해보겠습니다. requests.get("주소") :requests 라이브러리를 이용하여 원하는 주소를 가져오는 코드입니다. 저희는 naver의 실시간 검색순위가 필요하니 주소부분에 naver메인창의 주소를 가져오면 됩니다. html= BeautifulSoup(r.content,"html.parser") : 보기..
이번 포스팅에서는 기본 라이브러리인 "Beautifulsoup", "Reqeusts" 설치에 대해 알아보겠습니다. 라이브러리(library) 란 ? -컴퓨터 프로그램에서 자주 사용되는 부분 프로그램들을 모아 놓은 것이다. 쉽게 말해서 어떤 프로그램이 돌아갈 수 있게 하는 도구라고 이해하면 쉬울 것 같다. 그럼 이제 크롤링을 좀 더 손쉽게 할 수 있도록 도움을 주는 라이브러리인"Beautifulsoup", "Reqeusts" 를 설치해보도록 하자 Beautifulsoup : HTML태그 등 사진,글 컨텐츠를 가져온 뒤 사용자가 파싱하기 쉽게 도와주는 라이브러리 Requests : 웹에 있는데이터를 요청하는 라이브러리 cmd 창을 이용하여 쉽게 설치할 수 있다. 윈도우 검색에 cmd라고 치면 나오는 명령 프..