- Array
Array List continuous
Linked list discontinous
배열은 연속적인 메모리 공간에 저장되지만, ArrayList는 동적으로 크기가 변경되는 연속적인 메모리 공간 사용을 한다.
배열은 고정되어 있지만, ArrayList는 동적으로 크기가 변경될 수 있다.
배열은 중간 삽입/ 삭제 시 데이터 이동이 필요하지만 ArrayList는 동적 크기 조절로 인하여 상대적으로 효율적이다.
삽입과 삭제가 편함
연결 리스트는 불연속적인 메모리 공간을 저장하고, 배열에 비해 삽입과 삭제가 편하고, 연셜 리스트의 시작 또는 끝 부분에서의 삽입/삭제는 O1 시간 복잡도를 가진다. 연결 리스트는 순차적으로 탐색해야하므로 배열에 비하여 탐색 효율성이 낮다.
- 시간복잡도
완전 탐색: 노가다로 일일히 다해보는 방법, 컴퓨터에 특화, 컴퓨터는 빠르기 때문에 결과가 빨리 나옴
가장 단순한 방법이지만 개인적으로는 가장 어려운 것 같음, 정해진 틀이 없기 때문에
재귀 함수
재귀 함수는 문제해결의 간결성을 위해서 사용되고, 팩토리얼이나, 피보나치 수열 계산과 같은 문제는 재귀함수를 사용하면 간단하게 구현할 수 있다.트리 구조나 수열과 같은 문제들은 재귀적으로 해결하기 적합하고 코드의 가독성이 향상될 수 있다. 하지만 메모리 사용이 증가할 수 있고, 반복문에 비해 오버헤드로 인한 성능이 낮아 질 수 있다.
Solution 함수는 num 리스트와 target 값을 입력받고, 내부에 recur 함수를 정의하여 재귀적으로 해결하고자 접근한다.
n은 nums 리스트의 길이를 저장하고, 초기화하며, recur 함수에서는 ans리스트와 start의 인덱스를 입력받고, ans 리스트는 현재까지 찾은 두 개의 인덱스를 저장하는 리스트이고, start는 현재 탐색을 시작할 위치를 나타낸다.
if lenans ==2: 조건은 ans 리스트에 두 개의 인덱스가 있는지 확인하고, 두 개의 인덱스가 있다면 더해서 타겟의 조건이 되는 지 확인하고, 만족하면 ans 리스트를 반환하고, 그렇지 않으면 False를 반환한다.
그리고 start부터 n까지 순회하고 재귀적으로 하며 중요한 것은 recur함수가 다음 인덱스 부터 재귀 호출이 된다는 것이다.
BFS
BFSBreath−FirstSearch는 그래프 탐색 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례대로 방문하는 방식이고, 큐 자료를 사용해서 방문할 노드를 순서대로 관리한다.
먼저 큐 초기화 및 시작 노드를 추가하고, 큐가 빌 때까지 반복한다. 그래프의 데이터 구조는 인접 리스트 형태로 표현되어 있고, 각 키는 노드를 값은 해당 노드의 인접 노드 리스트를 나타낸다. BFS는 최단 경로 찾기, 웹 크롤링, 미로 탐색, 레벨 순회, 너비 우선 탐색 구축을에 사용된다.
이 코드는 연습한 코드이고, q를 생성하고, start_v에 큐를 추가하고, visted 방문한 값에 start_v를 True로 표시한다. 그리고 q일 동안에 현재 노드를 popleft로 출력하고, 그래프에서 cur_v 값이 있고, 방문하지 않았으면 큐에 next_v를 추가해주고, visted를 True로 바꿔준다.
DFS
DFS는 그래프 탐색 알고리즘의 한 종류로, 깊이 우선 탐색이라고도 불린다. 스택 자료 구조 기반이고, LIFO특성을 이용하여 깊이 우선으로 탐색할 수 있고, 재귀 함수를 구현할 수 있다. 구현시 방문한 노드를 기록하는 배열 또는 집합을 이용하여 중복 방문을 방지하고, 그래프 알고리즘에 활용할 수 있다. 구현은 간단하지만 메모리 사용량이 많고, 깊이 우선으로 탐색하기 떄문에 너비 우선 탐색이 필요한 경우에 적합하지 않다.
Heap
min-heap
max-heap