728x90 반응형 알고리즘/자료구조4 자료구조 시간복잡도 정리(평균, 최악) 자료구조의 평균 시간 복잡도 자료구조 접근 탐색 삽입 삭제 배열 O(1) O(n) O(n) O(n) 스택 O(n) O(n) O(1) O(1) 큐 O(n) O(n) O(1) O(1) 이중 연결 리스트 O(n) O(n) O(1) O(1) 해시 테이블 O(1) O(1) O(1) O(1) 이진 탐색 트리 O(logn) O(logn) O(logn) O(logn) 자료구조 최악의 시간 복잡도 자료구조 접근 탐색 삽입 삭제 배열 O(1) O(n) O(n) O(n) 스택 O(n) O(n) O(1) O(1) 큐 O(n) O(n) O(1) O(1) 이중 연결 리스트 O(n) O(n) O(1) O(1) 해시 테이블 O(n) O(n) O(n) O(n) 이진 탐색 트리 O(n) O(n) O(n) O(n) 해시 테이블과 이진 탐.. 2023. 8. 28. 그리디 알고리즘 그리디 알고리즘이란? 그리디 알고리즘은 보통 탐욕법이라고 한다. 말 그대로 문제를 해결할 때 현재 경우만 고려해서 최적의 상황을 선택하는 방법이다. 그리디 알고리즘 성립 조건 2가지 하지만 당연하게도 항상 사용할 수 있는 방법은 아니기 때문에 아래의 2가지 조건이 성립된다면 그리디 알고리즘을 기계적으로 적용할 수 있다. 1. 현재의 최적의 선택이 다음 선택에 영향을 미치지 않는다. 2. 현재의 선택이 최종 선택의 최적 해결 방법에 포함된다. 그리디 알고리즘 문제를 해결하는 방법 1. 현재 상태에서의 최적의 해답을 선택한다. 2. 선택된 해가 문제의 조건을 만족하는지 검사한다. 3. 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복한다. 그리디 알고리즘 예시 일반적인.. 2023. 8. 28. 자료구조 - 연결 리스트 연결 리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 메모리에 곳곳에 흩어진 연결된 데이터를 노드라고 부르고, 각 노드는 다음 노드의 메모리 주소도 포함한다. 이를 링크라고 한다. 노드와 연결리스트를 직접 코드로 구현해봤다. 여기서 length는 노드의 개수이고, head는 첫 노드의 주소이다. class Node { next = null; constructor(data) { this.data = data; } } class LinkedList { length = 0; head = null; } 데이터를 추가, 검색, 삭제하는 메소드도 추가로 구현해보았다. class Node { next = null; constructor(data) { this.data = data; } } class.. 2023. 7. 7. 자료구조 - 배열 1. 읽기 1단계로 배열에서 값을 찾을 수 있다. 2. 검색 값이 어떤 인덱스에 있는지 찾는 것이 검색이다. 선형 검색(한 번에 한 셀씩 확인하는 방법)의 경우 N개의 셀로 이루어진 배열은 최대 N 단계가 소요된다. 3. 삽입 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다. 배열을 할당할 때 항상 배열의 크기를 기록하기 때문이다. 맨 뒤에 데이터를 삽입하는 경우 => 1단계 그 외(N개의 원소 전부 이동 + 실제 삽입 단계) => N + 1 단계 4. 삭제 최대 N단계(삭제 + 데이터 이동) 질문이나 잘못된 점은 댓글로 남겨주세요 :)💖 2023. 7. 5. 이전 1 다음 728x90 반응형
