공부 !/Computer Science
-
[ 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..
-
[ Data Structure ] Stack 스택공부 !/Computer Science 2022. 4. 14. 01:06
Stack 스택은 어떤 자료구조인가 ! 선형 자료구조의 일종으로 나중에 들어온 원소가 먼저 나가는 LIFO(Last-In-First-Out) 특징을 가진다 가장 먼저 들어간 원소가 제일 아래 깔리고 그 위로 차곡차곡 쌓이기 때문에 호출시에는 가장 위에 있는 원소가 호출된다 ! 스택을 프링글스 통이라고 생각하면 이해가 쉽다 ^ㅁ^ 파이썬에서는 스택 자료구조를 따로 제공하지 않아 기본 클래스 list 를 통해 구현할 수 있다 장점 구조가 단순해서 구현이 쉽다 데이터의 삽입 / 삭제가 빠르다 단점 ( 일반적인 스택 구현시 ) 데이터 최대 갯수를 미리 정해야한다 파이썬의 경우 재귀함수는 1000번까지만 호출이 가능하다 저장 공간의 낭비가 발생할 수 있다 미리 최대 갯구 만큼 저장 공간을 확보해야한다 stack ..