그 땐 Algorithm했지/그 땐 Python했지 (21) 썸네일형 리스트형 [TAVE/파이썬 알고리즘] Ch10 | 데크, 우선순위 큐 - 개념 정리 개념 정리 📌데크: 스택과 큐 자료형의 특징을 모두 갖고 있는 복합 자료형이다. 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. 👉🏻배열이나 연결 리스트로 구현할 수 있다. 👉🏻그림과 같이 이중 연결 리스트로 구현하면 양쪽처럼 HEAD와 TAIL이라는 이름의 두 포인터를 가지고 있다가 새로운 아이템이 추가될 때마다 앞쪽 혹은 뒤쪽으로 연결시켜준다. 연결 후에는 포인터를 이동하면 된다. import collections d = collections.deque() type(d) # 👉🏻파이썬은 collections 모듈에서 deque라는 이름으로 데크 자료형을 지원한다. 이 deque는 이중 연결 리스트로 구현되어 있다. [TAVE/파이썬 알고리즘 인터뷰] Ch12 | 그래프 - 개념 정리 참고자료 : 파이썬 알고리즘 인터뷰 ✅그래프란? 👉🏻객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 ✍🏻쾨니히스베르크에 있는 섬과 도시를 연결하는 7개의 다리를 한 번씩만 건너서 모두 지나가는 해법을 찾으며 시작되었다. 오일러 경로 A ~ D는 정점 a ~ g는 간선 👉🏻오일러의 주장: 모든 정점이 짝수 개의 차수를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다. 👉🏻오일러의 정리: 칼 히어홀저가 수학적으로 증명했다. ✍🏻쾨니히스베르크의 다리는 모든 정점이 짝수 개의 차수를 갖지 않으므로 오일러 경로가 아니다. 해밀턴 경로 👉🏻각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로이다. 최적 알고리즘이 없는 대표적인 NP-완전 문제다. 👉🏻해밀턴 순환: 원래의 출발점으로 돌아오는 경로.. [TAVE/파이썬 알고리즘] Ch8 | 연결 리스트 - 13번 팰린드롬 연결 리스트(leetcode 234) 📌연결 리스트: 선형적인 자료구조이다. 구조체 각각이 서로 연결된 형태로 구성되어 있고 메모리 어딘가에 흩뿌려져 있다. 해당 구조체는 다음 구조체가 무엇인지에 대한 정보를 담고 있어 연결된 형태를 유지할 수 있는 것이다. 📌팰린드롬: 회문이라고도 부른다. 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 리스트 변환 1️⃣파이썬의 리스트로 변환한다. q: List = [] node = head #리스트 변환 while node is not None: q.append(node.val) node = node.next 2️⃣pop함수에 인덱스를 지정해 요소를 추출하며 같은 값인지 확인한다. #팰린드롬 판별 while len(q) > 1: if q.pop(0) != q.pop(): r.. [TAVE/파이썬 알고리즘] Ch7 | 배열 - 11번 자신을 제외한 배열의 곱 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈 1️⃣왼쪽→오른쪽 방향으로 곱한다. out = [] #왼쪽 곱셈 p = 1 for i in range(0, len(nums)): out.append(p) p = p * nums[i] 📌공간 복잡도는 O(1)을 위해 기존 out 변수를 재활용한다. 👉🏻p와 리스트의 각 요소들 간의 곱셈 결과를 그대로 out 리스트에 담는다. 👉🏻결과: [1, 1, 2, 6] ✍🏻만약 별도의 리스트 변수를 만들고 그 변수에 우측 곱셈 결과를 넣으면 공간 복잡도는 O(1)이 된다. ✅공간복잡도 O(n) 👉🏻저장되는 메모리, 변수 양에 따라서 공간복잡도가 결정된다. 배열이 중첩될수록 n의 차수가 높아진다. ✍🏻참고로 시간복잡도는 코드 실행의 시간에 따라 결정된다. for문이 중첩될수.. [TAVE/파이썬 알고리즘] Ch6 | 문자열 조작 - 4번 가장 흔한 단어 리스트 컴프리헨션, Counter 객체 사용 1️⃣ Data Cleansing 📌입력값에 대한 전처리 작업 👉🏻대소문자가 섞이고 쉼표 등 구두점 등을 처리해준다. words = [word for word in re.sub(r'[^\w]', ' ', paragraph) .lower().split() if word not in banned] ✍🏻정규식 문법 ＼w 단어 문자 ^ not 👉🏻단어 문자가 아닌 모든 문자를 공백으로 치환하는 역할을 한다. 👉🏻다음으로 소문자로 바꿔주고 공백으로 나눠준다. 👉🏻마지막으로 if문을 써주어 금지 단어를 제외한 단어들을 리스트로 저장한다. 2️⃣ 흔한 단어 추출 counts = collection.defaltdict(int) for word in words: counts[.. 이전 1 2 3 다음
