티스토리

To the big data of media

검색하기

블로그 홈

To the big data of media

coding789.tistory.com/m

Mecodata 님의 블로그입니다.

구독자: 2

방명록 방문하기

주요 글 목록

Map - Python의 딕셔너리({key:value})와 같은 Java의 자료구조 - 제너릭()을 이용하여 key와 value의 타입을 지정할 때 primitive type이 아닌 wrapper class로 정의 주요 메서드 - clear() = Map 원소들 모두 지움 (초기화) - isEmpty() = Map에 원소가 한 개라도 있는지 조회 => 있으면 true, 없으면 false - size() = 원소의 개수 조회 - containsKey() = 해당 Key를 가지는 원소가 있는지 조회 - containsValue() = 해당 Value를 가지는 원소가 있는지 조회 - get(key) = 해당 key와 매핑되는 value 반환 - put(key, value) = 해당 key:value 원소 추가 - r.. 공감수 0 댓글수 0 2023. 2. 16.
Tree - 노드 간 부모-자식 관계와 루트 노드를 가지는 그래프 => 계층 관계를 표현하기에 적합 ※ 그래프 = 노드와 노드 간을 연결하는 간선(branch)으로 구성된 자료구조 - 자식 노드는 단 하나의 부모 노드만을 가질 수 있고 부모 노드는 여러 개의 자식 노드를 가질 수 있음 - 비선형 구조, 방향성 존재, 비순환 그래프 - 루트 노드(맨 위), 내부 노드(중간), 리프 노드(맨 밑, 자식이 없는 노드) 이진 트리(Binary Tree) - 자식 노드의 개수가 2개 이하인 트리 - 탐색 속도 = O(logN) - 이진 탐색 트리(BST, Binary Search Tree) = 이진 탐색 + LinkedList가 결합된 구조로 왼쪽 자식 노드에는 부모 노드 보다 작은 값이 오른쪽 자식 노드에는 부모 노드 .. 공감수 0 댓글수 0 2023. 2. 2.
HashMap과 HashTable Hash - 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값 HashMap과 HashTable 비교 HashMap HashTable key와 value null 허용 O X Thread-safe X O Enumeration X O 멀티 스레드 부적합(비동기) 적합(동기화 지원) 해시 충돌 상대적으로 적게 발생 (보조 해시 함수 사용) 상대적으로 많이 발생 (보조 해시 함수 사용 X) key 중복 X value 중복 O 저장 방식 key:value 형태로 저장 (Map 인터페이스를 상속받아 구현) 탐색 속도 O(1)로 빠름 => 해시 함수에 키를 넣으면 값이 저장된 해시 값(인덱스)를 돌려주기 때문 정의 키(key)에 대한 해시 값을 사용하여 값(value)을 저장하는 자료구조 공감수 0 댓글수 0 2023. 2. 2.
ArrayList vs LinkedList LinkedList - 노드를 포인터로 서로 연결하여 만든 리스트 - 데이터의 수정, 삭제가 빈번할 경우 빠른 속도를 보장함 => O(1)의 속도 - 인덱스 X => 조회 시 첫번째 노드부터 순차적으로 탐색 => O(N)의 속도 ※ ArrayList의 경우 반대로 수정과 삭제 = O(N)의 속도지만 조회 = O(1)의 속도 => 조회는 인덱스를 이용하여 빠르지만 수정/삭제의 경우 해당 명령 수행 후 뒷 순서 원소들의 인덱스를 조정하기 때문 ArrayList와 비교 ArrayList LinkedList 크기 제한 O X 접근 방식 무작위(랜덤) 접근 가능 (인덱스 O) 순차 접근만 가능 (인덱스 X) 조회 속도 O(1) O(N) 수정/삭제 속도 O(N) O(1) 조회 시에는 ArrayList를 수정/삭제 .. 공감수 0 댓글수 0 2023. 2. 2.
탐색 알고리즘 (Search Algorithm) 선형 탐색(Linear Search) - 리스트 안에 있는 데이터들을 맨 앞이나 맨 뒤에서부터 순서대로 탐색하는 알고리즘 - 시간 복잡도 O(N) 이진 탐색(Binary Search) - 리스트 안에 있는 데이터들을 중간 지점을 기준으로 데이터를 반씩 나눠서 탐색하는 알고리즘 - 원하는 값을 찾을 때까지 반을 나눈 후 탐색하는 과정을 반복함 - 시간 복잡도 O(logN) 이진 탐색 트리(BST, Binary Search Tree) - 각 노드가 최대 두개의 자식을 갖는 탐색 트리이며 왼쪽 자식 트리에는 부모의 키 보다 작은 값을 오른쪽 자식 트리에는 부모의 키 보다 큰 값을 포함하는 속성을 가짐 - 시간 복잡도 O(H) (H = 트리의 높이) 공감수 0 댓글수 0 2023. 1. 24.
itertools (순열과 조합) itertools - 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리 - 코테에서 유용한 메소드는 순열 함수인 permutations과 조합 함수인 combinations - import itertools - 시간복잡도 = O(N!) 주요 메서드 - 주요 메서드 모두 리스트를 이용하며 결과값도 리스트로 반환함 - permutations(리스트, 숫자) = 해당 리스트에서 지정한 숫자만큼 데이터를 뽑아(중복 X) 일렬로 나열하는 모든 경우를 반환 (순열) - combinations(리스트, 숫자) = 해당 리스트에서 지정한 숫자만큼 데이터를 뽑아(중복 X) 순서를 고려하지 않고 나열하는 모든 경우를 반환 (조합) - product(리스트, 숫자) = 데이터의 중복이 허용되는 permu.. 공감수 0 댓글수 0 2022. 10. 31.
bisect bisect - 파이썬에서 이진 탐색을 쉽게 구현할 수 있도록 해주는 라이브러리 - 정렬된 리스트에서 특정 범위에 속하는 원소 개수를 구할 때 유용함 (bisect는 숫자 데이터에서만 적용 가능!!) - 시간복잡도 = O(logN) import bisect - bisect_left(리스트, 숫자 데이터) = 해당 리스트에서 지정한 숫자 데이터가 들어갈 수 있는 인덱스의 최솟값 반환 => 오름차순으로 정렬된 리스트에서 해당 숫자 데이터보다 작은 데이터의 개수 - bisect_right(리스트, 숫자 데이터) = 해당 리스트에서 지정한 숫자 데이터가 들어갈 수 있는 인덱스의 최댓값 반환 => 오름차순으로 정렬된 리스트에서 해당 숫자 데이터보다 큰 숫자 데이터의 개수 ex) A=리스트, a, b= 서로 다른 .. 공감수 0 댓글수 0 2022. 10. 31.
정렬 알고리즘 선택 정렬 (Selection Sort) - 크기가 가장 작은 데이터를 맨 앞 순서의 원소와 서로 교체하고 그 다음으로 작은 데이터를 두 번째 순서의 원소와 교체하는 방식의 정렬 알고리즘 - 시간 복잡도 O(N^2) 삽입 정렬 (Insertion Sort) - 맨 앞의 요소는 정렬이 됐다는 가정하에 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 - 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있음 - 시간 복잡도 O(N) => 최악의 경우 O(N^2) 퀵 정렬 (Quick Sort) - 정렬의 기준이 되는 피벗(Pivot)을 지정한 후 피벗을 기준으로 왼쪽에서는 피벗보다 크기가 큰 원소들을, 오른쪽에는 피벗보다 크기가 작은 원.. 공감수 0 댓글수 0 2022. 10. 5.
Hash - 파이썬의 딕셔너리와 유사 - 데이터를 입력하는 순서 상관 X - key:value 형식으로 데이터 저장 - value는 중복이 가능하지만 key는 중복 X - 저장한 데이터 수정 가능 - 모든 데이터 타입으로 접근 가능 - list에 비해 빠른 시간 복잡도 (list=O(N), Hash(Dict)=O(1)) - string을 기반으로 데이터를 기록하고 관리해야 할 때 주로 사용 (string 타입의 key) 해쉬 함수(Hash Function) - 임의의 길이를 갖는 임의의 데이터(key)를 고정된 길이의 데이터(해시 값)로 매핑하는 함수 - hash() = 해쉬값 설정 (해쉬값은 랜덤으로 부여됨, 중복 가능성 존재 - 중복 발생 = 해쉬 충돌 발생) ※ Java의 경우에는 hashCode() ※ 만.. 공감수 0 댓글수 0 2022. 9. 10.
Greedy Algorithm (그리디 알고리즘) - 나중에 미칠 영향에 대해서는 고려하지 않은 채 현재의 상황에서 당장 좋은 것만 고르는 알고리즘 - 다른 알고리즘에 비하여 속도가 빠른 편이지만 최적해를 찾을 수 없는 가능성이 높음 ex) 가장 큰 순서대로, 가장 작은 순서대로 공감수 0 댓글수 0 2022. 8. 31.
Page Replacement Algorithm (페이지 교체 알고리즘) 정의 - 빈 프레임이 없을 경우 희생(삭제) 당할 프레임을 고르는 알고리즘 종류 - FIFO(First In First Out) 알고리즘 : 가장 먼저 들어온 페이지 교체 (Queue와 비슷) ※ Queue는 FIFO 알고리즘을 사용한 한 자료구조 - OPT(Optimal)알고리즘 : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체 - LRU(Least Recently Used)알고리즘 : 가장 오랫동안 사용되지 않은 페이지 교체 - LFU(Least Frequently Used)알고리즘 : 참조 횟수가 가장 작은 페이지 교체 - MFU(Most Frequently User)알고리즘 : 참조 횟수가 가장 많은 페이지 교체 - NUR(Not Used Recently) 알고리즘 : 최근에 사용하지 않은 페이.. 공감수 0 댓글수 0 2022. 8. 31.
Stack, Queue, deque Stack - 후입선출의 LIFO(Last In First Out) 구조 - 책이 쌓여있을때 맨 위에 책을 추가로 쌓는 것 = push(=append) - 책을 위에서 내려다 보았을 때 가장 위에 있는 책을 확인하는 것 = peek - 맨 위에 있는 책을 가져가는 것 = pop - Python은 리스트 스택으로 사용 가능하도록 구현됨 -스택의 대표적인 활용은 인터넷 창 이전 페이지, 다음 페이지 class Stack(li): push = li.append def peek(self): return self[:-1] s = Stack() s.push(1) s.push(2) s.push(3) print('my stack is : ', s) # my stack is : [1, 2, 3] print('제거 :',.. 공감수 0 댓글수 0 2022. 8. 17.
heapq 사용 이유 코테에서 주어진 변수의 범위가 적당할 경우에는 기본 자료형으로도 통과하지만 범위가 1~백만 정도로 커지면 처리 시간이 매우 길어져 효율성이 떨어지기 때문에 이를 해결하기 위해 heapq(힙)이라는 모듈을 사용 파이썬에서의 힙 - 파이썬에서 힙 모듈은 완전 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공 - 최소 힙은 원소들이 항상 오름차순으로 정렬되며 항상 최소힙의 인덱스 0번의 위치에는 최솟값 데이터가 위치 힙 함수 종류 import heapq - heappush(객체, 데이터) = 힙에 해당 데이터 추가 - heappop(객체) = 괄호안에 데이터를 입력하면 힙에서 해당 데이터 삭제 후 그 값을 출력 - heapify(리스트) = 리스트를 힙으로 변환 -.. 공감수 0 댓글수 0 2022. 7. 16.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.