CS (3) 썸네일형 리스트형 hash map # hash function # 충돌 hash collision hash map이란? - hash table 이라고도 한다. - key, value 형태로 저장하는 자료구조 - 하나의 key는 하나의 value에 맵핑 - key는 uniqueness를 보장 특징 - 삽입, 삭제, 갱신, 탐색이 '상수 시간'에 처리(된다는 장점이 있다. 데이터의 크기에 상관 없이) Big O 표기법으로 표현시 O(1) ( 데이터의 사이즈에 따라 결정된다면 O(n) ) - 내부 구현 배열(Array)로 구현 배열은 index를 통해서 삭제, 구현, 탐색이 상수 시간대로 처리가 가능 배열로 구현한다는 것은 index를 이용한다는 것 hash map은 key를 통해서 index에 접근. 어떻게? -> hash function hash function: key를 배열 크기 내의 index로 .. 컴퓨터의 음의 정수 표현 1 byte = 8 bit 다음과 같은 1byte 공간에서 맨 앞자리는 양수/정수 나타낸다 00000000 양수: 0 음수: 1 2의 표현 00000010 -2의 표현 1) 2를 이진수로 표현 00000010 2) 0 -> 1, 1-> 0으로 변경 11111101 3) +1 11111110 2)와 3)은 '2의 보수'를 구하는 과정 ( 2)만 하면 1의 보수를 구하는 것) -2 + 2 = 0이 되어야 하고 bit로 표현된 -2와 2를 더해보자 11111110 + 00000010 ------------------- 100000000 -> byte 단위를 넘어가는 맨 앞 1은 버려진다 -> 00000000 컴퓨터의에서의 음수 표현 방식: 2의 보수를 통해 음수를 표현 ** 이진법 음수의 절대값 구하기 ** .. ADT: 추상 자료형 ADT - Abstract Data Type 추상적으로 정의된 자료형 데이터를 추상화하여 논리적인 구조를 정의한 것 게임에서 캐릭터를 구현한다고 하면, 캐릭터의 동작, 속성들은 컴퓨터가 연산할 수 있는 자료형으로 정의되어야 한다. 현실에 존재하는 개념 등을 구현하기 위해 원하는 자료형으로 만든 것을 의미. Python으로 예를 들면 Python에서는 주로 Class를 통해 추상 자료형을 만든다. 예를 들어 '자동차' 라는 개념의 추상자료형을 만들고, 이 추상자료형의 속성으로 이름, 브랜드를 정의할 수 있다. class Car: def __init__(self, name, brand): self.name = name self.brand = brand def describe(self): print(f"이 차.. 이전 1 다음