알고리즘

ID

27

status

Public

menu

Algorithm

submenu

tags

Data Structure

Algorithm

summary

thumbnail

date

Apr 20, 2024

• 해야함
• dfs
• 백트래킹
• bfs
• 투포인터
• 누적합
• 에라토스테네스의체
• 이분탐색
• 구현 및 시뮬레이션
• 유클리드호제법
• 큐, 스택, 힙, 디큐, 해시

• 가끔 나와서 준비는 해야함
• 다익스트라
• 플로이드워셜
• 유니온파인드
• 크루스칼
• 프림
• LCS
• LIS
• 진법변환

• 하면 좋지만 안해도 지장 없음
• 트라이
• 라빈카프, KMP, 보이어-무어
• 위상정렬

• etc
• 비트마스킹
• DP
• 그리디
• 세그먼트트리

2003번: 수들의 합 2

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/2003

1. Implementation - 구현

2. Dynamic Programmin - 동적계획법

3. Greedy - 그리디

4. Bruteforce - 브루트포스

5. Sorting - 정렬

6. Binary Search - 이분 탐색

7. BFS & DFS - 너비 & 깊이 우선탐색

8. Prefix Sum - 누적합

9. Dijkstra - 다익스트라

10. Disjoint Set - 분리 집합

11. Backtracking - 백 트래킹

12. Stack & Queue - 스택 & 큐

13. Two Pointer - 투 포인터

14. Minimum Spanning Tree - 최소 스패닝 트리

15. Topological Sorting - 위상 정렬

16. Floyd-warshall - 플로이드 와샬

17. Sliding Window - 슬리이딩 윈도우

 

1. 자료구조

• 기본 자료구조
• 배열 (Array)
• 연결 리스트 (Linked List)
• 스택 (Stack)
• 큐 (Queue)

• 연관 자료구조
• 해시맵 (Hash Map)
• 트리 (Tree)
• 이진 탐색 트리 (Binary Search Tree)
• 힙 (Heap)
• 그래프 (Graph)
• 인접 리스트 (Adjacency List)
• 인접 행렬 (Adjacency Matrix)

2. 알고리즘

• 정렬 알고리즘
• 기본 정렬 알고리즘
• 버블 정렬 (Bubble Sort)
• 선택 정렬 (Selection Sort)
• 삽입 정렬 (Insertion Sort)
• 고급 정렬 알고리즘
• 병합 정렬 (Merge Sort)
• 퀵 정렬 (Quick Sort)
• 힙 정렬 (Heap Sort)
• 계수 정렬 (Counting Sort)
• 기수 정렬 (Radix Sort)

• 검색 알고리즘
• 선형 검색 (Linear Search)
• 이진 검색 (Binary Search)
• 이진 탐색 트리 (Binary Search Tree)

• 재귀와 백트래킹
• 기본 재귀 (Basic Recursion)
• 백트래킹 (Backtracking)
• 분할 정복 (Divide and Conquer)

• 그래프 알고리즘
• 탐색 알고리즘
• 깊이 우선 탐색 (DFS)
• 너비 우선 탐색 (BFS)
• 최단 경로 알고리즘
• 다익스트라 알고리즘 (Dijkstra's Algorithm)
• 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
• 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)
• 최소 신장 트리 (MST)
• 크루스칼 알고리즘 (Kruskal's Algorithm)
• 프림 알고리즘 (Prim's Algorithm)
• 기타
• 위상 정렬 (Topological Sorting)

• 동적 프로그래밍 (Dynamic Programming)
• 기본 개념
• 메모이제이션 (Memoization)
• 타뷸레이션 (Tabulation)
• 주요 문제 유형
• 피보나치 수열 (Fibonacci Sequence)
• 배낭 문제 (Knapsack Problem)
• 최장 공통 부분 수열 (Longest Common Subsequence, LCS)
• 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS)
• 동전 거스름돈 문제 (Coin Change Problem)

• 탐욕 알고리즘 (Greedy Algorithms)
• 대표 문제
• 활동 선택 문제 (Activity Selection Problem)
• 그리디로 해결할 수 있는 다양한 문제들

• 분할 정복 (Divide and Conquer)
• 병합 정렬 (Merge Sort)
• 퀵 정렬 (Quick Sort)
• 이진 탐색 (Binary Search)

3. 수학적 알고리즘

• 기본 수학
• 소수 판별 (Prime Number)
• 유클리드 호제법 (Euclidean Algorithm)
• 거듭제곱 (Exponentiation)

• 조합론
• 순열과 조합 (Permutations and Combinations)
• 파스칼의 삼각형 (Pascal's Triangle)

• 비트 조작
• 비트 연산 (Bit Manipulation)
• 비트마스크 (Bitmask)

4. 기타 알고리즘

• 슬라이딩 윈도우 (Sliding Window)

• 투 포인터 (Two Pointers)

• 유니온 파인드 (Union-Find)

• 트라이 (Trie)

• 세그먼트 트리 (Segment Tree)

• 페네윅 트리 (Fenwick Tree)