Computer Science/Algorithm, Data Structure
-
CS : Data Structure : ArrayList & LinkedListComputer Science/Algorithm, Data Structure 2021. 4. 6. 16:55
ArrayList 1. 일반적인 배열과 유사하다. 중복을 허용하고, 순서를 유지하며, 인덱스로 원소를 관리한다. 2. 배열은 선언 시 크기가 고정되지만, ArrayList는 선언 후 추가, 삭제가 가능하다. 3. 단, ArrayList에 데이터를 추가할 경우, 추가할 때마다 동적으로 크기가 증가하는 것이 아니라, 용량이 꽉 찼을 경우(= default_capacity를 초과할 경우) 더 큰 용량의 배열을 만들어 옮기는 작업을 한다. 4. 초기 용량을 예상하여, default_capacity를 조절하는 것이 좋다. LinkedList 1. 크기를 변경할 수 없고, 데이터의 추가, 삭제에 시간이 많이 걸린다는 일반적인 배열의 단점을 보완하기 위해 등장한 개념이다. 2. 다음 원소의 메모리 주소만 연결시켜 주..
-
CS : Algorithm : DFS & BFSComputer Science/Algorithm, Data Structure 2021. 4. 1. 22:59
탐색 알고리즘 1. 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 2. 그래프 : 정점과 간선으로 구성된, 한정된 자료구조. 각각의 지점을 정점이라고 하고, 정점과 정점의 연결을 간선이라고 한다. 3. 그래프가 주어지고, 특정 정점과 다른 정점 간 이동이 가능한가? 또는 이동할 수 있다고 했을 때 해당 경로는 효율적인가? 등을 따질 때 사용되는 알고리즘이 탐색 알고리즘이다. DFS (깊이 우선 탐색) 1. 가장 직관적이고, 구현하기 쉬운 탐색 방법 2. 현재의 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점을 갈 수 있다면 그 정점에 가서 같은 행위를 반복한다. 갈 수 없다면, 이전 정점으로 돌아간다. 3. 같은 정점을 다시 방문하지 않도록 정점에 방문했다는 것을 표시해준..