Algorithm & Data Structure
1.[알고리즘] 다익스트라(Dijkstra) 알고리즘
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산음의 간선이 없을 때 정상적으로 동작- 현실 세계의 도로그리디 알고리즘으로 분류
2.[알고리즘] 위상정렬(topological sorting)
사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것선수 과목을 고려한 학습 순서 설정 등의 문제에서 사용진입 차수 : 특정한 노드로 들어오는 간선의 개수진출 차수 : 특정 노드에서 나가는 간선의 개수DFS 또는 큐를 활용하여 구현큐를
3.[알고리즘] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘 수행 \- 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 찾는 과정이 필요X플로이드 워셜은2 차원 테이블에 최단 거리 정보를 저장플로이
4.[알고리즘] 그리디(Greedy) 알고리즘
현재 상황에서 지금 당장 좋은 것만 고르는 방법최소한의 아이디어를 떠올릴 수 있는 능력 요구정당성 분석이 중요단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토!
5.[알고리즘] 이분탐색(Binary Search)
• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인• 이분 탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법(시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정)단게마다 탐색 범위를 2로 나누
6.[자료구조] 우선순위 큐(Priority Queue)
우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조리스트를 이용하여 구현 삽입시간 : O(1)삭제시간 : O(N)힙 자료구조를 이용하여 구현삽입시간 : O(logN)삭제시간 : O(logN)단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙
7.[알고리즘] 소수판별, 투포인터, 구간합
소수1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수약수의 성질모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸따라서 소수를 판별할 때, 가운데 약수까지만 확인하면 됨(Math.sqrt(x)다수의 자연수에 대하여