김희성의 개발자 면접 cs 강의/ 스터디 자료형 변수란? 값을 저장할 때 사용하는 식별자 값의 이름과 저장위치의 쌍 저장위치 = 메모리 즉 변수는 값을 저장한 메모리 주소에 대응. 자료형 표현 범위 메모리 연산 속도 int -2,147,483,648 ~ 2,147,483,647 32bit( =4Byte) 가장 빠름 Long(int64) -9223372036854775808 ~ +9223372036854775807 64bit( =8Byte) int 대비 느림 float 정확도 낮음(유효자리수:7) 32bit( =4Byte) int 대비 느림 double 정확도 높음(유효자리수:16) 64bit( =8Byte) int 대비 느림 * 위 자료형 중 대부분 CPU에서는 int 형이 연산속도가 가장 빠르다. 시간..

김희성의 개발자 면접 cs 강의/ 스터디 Hash Collision (해시 충돌) 서로 다른 Key 값에 대해서 Hash 함수의 반환 값이 동일한 경우를 말한다. key의 값의 경우의 수는 무한하지만 메모리상 버킷사이즈는 줄일 수 밖에 없다. (Java에서 HashMap()의 initial Capacity는 16으로 정의되어있음) 그 때 버킷사이즈를 늘리기위해 리사이징하는 과정에서 해시 충돌 발생 연산 속도도 빠르며, 해시 충돌이 가능 한 발생하지 않아야 성능이 좋은 Hash 함수라 할 수 있다. Hash Collision (해시 충돌) 해결 방법 Open Addressing 해시 충돌이 발생한 경우 비어있는 버킷을 찾아서 저장한다. 해시 충돌이 발생한 경우, 탐색/접근의 시간 복잡도가 O(N) 으로 증..

김희성의 개발자 면접 cs 강의/ 스터디 Priority Queue 비선형 자료구조 Heap이라는 완전 이진 트리로 구현 FIFO Queue와 다르게 데이터 삽입 순서와 관계없이 우선순위가 가장 높은(낮은)데이터 먼저 꺼낸다. 우선순위 높은 데이터부터 꺼냄 : Max Heap(최대힙) (c++) 우선순위 낮은 데이터부터 꺼냄 : Min Heap (최소힙) (java, python) 시간복잡도 i번째 데이터에 접근(Access) : *NONE 데이터의 삽입 : O(logN) 우선순위가 가장 높은(낮은) 데이터에 접근 : O(1)/삭제:O(logN) 데이터가 계속 들어가고 나오는 상태에서 가장 큰 값이나 가장 작은 값을 빠르게 알고싶을 때 사용. import java.util.PriorityQueue; pu..

김희성의 개발자 면접 cs 강의/ 스터디 HashTable (HashMap , unordered_map(set)) java는 HashMap map: [key,value] 저장 / set : key만 저장 Map과 Set은 key가 중복되는 데이터는 저장 불가 비선형 자료구조 일정 크기의 배열(버킷) 생성 후 key값을 hash함수를 통해 배열의 index로 변환하여, 해당 index에 해당 key값과 value값 저장 시간 복잡도 i번째 데이터에 접근(Access) : NONE / *O(N) (순서라는게 없음) X라는 데이터(Key)가 있는지 탐색 : O(1) X라는 데이터(Key)에 접근(Access) : O(1) X라는 데이터(Key)의 삽입/삭제 : O(1) Dictionary는 HashMap 으로..

김희성의 개발자 면접 cs 강의/ 스터디 Queue 데이터가 연속적(논리적)으로 저장되어있는 선형 자료구조이다. (메모리상에서 연속적x) FIFO 자료구조 Enqueue (Add) : Queue에 데이터 넣음 Dequeue (Poll) : Queue에서 데이터 꺼냄 시간복잡도 i번째 데이터 접근 O(N) 맨 앞 데이터 접근/삭제 O(1) 맨 뒤 데이터 추가 O(1) x 라는 데이터 있는지 탐색 O(N) Deque ( Double Ended Queue) 한 방향이 아니라 양쪽 끝에서 데이터 추가하거나 꺼낼 수 있는 자료구조 FIFO 구조라고 할 수 없음 시간복잡도 i번째 데이터 접근 O(N) 맨 앞/뒤 데이터 접근/추가/삭제 O(1) x 라는 데이터 있는지 탐색 O(N) queue.addFirst() , ..

김희성 개발자 면접 CS강의/스터디 Array (배열) 배열은 메모리 상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조이다. 크기는 고정되어 변경될 수 없다. (데이터의 삽입/삭제 불가능. 배열의 사이즈 변경 안 됨) 시간 복잡도 i번째 데이터에 접근/변경 O(1)(Random Access) x라는 데이터 탐색 O(N) Dynamic Array(List, ArrayList, Vector) Dynamic Array는 메모리상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조. 크기가 동적으로 변경될 수 있으나 근본적으로 배열 기반으로 구현 여유공간 없으면 사이즈를 (2배 or 50%)씩 늘린다. 사이즈 늘리는 로직상 메모리 낭비 발생가능 리사이징 발생할 때마다 새로운 메모리 영역을 할당하고 데이터를..