공부 !
-
[ Algorithm ] Sorting Algorithm 정렬 알고리즘공부 !/Computer Science 2022. 4. 21. 21:05
Sorting Alogrithm 정렬알고리즘이란 뭘까 ? 섞여 있는 여러 데이터를 순서대로 정렬하여 나열하는 알고리즘이다 시간복잡도에 따라 성능이 좌우되며 성능이 좋을수록 구현이 복잡하다 이 포스팅에서는 비교 방식 알고리즘을 소개한다 ! ( Non-comparisons github repo 게시 ! ) 정렬의 종류 O(n²) 의 시간복잡도 ( 정렬할 자료의 수가 늘어나면 제곱에 비례하여 증가 ) 버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) O(nlogn) 의 시간복잡도 병합 정렬 (Merge Sort) 퀵 정렬 (Quick Sort) 버블정렬 인접한 두 수를 비교하며 정렬하는 방식이다 앞에서부터 비교하여 큰 수를 뒤로 보내고 가장 ..
-
[ Algorithm ] BitMask 비트마스크공부 !/Computer Science 2022. 4. 20. 21:55
비트마스크 알고리즘 문제를 풀다보면 비트마스크의 개념을 알고 있으면 도움이 될 때가 있다 ! 그렇다면 비트마스크는 무엇일까 ?! 컴퓨터의 최소 연산 단위는 bit 이다 내부적으로 모든 자료를 이진수로 표현한다 bit 는 이진수를 나타내기 위해 0과 1로 이루어져 있고 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라 한다 비트연산자 비트연산자에는 AND, OR, XOR, NOT, SHIFT 가 존재한다 AND (&) # 대응하는 두 비트가 모두 1일 때 1을 반환한다 1010 & 1111 = 1010 OR (|) # 대응하는 두 비트가 모두 1 또는 하나라도 1인 경우 1을 반환한다 1010 | 1111 = 1111 XOR (^) # 대응하는 두 비트가 서로 다르면 1을 반환한다 1010^111..
-
[ Data Structure ] Heap 힙 & 우선순위 큐공부 !/Computer Science 2022. 4. 14. 23:44
Heap 힙은 어떤 자료구조인가 ! 비선형 자료구조의 일종으로 최소값과 최대값을 빠르게 찾기 위한 이진트리 구조이다 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다 힙은 heapq 내장 모듈로 구현할 수 있고 우선순위 큐는 힙으로 구현이 가능하다 ! 최소 힙은 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙을 의미하고 최대 힙은 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙을 의미한다 힙은 완전이진트리의 성질을 갖고 1차원 배열로 표현이 가능하다 아래를 참고하면 root index 에 따라 chlid index 를 계산할 수 있다 root index = 0 left index = index * 2 + 1 right index = index * 2 + 2 ..
-
[ Data Structure ] Queue 큐공부 !/Computer Science 2022. 4. 14. 23:26
Queue 큐는 어떤 자료구조인가 ! 선형 자료구조의 일종으로 먼저 들어온 원소가 먼저 나가는 FIFO(First-In-First-Out) 특징을 가진다 한 끝에서 삽입과 삭제가 이뤄지는 스택과는 반대로 큐는 삽입과 삭제가 다른 끝에서 이루어진다 큐는 줄 서기 라고 생각하면 이해가 쉽다 ^ㅁ^ 파이썬에서는 기본 클래스 list 와 내장모듈 Queue를 통해 구현할 수 있다 하지만 리스트를 사용할 경우 추가의 복잡도는 O(1) 이며 삭제는 O(N) 이기 때문에 데이터 처리속도가 O(1)인 내장 모듈로 구현하는 것이 좋다 Queue 구현 queue 초기화 ( Queue 모듈 사용 예시 ) # 빈 큐 초기화 import queue q = queue.Queue() queue 원소 삽입 enqueue # appe..