트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 트리는 항상 하나의 루트(Root)에서 시작되며, 자식(Child) 노드를 가지고, 간선(Edge)으로 연결되어 있다 차수(Degree): 자식 노드의 개수, 크기(Size): 자신을 포함한 모든 자식 노드의 개수 높이(Height): 현재 위치에서부터 리프까지의 거리, 깊이(Depth): 루트에서부터 현재 노드까지의 거리 레벨은 루트에서 0이고, 노드 A의 자식노드는 A의 레벨 + 1 트리는 순환 구조를 갖지 않는 그래프, 단방향, 하나의 부모 노드, 하나의 루트 이진 트리: 가장 널리 사용되는 트리 자료구조 m-ary 트리(..
Python
최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제 정점: 교차로, 간선: 길, 가중치: 거리 & 시간 등의 이동 비용 다익스트라 알고리즘: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 -> BFS 이용 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다 743. network delay time - 다익스트라 알고리즘 -> 시작점에서 각 노드까지 최단시간 계산하고 저장(BFS) 및 계산되지 않는 노드 여부 확인 heapq 모듈에는 우선순위 업데이트 기능 없음 이전 노드의 값이 무엇인지 필요없으므로 생략 787. cheapest flights within k stops - 다익스트라 알고리..
그래프: 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 오일러 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프 경로(= 한붓그리기) 모든 정점(vertex)이 짝수 개의 차수(degree)를 갖는다면 오일러 경로 해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 최적 알고리즘이 없는 대표적인 NP-완전 문제 (NP문제 중 NP-난해 문제) 해밀턴 순환: 원래의 출발점으로 돌아오는 경로 외판원 문제: 최단거리인 해밀턴 순환을 찾는 문제 -> 다이나믹 프로그래밍으로 최적화 그래프 순회 (그래프 탐색): 그래프의 각 정점을 방문하는 과정 깊이 우선 탐색(DFS)이 너비 우선 남색(BFS)에 비해 더 널리 쓰임 DFS는 주로 스택이나 재귀로 구현(재귀 선호), BFS는 주로..
해시 테이블(해시 맵): 키를 값(해시)에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현하는 자료구조 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1) 해시 함수: 임의 크기 데이터를 고정 크기 값(해시)으로 매핑하는 데 사용할 수 있는 함수 해시 함수가 값을 매핑할 때 충돌을 최소화하는 것이 무엇보다 중요함 로드 팩터: 해시 테이블에 저장된 데이터 개수를 버킷의 개수로 나눈 것 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 개별 체이닝: 충돌 발생 시 연결리스트로 연결 오픈 어드레싱: 충돌 방생 시 탐사를 통해 빈 공간을 찾는 방식 전체 슬롯 개수 이상 저장 불가, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음 데이터들이 고르지 않고 뭉치는 ..
- 데크 (double-ended queue): 양 쪽에서 삽입 및 삭제 가능 - ADT는 이중연결리스트로 구현 641. design circular deque - 이중 연결 리스트로 구현(빈 head, tail) * 배열은 첫 인덱스에 삽입 시 O(n) - 우선순위 큐: 특정 조건에 따른 우선순위가 가장 높은 순으로 추출 (ex. 최댓값 추출) -> 정렬 알고리즘으로 구현 가능 - 다익스트라 알고리즘이나 힙 자료구조와 관련이 깊음 23. merge k sorted lists - 파이썬 heapq 모듈 (최소 힙): 이진 트리 기반 1. 원소들이 정렬된 상태(키 기준)로 삽입, 삭제 2. 가장 작은 원소가 첫 인덱스에 위치 3. 모든 원소들은 자식 원소들보다 작거나 같게 위치 * 두번째로 작은 값 확인하..
- 스택: lifo, 큐: fifo - 파이썬 리스트는 스택과 큐의 모든 연산 수행 가능 - 그러나 성능을 고려한다면 큐는 데크를 사용해야 좋음 - 스택 ADT에서는 차곡차곡 쌓이지만, 실제 연결리스트로 구현 시 무작위로 배치되고 포인터로 처리 ※ 참고: 클래스의 메소드에서 self는 인스턴스 자체, 인스턴스로 메소드 호출하면 자동으로 인스턴스(self) 인자로 넣음 20. valid parentheses - 딕셔너리 활용 - 스택에 왼 괄호 쌓기 316. remove duplicate letters - 재귀(분리 가능하냐로 접근) - 스택에 문자 쌓으면서 비교 - collections.Counter() 739. daily temperatures * [0] * len(T) - 스택에 인덱스 쌓으면서 온도..
234. palindrome linked list - 리스트로 변환 - 데크 - 런너 * 다중할당: 동시에 일어남 21. merge two linked lists - 재귀 (함수 안에서 다시 함수 호출) - 괄호가 연산순위 제일 높음 206. reverse linked list - 재귀 - 반복 - 내 풀이: 런너 2. add two numbers - 연결 리스트 만들때 더미 노드 생성 필수 - 전가산기 응용 - divmod() * map() * functools 모듈(reduce 메소드) * operator 모듈(add, mul 메소드) ※ b가 a를 참조할 때, a가 가변객체인 경우(list, set, dict) b에서 값을 조작하면 두 객체 모두에게 적용 (불변객체인 경우 b는 더이상 a를 참조하지..
1. two sum - brute force - in - enumerate - 투포인터로는 인덱스 엉망 42. trapping rain water - 투포인터 - 스택(변곡점) 15. 3 sum - brute force (x) - 투포인터 ※ 투포인터는 주로 정렬된 배열을 대상으로 두개의 포인터가 좌우로 자유롭게 움직이며 풀이 561. array partition 1 - 오름차순 - 슬라이싱 238. product of array except self - 왼쪽 곱셈 결과 저장 후 오른쪽 곱셈 결과 차례로 곱하기 121. best time to buy and sell stock - brute force(x) - sys.maxsize, float('inf') - 저점과 현재값 차이 카운팅
125. valid palindrome - str.isalnum()이나 정규식으로 전처리 - 데크로 최적화 - pop()이나 슬라이싱으로 판별 344. reverse string - 투포인터로 스왑 - list.reverse() - s[:] 937. reorder log files - str.isdigit() - 람다 표현식, 리스트 + - list.sort(key=) 819. most common word - 정규식으로 전처리 - collections.defaultdict(int), collections.Counter() 49. group anagrams - ''.join() - collections.defaultdict(list) 5. longest palindrome substring - 투포인터 ..
DB 세팅 # init_db.py import requests from bs4 import BeautifulSoup from pymongo import MongoClient client = MongoClient('localhost', 27017) db = client.dbsparta # DB에 저장할 영화인들의 출처 url을 가져옵니다. def get_urls(): headers = { 'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64)AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.86 Safari/537.36'} data = requests.get('https://movie.naver.com/movi..
