Algorithm

리스트를 원소로 가지는 리스트로 행렬을 표현할 수 있다. 알고리즘 문제에 자주 사용되는 자료구조이기 때문에 활용법까지 알아보자!

완전 탐색에는 브루트포스와 델타탐색이 있다. 이 두 가지에 대해 알아보겠다.모든 경우의 수를 탐색하여 문제를 해결하는 방식Brute-force는 무식하게 밀어붙인다는 뜻

그래프란 정점(Vertex)과 이를 연결하는 간선(Edge)들의 집합으로 이루어진 비선형 자료구조로, 소셜 네트워크, 지하철 노선도 같이 개체 간의 관계를 나타내기 위해 사용한다.

DFS와 BFS는 그래프 탐색 알고리즘이다. 그래프 탐색 알고리즘이란 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 찾는 알고리즘이다. 그래프의 깊이를 우선으로 탐색하는 DFS와 너비를 우선으로 탐색하는 BFS에 대해 알아보자!

알고리즘 비교의 기준 : CPU 처리 시간! 성능 측정 시 입력을 통일시킴최악의 입력 n개가 들어온다고 가정하고 측정알고리즘의 수행시간 의미(시간 복잡도가 높다 -> 느린 알고리즘)

자기 자신을 다시 호출하는 함수, 재귀함수 사용 시 종료 조건을 명시해야 함(그렇지 않으면 무한루프로 오류 발생)

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함. 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상. DP의 구현은 일반적으로 탑다운, 보텀업으로 구성

소수 : 1보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수, 2부터 나누어 보며 나머지가 남지 않는지 확인하여 소수 판별한다.

두 개의 포인터 위치를 기록하며 처리하는 알고리즘. 순차적으로 접근하여 start 지점과 end 지점 사이의 어떠한 값을 도출하는데 사용됨

기본적으로 정렬된 리스트에서 사용 가능. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하여 O(logN)의 시간복잡도를 가짐. 시작점, 끝점, 중간점을 이용하여 탐색범위 설정

스택에 원소들을 오름차순 또는 내림차순이 유지될 수 있도록 push와 pop을 하는 것. 특정 문제에서 시간 복잡도를 O(N)으로 줄일 수 있음.