728x90 반응형 알고리즘16 자료구조 시간복잡도 정리(평균, 최악) 자료구조의 평균 시간 복잡도 자료구조 접근 탐색 삽입 삭제 배열 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. [프로그래머스/더 맵게] - JS로 힙 직접 구현해보기 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시간 복잡도 힙을 사용하지 않고, 코드를 구현했었는데, 효율성까지 통과해야하는 문제였기 때문에 힙을 사용해서 구현을 해야만 효율성을 모두 통과할 수 있었다. 처음에는 힙을 사용하지 않고 배열을 매번 정렬했었기에 nlogn의 시간복잡도가 걸렸지만, 힙을 사용함으로써 logn으로 시간복잡도를 줄일 수 있었다. 알고리즘 설계 처음 작성한 코드는 아래와 같다. function solution(scoville, K) { let answer = 0; // 섞어야 하는 최소 횟수 // 모든 값이 K 이상인지 확.. 2023. 8. 8. 자료구조 - 연결 리스트 연결 리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 메모리에 곳곳에 흩어진 연결된 데이터를 노드라고 부르고, 각 노드는 다음 노드의 메모리 주소도 포함한다. 이를 링크라고 한다. 노드와 연결리스트를 직접 코드로 구현해봤다. 여기서 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. [백준/연결리스트/JS] 에디터 문제 설명 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 소문자만, 600000글자까지 커서 위치: 문장 맨 앞, 문장 맨 뒤, 문자 사이 맨 처음에 커서는 맨 뒤에 위치 L: 왼쪽으로 한칸 D: 오른쪽으로 한칸 B: 왼쪽에 있는 문자 삭제 P$: $를 커서 왼쪽에 추가 입력값: 문자열, 명령어 개수, 명령어들 출력값: 입력값에 모든 명령어 수행한 후의 결과값 시간 복잡도 arr.splice() 삭제하려는 요소의 위치, 배열 개수에 따라서 시간 복잡도가 달라진다. 삭제하려는 요소가 배열의 맨 끝에 위치할 경우.. 2023. 7. 6. 이전 1 2 3 4 다음 728x90 반응형
