분리집합(Union-Find)은 그래프 알고리즘 중 하나로 코딩 테스트 킬러 문제로 주로 나오는 알고리즘입니다. 서로소 집합 일단 유니온 파인드 알고리즘을 알기 전 disjoint sets을 먼저 이해해야 하는데요, 쉽게 설명하면 공통 원소가 없는 두 집합을 뜻합니다. 아래 그림을 보시면 왼쪽은 서로소 집합을 나타내고 오른쪽은 공통된 7이라는 원소 때문에 서로소 관계가 깨지게 됩니다. 따라서 왼쪽은 서로소 집합, 오른쪽은 서로소 집합이 아니게 되는 것이죠. Union-Find는 서로소 집합 자료구조를 만들 수 있습니다. 집합에서 노드들을 합치고(Union), 부모를 찾아(Find) 서로소 집합을 찾아내는 알고리즘인 것이죠. 한마디로 DSU(Disjoint Sets Union) 자료구조를 만들어 내는 과정..
힙의 개념 힙은 완전 이진트리로 구성된 자료구조이다. 우선순위 큐를 위해 만들어진 자료구조이다. 힙 자료구조로 우선순위 큐를 구현할 때 삽입 삭제 모두 O(logN) 연산을 가진다. 최소 힙: 부모 노드의 값이 자식노드의 값보다 항상 작은 힙 최대 힙: 부모 노드의 값이 자식노드의 값보다 항상 큰 힙 위 사진과 같이 항상 완전 이진트리로 구성되어 최소 최대 값을 빠르게 찾아낼 수 있도록 설계되어있다. heapq 모듈 파이썬에선 heapq 모듈을 이용하여 최소 힙과 최대 힙 모두 구현할 수 있다. heapq 메서드 heappush(heap, item) 힙 불변성을 유지하면서 item 값을 heap으로 푸쉬한다. heapq.heappop(heap) 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 po..
최근 알고리즘 테스트 공부를 위해서 파이썬을 꽤나 자주 이용하는데, 문제에서 빈번하게 사용되는 deque에 대해서 알아봅시다! Deque, 왜 쓰나요? 먼저 주 언어가 Javascript였던 제가, 파이썬으로 알고리즘을 하게 된 가장 큰 이유가 바로 deque의 유무였습니다. 자바스크립트에서 후입선출 방식의 Queue나 양쪽에서 삽입 삭제가 가능한 Double-ended Queue 같은 자료구조를 구현하기 위해선, 링크드리스트를 거의 필수로 사용해야 했습니다. 예를 들어 1, 2, 3이 있는 배열을 큐 방식으로 넣고 뺀다고 생각해 봅시다. 1, 2, 3에서 가장 먼저 들어왔던 1의 값만 뺀다고 생각 해봅시다. 그럼 1을 빼기 위해서, 뒤에 있는 모든 index들이 한 칸 앞으로 와야 하는 귀찮은 일이 발..
이번엔 파이썬 크롤러 라이브러리를 사용하여 학교 공지 사항 크롤링을 진행 해보려고 한다. https://www.crummy.com/software/BeautifulSoup/bs4/doc/ Beautiful Soup Documentation — Beautiful Soup 4.9.0 documentation Non-pretty printing If you just want a string, with no fancy formatting, you can call str() on a BeautifulSoup object, or on a Tag within it: str(soup) # ' I linked to example.com ' str(soup.a) # ' I linked to example.com ' The..
한창 JS를 하다가 Python에 이번엔 제대로 입문 해보려고 토이 프로젝트를 만들려고 생각했다. 고민 고민 하다보니, 내가 카카오톡 다음으로 많이 사용하는 채팅 프로그램인 Discord 봇 개발 관련으로 다시 한번 도전 해 볼까 하여 블로그에 정리 하면서 개발을 시작 해보려고 한다. Python으로 개발을 진행 하기 위해선 discord.py 라이브러리를 사용하여 개발 하여야 한다. Python 언어나, 다른 개발 언어를 접해보고 진행 하는 것을 추천한다. 무턱대고 개발 해보기엔 난이도가 생각보다 좀 있다. https://codingapple.com/course/python-basic/ 빠르게 정리하는 파이썬 기초 문법 - 코딩애플 온라인 강좌 (파이썬 웹크롤러/업무자동화 강의 + 딥러닝 AI 강의 패..
