파이썬 알고리즘 인터뷰
1.파이썬 알고리즘 인터뷰
< 파이썬 알고리즘 인터뷰 챌린지 > 기간 : 2021.7.31 ~ 2021.8.14 목적 : 파이썬 알고리즘 인터뷰 1회독 & 책 내의 문제들 스스로 구현할 수 있도록 완벽히 이해Part 1) 2부 파이썬Part 2) 3부 선형자료구조 - 7장 배열 / 8장 연
2.[2부 파이썬] 6장 문자열 조작
📌 1) 유효한 팰린드롬 ( 리트코드 125. Valid Palindrome ) ✔ 풀이 ✔ 풀이 (슬라이싱 사용) ✔ 풀이 (슬라이싱, 정규표현식 사용) 📝 isalnum(), 정규 표현식 📌 2) 문자열 뒤집기 ( 리트코드 344. Reverse Str
3.[3부 선형 자료구조] 7장 배열
📌 7) 두 수의 합 ( 리트코드 1. Two Sum ) ✔ 풀이 (브루트 포스) => 시간 복잡도 O(n2) ✔ 풀이 (in을 이용한 탐색) => 시간 복잡도 O(n2) , 하지만 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행됨.
4.[3부 선형 자료구조] 8장 연결리스트
📌 13) 팰린드롬 연결 리스트 ( 234. Palindrome Linked List ) ✔ 풀이 (deque 데크 이용) ✔ 풀이 (runner 런너 이용) 📌 14) 두 정렬 리스트의 병합 ( 리트코드 21. Merge Two Sorted Lists ) ✔
5.[3부 선형 자료구조] 9장 스택, 큐
📌 20) 유효한 괄호 ( 리트코드 20. Valid Parentheses ) ✔ 풀이 📝 input = '['인 경우 for문 전체를 반복하고 통과한다. return len(stack) == 0을 하므로써 해당경우에 대한 예외처리를 한다. 📌 21) 중복
6.[3부 선형 자료구조] 10장 데크, 우선순위 큐
📌 26) 원형 데크 디자인 ( 리트코드 641. Design Circular Deque ) ✔ 풀이 📌 27) k개 정렬 리스트 병합 ( 리트코드 23. Merge k Sorted Lists ) ✔ 풀이
7.[3부 선형 자료구조] 11장 해시 테이블
📌 28) 해시맵 디자인 ( 리트코드 706. Design HashMap ) ✔ 풀이 📌 29) 보석과 돌 ( 리트코드 771. Jewels and Stones ) ✔ 풀이 (해시 테이블을 이용한 풀이) ✔ 풀이 (defaultdict을 이용한 비교 생략) ✔
8.[4부 비선형 자료구조] 12장 그래프
📝 재귀함수 종료조건에서 gridi != '1'가 (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid0)) 보다 앞에 있으면 IndexError: list out of range(Runtime Error) 발생📝
9.[4부 비선형 자료구조] 13장 최단 경로 문제
input 👇n = 13flights = \[11,12,74,1,8,91,4,6,13,7,6,39,5,12,8,0,12,54,8,4,32,0,11,4,4,0,91,11,7,64,6,3,88,8,5,80,11,10,91,10,0,60,8,7,92,12,6,78,6,2,
10.[4부 비선형 자료구조] 14장 트리
📌 42) 이진 트리의 최대 깊이 ( 리트코드 104. Maximum Depth of Binary Tree ) ✔ 풀이 (반복구조로 BFS 풀이) 📌 43) 이진 트리의 직경 ( 리트코드 543. Diameter of Binary Tree ) ✔ 풀이 (상태값 누
11.[4부 비선형 자료구조] 15장 힙
📌 55) 배열의 K번째 큰 요소 ( 리트코드 215. Kth Largest Element in an Array ) ✔ 풀이1 (heapq모듈 이용) ✔ 풀이2 (heapq모듈의 heapify 이용) ✔ 풀이3 (heapq모듈의 nlargest 이용) ✔ 풀이4
12.[4부 비선형 자료구조] 16장 트라이
Time Limit Exceeded 시간 제한 초과 👉 더 효율적인 풀이 필요!💡 판별 로직 : wordi + wordj가 팰린드롬이 되는 경우word1 = wordi, word2 = wordj 라고 가정1️⃣ word1 == word2::-1 & word2 ==
13.[5부 알고리즘] 17장 정렬
퀵 정렬 알고리즘으로 구현하면 타임아웃 발생.\-> 퀵 정렬을 변형해 좀 더 최적화를 진행해야함퀵 정렬은 대표적인 불안정 정렬로, 같은 값이 반복될 경우에도 계속하여 스왑을 시도한다. 정렬된 리스트가 입력값으로 들어오게 된다면 계속해서 불균형 리스트로 나뉘게 되기 때문
14.[5부 알고리즘] 18장 이진 검색
📝 파이썬 bisect모듈중앙의 위치를 구하는 풀이 mid = (left + right) // 2에서 버그 발생수학적으로는 문제 없지만 컴퓨터과학에서는 문제를 일으킬 만한 소지가 있음왜? 자료형에는 최대값이 존재하기 때문!즉, 두 수의 합이 자료형의 최대값을 넘어선다
15.[5부 알고리즘] 19장 비트 조작
📌 70) 싱글 넘버 ( 리트코드 136. Single Number ) ✔ 풀이 (XOR풀이) 📌 71) 해밍 거리 ( 리트코드 461. Hamming Distance ) ✔ 풀이 (XOR풀이) 📌 72) 두 정수의 합 ( 리트코드 371. Sum of Two
16.[5부 알고리즘] 20장 슬라이딩 윈도우
풀이1과는 다르게 필요할 때만 전체의 최대값을 계산하고 이외에는 새로 추가되는 값이 최대인지만을 확인하는 형태로 계산량을 줄임👉 그래도 시간 초과 발생함 (n이 매우 큰 경우 시간 초과 발생)👉 조금 더 최적화 필요👉최대값을 계산하는 max 메소드 사용하지 않고
17.[5부 알고리즘] 21장 그리디 알고리즘
👉 풀이1은 Counter모듈을 무리하게 사용한 탓에 속도가 느림.👉 풀이2는 Counter모듈 연산을 빼고, heapq모듈로 로직 구성하여 풀이1보다 약 2배 빠른 속도를 갖음👉 두 번의 루프가 중첩되어 있으므로 O(n2)👉 조금 더 최적화 필요👉 O(n)
18.[5부 알고리즘] 22장 분할 정복
👉 nums.count(num)은 한번 계산해서 재활용함. 이 풀이는 메모이제이션을 이용한 매우 간단한 다이나믹 프로그래밍 풀이.
19.[5부 알고리즘] 23장 다이나믹 프로그래밍
📌 85) 피보나치 수 ( 리트코드 509. Fibonacci Number ) ✔ 풀이1 (재귀 구조 브루트 포스) ✔ 풀이2 (메모이제이션) ✔ 풀이3 (타뷸레이션) ✔ 풀이4 (두 변수만 이용해 공간 절약) 📌 86) 최대 서브 배열 ( 리트코드 53. Maximum Subarray ) ✔ 풀이1 (메모이제이션) ✔ 풀이2 (카데인 알고리즘...
20.배낭 문제 (그리디 알고리즘, 다이나믹 프로그래밍)
배낭에 담을 수 있는 무게의 최대값이 15kg,짐의 값과 무게가 각각 cargo = (4, 12), (2, 1), (10, 4), (1, 1), (2, 2) 일 때, 배낭에 담을 수 있는 짐 가격의 합의 최대값을 return