young-hun-jo/PythonTeamNotes

This is a reference about the algorithm by native python

🐍 PythonTeamNotes

• 알고리즘을 native Python으로 구현한 소스코드를 기록하는 레포지토리

🔍 Search(탐색)

• DFS(깊이우선탐색)
  • 유방향 그래프에서 사이클 판별
  • 부분집합 구하기
  • 중복순열 구하기
  • 순열 구하기
  • 조합 구하기
• BFS(너비우선탐색)
• Linear(Sequential) Search(선형탐색)
• Binary Search(이진탐색)
  • 이진탐색을 활용해 정렬된 배열에서 특정한 원소를 찾는 방법: bisect 라이브러리 활용

🌪 Dynamic Programming(동적 프로그래밍)

• 메모제이션 기법(Top-Down 방식): 재귀함수 활용
• DP 테이블 기법(Bottom-Up 방식): for loop 활용
• 가장 긴 증가하는 부분 수열 길이 찾는 LIS(Longest Increasing Sequence)
• 한 문자열에서 다른 문자열로 편집하는 최소 연산 횟수
• 중복 여부에 따른 냅색(Knapsack) 알고리즘

🗂 Sort(정렬)

• Selection Sort(선택 정렬)
• Insertion Sort(삽입 정렬)
• Quick Sort(퀵 정렬)
• Merge Sort(병합 정렬)
• Counting Sort(계수 정렬)
• Heap Sort(최소/최대 힙 정렬)
• 그래프 데이터를 사용하는 Topology Sort(위상 정렬)

🛣 Shortest Path(최단 경로)

• 다익스트라(Dijksttra) 알고리즘
  • 간단한 방법
  • 우선순위 큐 활용한 방법
• 플로이드-워셜(Floyid-Warshall) 알고리즘

💡 Graph(그래프 알고리즘)

• 서로소 집합 자료구조
  • 서로소 집합 자료구조 알고리즘
  • 무방향 그래프에서 사이클 판별
• 신장트리
  • 크루스칼 알고리즘
    • 전체 그래프에서 최소 신장 트리 2개로 분할하는 방법: 최초의 최소 신장 트리에서 비용이 가장 큰 간선 제거하기

🔗 Etc Algorithm(기타 알고리즘)

• 특정 수 소수(Prime Number) 판별 알고리즘
• 주어진 범위 내 다수의 소수 판별 알고리즘(에라토스테네스의 체)
• 투 포인터(Two Pointer)
  • 특정한 합을 갖는 부분 연속 수열 찾는 알고리즘
  • 정렬된 두 리스트 합집합 후 정렬하는 알고리즘
    • 병합 정렬(Merge Sort)에 사용됨
• 구간 합
  • 특정 구간의 모든 수를 합하는 알고리즘
• 2차원 리스트 90도 회전시키기
• 2차원 리스트 테두리 시계방향으로 1칸 이동하기
• 상,하,좌,우 왼쪽/오른쪽 방향으로 그 때마다 다른 방향으로 회전 가능한 알고리즘
• 나누기 연산자(%)는 분배법칙 가능
• 몫(//), 나누기(%) 연산 활용해 정수 자릿수 합, 뒤집기 구현
• 리스트 원소 개수 별 슬라이딩 윈도우
• 10진수와 n진수 상호 변환
• 유클리드 호제법
  • 최대공약수 구하기
  • 최소공배수 구하기