카테고리 없음
[인프런 수강일기#2] 기출로 대비하는 개발자 전공면접 [CS 완전정복]
ヽ(°ᴥ°)ﾉ
2024. 1. 6. 19:52
먼저 1주차에는 "자료구조"를 배우고, 예상 질문과 답변을 작성해보고 서로 피드백하는 시간을 가졌습니다!!
크게 아래 개념들을 복습했습니다
Array, Dynamic Array, Linked List
| 연산 | Array | Linked List |
| 크기 | 고정적 (메모리 낭비 or overhead) |
가변적 (필요한만큼 메모리 할당) |
| 메모리 저장 방식 | 연속적 | 메모리상에서 불연속 (다음 원소의 메모리 주소값을 저장해 논리적 연속성 유지) |
| 조회 | O(1) | O(n) |
| 삽입, 삭제 | O(n) | O(1) ( 다음주소를 가르키는 부분만 다른 주소 값으로 변경하면 되기 때문에 O(1)이지만, 실질적으로 추가/삭제를 하려는 index까지 도달하는데 O(n)O(n)의 시간이 걸리기 때문에 O(n)으로 볼 수 있다 ) |
| 언제 사용? | - 조회 자주 해야할 때 - Array 선언 당시 데이터 개수 알고 있을때 - 데이터를 반복문을 통해 빠르게 순회할때 - 메모리를 적게 쓰는게 중요할때 ( Linked List보다 메모리 적게 사용) |
- 삽입, 삭제 빈번할 때 - 데이터 크기 가변적일 때 - 조회 작업 많이 없을 때 |
Queue, Stack, Priority Queue
Binary Search Tree, Hash Table, collision
- Direct-address
- 불필요한 공간 낭비
- key가 다양한 자료형을 담을 수 없게됨
- Hash table
- Hash function
- key를 이용해 hash값을 만들어냄
- collision을 최소화하는 방향으로 설계해야함
- 시간 복잡도
- 저장, 삭제, 검색 O(1)이지만 collision으로 인하여 최악의 경우 O(n)이 될 수 있음
- 장점
- 많은 양의 데이터 빠르게 탐색
- 적은 자원으로 많은 양의 데이터 효율적 관리
- 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리 가능
- Hash function
- Collision 충돌
- 서로 다른 key의 해시값이 똑같을 때 발생 (= 해시값 중복)
- 해결방법
- seperate chaining
- open addressing
스터디 후기
어느정도 자료구조를 알고 있다고 생각했는데, 생각보다 질문을 딱 들었을때 바로 대답할 수 있는 질문이 거의 없어서 제대로 더 공부하고 이해해야겠다는 생각이 들었습니다.
스터디원들의 예상 질문이 총 17개가 모였고, 그 질문들과 답변들을 읽는 시간을 가졌습니다.
질문들중에는 실제 스터디원분들이 면접에서 받은 질문도 있어서 큰 도움이 됐습니다 그리고 실제로 면접에 많이 나오는 질문들이구나,,를 실감하게 되는 시간이었습니다..!!
그리고 강의에 없는 추가 개념들도 같이 공유해볼 수 있어서 좋았어요
답변을 달고 같이 얘기하며 느낀점은, 확실히 단순히 글로 답변을 적는 것보다 읽으면서 문맥을 다듬으면서 적어보는게 큰 도움이 된다는 것이었습니다!! 어쨋든 실제 면접에서 대답할 답변들이기 때문에 읽어보며 준비하는 연습이 필요하다고 느꼈습니다 ㅎㅎ
이상 자료구조 스터디 후기였습니다
위 내용은 아래 강의를 듣고 작성한 내용입니다