Computer Science/DataStructure, Algorithm13 흐름도( 플로우 차트 ) 조건문 반복문 함수 호출과 실행Example 2024. 11. 14. 정렬 내가 그냥 정렬 해본거 그대로 따라할필요는 없고keyPoint들만 집중적으로 해야할듯 단순(구현 간단)하지만 비효율적인 방법 : 삽입, 선택, 버블 정렬 복잡하지만 효율적인 방법 : 퀵, 힙, 병합 정렬 삽입정렬( 기존에 정렬된 모임 )에서 ( 새로운 원소 )의 자리가 잡힐때까지 ( 모든 원소들 )과 비교 병합 정렬2개의 정렬된 리스트의 처음값들을 비교, 더 작은 값을 새로운 리스트(sorted)로 옮긴다.2개의 리스트중 하나가 끝날 때까지 위 과정을 되풀이한다. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다. 삽입 정렬( insertion sort )이미 정렬된 부분배열의 각 원소들과 모두 비교2번째 자료부터 시작, 왼쪽.. 2024. 10. 7. 해시 테이블 시간복잡도 자료구조접근탐색삽입삭제해시 테이블O(1)O(1)O(1)O(1)HashMap해시테이블과 같지 않을까?HashSet 해시테이블 - 삽입, 삭제 : O(1)key의 해시값을 배열의 크기로 나눠 index를 얻고key.hashCode() % SIZE;해당index의 LinkedList에 삽입,삭제 LinkedList의 삽입,삭제는 O(1) 이므로 해시테이블 - 접근 : O(1)key의 해시값으로 index얻고, 해당 index의 LinkedList에서 접근 LinkedList의 접근은 O(n) 이지만원소가 배열의 각 인덱스마다 LinkedList에 흩어져 있으므로 O(1) 실제로 (배열의 크기)와 (원소 개수)를 가지고 적절히 비교해서배열의 크기를 늘려주는 작업을 해준다.if (size >= table.size.. 2024. 7. 22. 자료구조에서의 시간복잡도( 연결리스트, 배열 ) 자료구조접근탐색삽입삭제배열O(1)O(n)O(n)O(n)이중 연결 리스트O(n)O(n)O(1)O(1)스택이중 연결리스트와 동일( 연결리스트로 구현 가능 )큐연결 리스트 - 삽입, 삭제 : O(1)클래스LinkedList 는head(맨 앞에 있는 노드)를 필드로 갖는다. head를 이용하면 삽입,삭제가 원소 수와 상관없이 이루어진다.삭제head = head.next;삽입newHead.next = head;head = newHead; 연결 리스트 - 접근 : O(n)클래스LinkedList는 head(맨 앞에 있는 노드)만을 필드로 갖고, 각 노드는 data와 다음노드를 가르키는 포인터(next) 만을 필드로 갖는다. head부터 시작해서 next값을 통해, 해당 index까지 이동해야함Node01 curre.. 2024. 7. 22. 시간 복잡도, 빅오 표기법, 공간 복잡도 시간 복잡도(Time Complexity)입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지를 나타내는 지표빅오 표기법(Big-O notation)수치가 작을수록 효율적인 알고리즘표기법시간복잡도설명예시O(1)상수 시간입력 크기와 상관없이 일정한 실행 시간배열에서 index 조회O(logn)로그 시간입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가이진탐색 알고리즘O(n)선형 시간입력 크기와 비례하는 실행 시간선형탐색 알고리즘 공간 복잡도(Space Complexity)알고리즘이 실행될 때 필요한 메모리 공간의 양, 일반적으로 메모리 사용량이 적을수록 더 효율적인 알고리즘 2024. 7. 20. 해시 테이블(Hash Table) 해시 테이블(Hash Table) key-value 쌍을 저장하는 자료구조 매우 빠른 검색데이터베이스 인덱싱, 캐시 구현, 집합(Set) 자료구조 등 다양한 분야에서 사용됨 동작원리해싱(Hashing)데이터를 저장할 때, key에 해시 함수(Hash Function)를 적용하여 해시 값을 계산 이 해시 값은 데이터가 저장될 배열의 인덱스를 결정 해시 함수(Hash Function)해시 값을 출력하는 함수( 키를 입력받음 ) 동일한 키에 대해 항상 동일한 해시 값을 반환함 해시 값으로 데이터가 저장될 배열의 인덱스를 결정( 보통 배열의 크기( 해시테이블의 크기 )로 나눈 나머지를 사용하여 ) 충돌 해결(Collision Resolution)~ ~ 간단히 HashMap 만들때ArrayList로 아래와같이.. 2024. 6. 3. 이전 1 2 3 다음
