README.md

Coding_Interview

LeetCode 문제 풀이

• 개발 언어 및 도구
  • "Python 3.7+" , 리트코드, 파이참 커뮤니티 에디션

---

문자열 조작

• LeetCode 125 유효한 팰린드롬 (Two Pointers, String)
  • 리스트로 변환
  • 데크 자료형을 이용한 최적화
  • 슬라이싱 사용
• LeetCode 344 문자열 뒤집기 (Two Pointers, String, Recursion)
  • 투 포인터를 이용한 스왑
  • Pythonic
• LeetCode 937 로그 파일 재정렬 (Array, String, Sorting)
  • 람다와 +연산자를 이용
• LeetCode 819 가장 흔한 단어 (Hash Table, String, Counting)
  • 리스트 컴프리헨션, Counter 객체 사용
• LeetCode 49 그룹 애너그램 (Hash Table, String, Sorting)
  • 정렬하여 딕셔너리에 추가
• LeetCode 5 가장 긴 팰린드롬 부분 문자열 (String, Dynamic Programming)
  • 중앙을 중심으로 확장하는 풀이

---

선형 자료구조

• 배열

  • LeetCode 1 두 수의 합 (Array, Hash Table)
    • 브루트 포스로 계산
    • in을 이용한 탐색
    • 첫 번쨰 수를 뺀 결과 키 조회
    • 조회 구조 개선
  • LeetCode 42 빗물 트래핑 (Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack)
    • 스택 쌓기
    • 투 포인터를 최대로 이동
  • LeetCode 15 세 수의 합 (Array, Two Pointers, Sorting)
    • 브루트 포스로 계산
    • 투 포인터로 합 계산
  • LeetCode 561 배열 파티션 1 (Array, Greedy, Sorting, Counting Sort)
    • 오름차순 풀이
    • 짝수 번째 값 계산
    • Pythonic
  • LeetCode 238 자신을 제외한 배열의 곱 (Array, Prefix Sum)
    • 왼쪽 곱셈 결과에 오르쪽 값을 차례대로 곱셈
  • LeetCode 121 주식을 사고팔기 가장 좋은 시점 (Array, Dynamic Programming)
    • 브루트 포스로 계산
    • 저점과 현재 값과의 차이 계산

• 연결리스트

  • LeetCode 234 팰린드롬 연결 리스트 (Linked List, Two Pointers, Stack, Recursion)
    • 리스트 변환
    • 데크를 이용한 최적화
    • 런너를 이용한 우아한 풀이
  • LeetCode 21 두 정렬 리스트의 병합 (Linked List, Recursion)
    • 재귀 구조로 연결
  • LeetCode 206 역순 연결리스트 (Linked List, Recursion)
    • 재귀 구조로 뒤집기
    • 반복 구조로 뒤집기
  • LeetCode 2 두 수의 덧셈 (Linked List, Math, Recursion)
    • 자료형 변환
    • 전가산기 구현
  • LeetCode 24 페어의 노드스왑 (Linked List, Recursion)
    • 값만 교환
    • 반복 구조로 스왑
    • 재귀 구조로 스왑)
  • LeetCode 328 홀짝 연결 리스트 (Linked List)
    • 반복 구조로 홀짝 노드 처리
  • LeetCode 92 역순 연결 리스트 (Linked List)
    • 반복 구조로 노드 뒤집기

• 스택, 큐

  • LeetCode 20 유호한 괄호 (String, Stack)
    • 스택 일치 여부 판별
  • LeetCode 316 중복 문자 제거 (String, Stack, Greedy, Monotonic Stack)
    • 재귀를 이용한 분리
    • 스택을 이용한 문자 제거
  • LeetCode 739 일일온도 (Array, Stack, Monotonic Stack)
    • 스택 값 비교
  • LeetCode 225 큐를 이용한 스택 구현 (Stack, Design, Queue)
    • push() 할 때 큐를 이용해 재정렬
  • LeetCode 232 스택을 이용한 큐 구현 (Stack, Design, Queue)
    • 스택 2개 사용
  • LeetCode 622 원형 큐 디자인 (Array, Linked List, Design, Queue)
    • 배열을 이용한 풀이

• 데크, 우선 순위 큐

  • LeetCode 641 원형 테크 디자인 (Array, Linked List, Design, Queue)
    • 이중 연결 리스트
  • LeetC0de 23 k개 정렬 리스트 병합 (Linked List, Divide and Conquer, Heap(Priority Queue), Merge Sort)
    • 우선순위 큐를 이용한 리스트 병합

• 해시 테이블

  • LeetCode 706 해시맵 디자인 (Array, Hash Table, Linked List, Design, Hash Function)
    • 개별 체이닝 방식을 이용한 해시 테이블 구현
  • LeetCode 771 보석과 돌 (Hash Table, String)
    • 해시 테이블을 이용한 풀이
    • defaultdict를 이용한 비교 생략
    • Counter로 계산 생략
    • Pythonic
  • LeetCode 3 중복 문자 없는 가장 긴 부분 문자열 (Hash Table, String, Sliding Window)
    • 슬라이딩 윈도우와 투 포인터로 사이즈 조절
  • LeetCode 347 상위 K 빈도 요소 (Array, Hash Table, Divide and Conquer, Sorting, Heap(Priority Queue), Bucket Sort, Counting, Quickselect)
    • Counter를 이용한 음수 순 추출
    • Pythonic

---

비선형 자료구조

• 그래프

  • Leetcode 200 섬의 개수(Array, Depth-First Search, Breadth-First Search, Union Find, Matrix )
    • DFS로 그래프 탐색
  • Leetcode 17 전화 번호 문자 조합 (Hash Table, String, Backtracking)
    • 모든 조합 탐색
  • Leetcode 46 순열 (Array, Backtracking)
    • DFS를 활용한 순열 생성
    • itertools 모듈 사용
  • LeetCode 77 조합 (Backtracking)
    • DFS로 K개 조합 생성
    • itertools 모듈 사용
  • LeetCode 39 조합의 합 (Array, Backtracking)
    • DFS로 중복 조합 그래프 탐색
  • LeetCode 78 부분 집합 (Array, Backtracking, Bit Manipulation)
    • 트리의 모든 DFS 결과
  • LeetCode 332 일정 재구성 (Depth-First Search, Graph, Eulerian Circuit)
    • DFS로 일정 그래프 구성
    • 스택 연산으로 쿠 연산 최적화 시도
    • 일정 그래프 반복
  • LeetCode 207 코스 스케줄 (Depth-First Search, Breadth-First Search, Graph, Topological Sort)
    • 가지치기를 이용한 최적화

• 최단 경로 문제

  • LeetCode 743 코스 스케줄 (Depth-First Search, Breadth-First Search, Graph, Heap(Priority Queue), Shortest Path)
    • DFS로 순환 구조 판별
  • LeetCode 787 K경유지 내 가장 저렴한 항공권 (Dynamic Programming, Depth-First Search, Breadth-First Search, Graph, Heap(Priority Queue), Shortest Path)
    • 다익스트라 알고리즘 응용

• 트리

  • LeetCode 104 이진 트리의 최대 깊이 (Tree, Depth-First Search, Breadth-First Search, Binary Tree)
    • 반복 구조로 BFS 풀이
  • LeetCode 543 이진 트리의 직경 (Tree, Depth-First Search, Binary Tree)
    • 상태값 누적 트리 DFS
  • LeetCode 687 가장 긴 동일 값의 경로 (Tree, Depth-First Search Binary Tree)
    • 상태값 거리 계산 DFS
  • LeetCode 226 이진 트리 반전 (Tree, Depth-First Search, Breadth-First Search, Binary Tree)
    • Pythonic
    • DFS
    • DFS2
    • Post-Order
  • LeetCode 617 두 이진 트리 병합
    • 재귀 탐색 (Tree, Depth-First Search, Breadth-First Search, Binary Tree)
  • LeetCode 297 이진 트리 직렬화 & 역직렬화 (String, Tree, Depth-First Search, Breadth-First Search, Design, Binary Tree)
    • 렬화 & 역직렬화 구현
  • LeetCode 110 균형 이진 트리 (Tree, Depth-First Search, Binary Tree)
    • 재귀 구조로 높이 차이 계산
  • LeetCode 310 최소 높이 트리 (Depth-First Search, Breadth-First Search, Graph, Topological Sort)
    • 단계별 리프 노드 제거
  • LeetCode 310 최소 높이 트리 (Depth-First Search, Breadth-First Search, Graph, Topological Sort)
    • 단계별 리프 노드 제거
  • LeetCode 1038 이진 탐색 트리를 더 큰 수 합계 트리로 (Tree, Depth-First Search, Binary Search Tree, binary Tree)
    • 중외 순회로 노드 값 누적
  • LeetCode 938 이진 탐색 트리 합의 범위 (Tree, Depth-First Search, Binary Search Tree, Binary Tree)
    • 재귀 구조 DFS로 부르트 포스 탐색
    • DFS 가지치기로 필요한 노드 탐색
    • 반복 구조 DFS로 필요한 노드 탐색
    • 반복 구조 DFS로 필요한 노드 탐색 (큐)
  • LeetCode 783 이진탐색트리(BST) 노드간 최소 거리 (Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree)
    • 재귀 구조로 중위 순회
    • 반복 구조로 중위 순회
  • LeetCode 105 전위, 중위 순회 결과로 이진 트리 구축 (Array, Hash Table, Divide and Conquer, Tree, Binary Tree)
    • 전위 순회 결과로 중위 순회 분할 정복

• 힙

  • LeetCode 215 배열의 K번째 큰 요소 (Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect)
    • heapq 모듈 이용
    • heapq 모듈의 heqpify 이용
    • heqpq 모듈의 nlargest 이용
    • 정렬을 이용한 풀이

• 트라이

  • LeetCode 208 트라이 구현 (Hash Table, String, Design, Trie)
    • 딕셔너리를 이용해 간결한 트라이 구현
  • LeetCode 336 팰린드롬 페어 (Array, Hash Table, String, Trie)
    • 팰린드롬을 브루트 포스로 계산
    • 트라이 구현

---

알고리즘

• 정렬

  • LeetCode 148 리스트 정렬 (Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort)
    • 병합정렬
    • 내장 함수를 이용하는 실용적인 방법
  • LeetCode 56 구간 병합 (Array, Sorting)
    • 정렬하여 병합
  • LeetCode 147 삽입 정렬 리스트 (Linked List, Sorting)
    • 삽입 정렬
    • 삽입 정렬의 비교 조건 개선
  • LeetCode 179 가장 큰 수 (String, Greedy, Sorting)
    • 삽입 정렬
  • LeetCode 242 유효한 애너그램 (Hash Table, String, Sorting)
    • 정렬을 이용한 비교
  • LeetCode 75 색 정렬 (Array, Two Pointers, Sorting)
    • 네덜란드 국기 문제를 응용한 풀이
  • LeetCode 973 원점에 K번째로 가까운 점 (Array, Math, Divide and Conquer, Geometry, Sorting, Heap(Priority Queue), Quickselect)
    • 유클리드 거리의 우선순위 큐 순서

• 이진검색

  • LeetCode 704 이진 검색 (Array, Binary Search)
    • 재귀 풀이
    • 반복 풀이
    • 이진 검색 모듈
    • 이진 검새을 사용하지 않는 index 풀이
  • LeetCode 33 회전 정렬된 배열 검색 (Array, Bianry, Search)
    • 피벗을 기준으로 한 이진 검색
  • LeetCode 349 두 배열의 교집합 (Array, Hashtable, Two Pointers, Binary Search, Sorting)
    • 부르트 포스로 계산
    • 이진 검색으로 일치 여부 판별
    • 투 포인터로 일치 여부 판별
  • LeetCode 167 두 수의 합 II (Array, Two Pointers, Binary Search)
    • 투 포인터
    • 이진 검색
    • bisect 모듈 + 슬라이싱
    • bisect 모듈 + 슬라이싱 최소화
    • bisect 모듈 + 슬라이싱 제거
  • LeetCode 240 2D 행렬 검색 II (Array, Binary Search, Divide and Conquer, Matrix)
    • 첫 행의 맨 뒤에서 탐색

• 비트 조작

  • LeetCode 136 싱글 넘버 (Array, Bit Manipulation)
    • XOR 풀이

• 슬라이딩 윈도우

• 그리디 알고리즘

  • LeetCode 122 주식을 사고팔기 가장 좋은 시점 2 (Array, Dynamic Programming, Greedy)
    • 그리디 알고리즘
    • Pythonic
  • LeetCode 406 키에 따른 대기열 재구성 (Array, Greedy, Binary Indexed Tree, Segment Tree, Sorting)
    • 우선순위 큐 이용
  • LeetCode 621 태스크 스케줄러 (Array, Hash Table, Greedy, Sorting, Heap(Priority Queue), Counting)
    • 우선순위 큐 이용
  • LeetCode 134 주유소 (Array, Greedy)
    • 모두 방문
    • 한 번 방문
  • LeetCode 455 쿠키 부여 (Array, Greedy, sorting)
    • 그리디 알고리즘
    • 이진 검색

• 분할 정복

• 다이나믹 프로그래밍

---

Sang.Kil. Park, 파이썬 알고리즘 인터뷰, 책만, 2020, pp.14-35.

pythaac, 다익스트라 알고리즘 응용), onlybooks/python-algorithm-interview#104