오늘 배운 것
자료구조
컴퓨터가 데이터를 효율적으로 저장하고 관리하도록 돕는 형식
배열
연속적인 공간에 차례대로 데이터를 저장한다.
배열 선언
int[] a;
int a[];배열 생성(길이지정)
a = new int[5];배열 초기화
int[] b = new int[5]; // 모두 0이 들어가있다.배열 선언과 동시에 생성 및 초기화
int[] numbers = {10,20,30,40,50};
// 요소 (Element) : 10, 20, 30, 40 , 50
// 인덱스 (Index) : 0, 1, 2, 3, 4
// 접근: numbers[0], numbers[1], ...배열 리스트 (ArrayList)
동적 배열 기반의 리스트로, 크기가 자동으로 조절된다.
ArrayList<Integer> arr = new ArrayList<>();
값 추가
arr.add(2);값 접근
arr.get(2) // 해당 index의 요소를 반환값 제거
arr.remove(1); // 해당 index의 요소를 삭제 한다. 연결 리스트 (LinkedList)
이중 연결 리스트 (Doubly Linked List) 기반의 리스트로, 요소가 노드에 저장된다.
LinkedList<Integer> arr = new LinkedList<>();
- previous, next로 이전, 이후의 노드를 알 수 있다.
- 특정 Node가 빠지면, 이전 노드에게 next 노드를 알려주고, 자신은 NULL로 해주면 된다.
스택 (Stack)
후입선출 (Last-In-First-Out, LIFO) 방식의 자료구조
Stack<Integer> S = new Stack<>();
push()와pop()으로 요소를 추가 및 제거할 수 있다.
큐 (Queue)
- 데이터가 순차적으로 처리되는 선형 자료 구조
- 선입선출 (First-In-First-Out, FIFO) 방식의 자료구조
- 데이터의 삽입과 삭제가 한쪽에서 이뤄진다.
Queue<Integer> Q = new LinkedList<>();
Enqueue와Dequeue가 있다.
덱 (Deque)
Double-Ended Queue는 Queue 인터페이스의 확장으로, 양쪽 끝에서 삽입과 삭제가 가능한 선형 자료 구조이다. 양방향 큐라고도 불리며, Queue와 Stack의 기능을 모두 포함한다.
Deque<Integer> DQ = new LinkedList<>();
해시 (Hash)
- Key와 Value가 쌍을 이루는 자료구조
- 해시 함수를 통해 고정길이 key 생성
- 길이가 고정되며, 비가역성(한 번 바꾸면 복원이 불가능)을 갖는다.
- 저장 또는 검색 등에서 자주 활용되는 자료구조
해시 테이블
- 해싱을 통한 원소들의 저장공간
- 키와 값을 함께 저장해 둔 데이터 구조
- 해싱 : 해시 함수를 통해 원소의 위치를 계산
- 크기가 s인 해시테이블을 T[0... s-1] 이라고 할 때, 원소 x에 대한 모든 값 h(x)는 {0,...s-1} 중 하나
- 해시 테이블의 각 엔트리를 버킷이라 하고, 버킷에는 1개 이상의 슬롯으로 구성
- 버킷 : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
- 슬롯 : 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러 개의 슬롯이 있다.
- 원소는 하나의 슬롯에 저장
해시 충돌
서로 다른 두 원소 x,y의 해시 값이 h(x) = h(y)이면 충돌이 발생한다.
해결 방법
- chaining : 충돌이 일어나면 원소들을 연결리스트로 연결한다.
- linear open addressing : 충돌이 일어나면 다음 빈 주소로 가서 저장한다.
- rehasing : 여러 해시 함수를 사용한다.
맵 (Map)
- 자바 컬렉션 프레임워크에서 키(key)와 값(value) 쌍을 저장하는 자료구조를 정의하는 인터페이스
- 각 키가 고유해야 하며, 하나의 키는 오직 하나의 값과 매핑된다.
- 값(value)는 중복될 수 있다.
- 순서를 유지하지 않는다.
- key로 value를 얻어낸다.
해시 맵 (HashMap)
가장 많이 사용되는 Map 구현체로, 해시 테이블을 기반으로 하여 키-값 쌍을 저장한다.
- 자바는
Separate Chaining을 사용하여 충돌을 방지한다.
HashMap<K,V> map = new HashMap<>();
해시 셋 (HashSet)
Set 인터페이스의 구현체로, 객체 그 자체를 저장한다. (객체가 key값이 되고, value는 더미객체를 사용한다.) 중복 허용하지 않는다. (hashCode(), equal() 메서드를 이용하여 중복체크)
오늘 유익했던 것
오늘 자료구조 수업을 했는데 엄청 유용했던 것 같다 ! 자바로 알고리즘을 풀다가 파이썬으로 갈아탄 이유 중 하나가 자료구조가 복잡하다? 뭐 이렇게 종류가 많아? 약간 이런 느낌 + 다른 분들의 풀이를 볼 때도 나랑은 너무 다른 자료구조를 쓰셔서 이해하는 데에도 조금 어려움이 있었기 때문이었는데, 오늘 강의를 듣고 아!! 하는 부분들이 너무 많았다. 우선 아주 큰 의문점이었던 .. ㅎ
List<Integer> list = new ArrayList<>(); 를
왜 ArrayList<Integer> list = new ArrayList<>();로 안 쓰냐 !!! 를 알게 되었다.
저걸 왜 궁금해 해? 라고 할 수 있지만.. 흑흑 전 이게 이해가 안됐답니다 :b 호호호 아무튼 이게 이해가 된다 !
배울 때 Collection을 구현하고, List를 구현하고 등등 이 관계를 아니까 훨씬 자료구조를 이해하기 쉬웠다. interface라는 것도 동시에 더 잘 이해된 것 같아서 좋았다. 참.. 이해되는 맛이란 좋구나..
바로 적용이 되면 좋겠지만,,, 열심히 더 이해하고 연습해서 알고리즘 문제 풀 때 이젠 더 다양한 자료구조를 이용해서 그들의 함수 덕 좀 봐야겠구나 ㅎㅎ ..
팀 활동 후기
오늘 첫 RBF를 진행하였다. 팀 활동은 소회의실 들어가서 그 첫 인사 후 진행시킬 때가 제일 뻘쭘한 것 같다. 여느때와 같이 MC가 된 것 같다 ㅋㅋㅋ 자~ 그럼 오늘도 해볼까요~? 다들 어색하겠지? 나만 그런 거 아니겠지? 하하
아무튼 RBF도 걱정했는데, 걱정했던 것보다 순조롭게 잘 진행이 되었다. 의견을 나누고 생각을 정리하는 과정에서 내가 생각하지 못한 질문도 듣고, 그 질문에 대해서 고민해보았다. 또, 알고 있었던 것 같은데? 하는 개념도 말로 설명하려니 어랏 하면서 헷갈리는 부분도 있었다. 그런 걸 계속 얘기하고, 또 이해 안 되는 것들을 다시 질문하면서 많이 도움이 된 것 같다 ! RBF도 잘 활용해서 한 주 마무리 + 복습을 잘 해봐야겠다 ! :)
아 그리고, 사실 저 위에 List<Integer> list = new ArrayList<>(); 이거.. TF님이 설명 달아주셨을 땐 이해됐는데 또 생각해보니까 또 이해가 안돼서 팀원들한테 다시 물어봤다..ㅎ 잠깐의 정적이 흐르다가 설명을 잘해주셨는데 덕분에 진짜 너무 이해가 됐다 !!!! 감사합니다 호호
느낀점
와.. 2주 끝난 거라구? for real..? 이 9-6 앉아있는 게 결코 쉽진 않구나.. ㅎ 6개월.. 대단한 시간이다. 그래도 어찌보면 벌써 2주나 했네 ! 2주동안 포기하지 않고 의자에 붙어 한 번도 지각하지 않고 수업에 잘 참여한 날 칭찬한다 ㅋ 막이래 암튼 이제 자료구조 들어가고 곧 DB, 네트워크 들어갈 텐데 정말... 자신 없는 부분이다. 수업 더 열심히 들고 복습도 잘 해야겠어요 ㅎ 파이팅 파이팅이다 !!
아.. 맞다 그리고 저.. 금요일을 사랑하게 됐어요. 응응. 이건 엄청난 날이야.. 그렇다고 약속이 있진 않지만 .. 그냥 좋아.. 너무.. 너만 기다릴게
아 또 그리고 오늘 강사님이 수업 초반에 학생들 자기소개도 다시 다 보시고 블로그나 깃헙도 들어가보셨다고 하셨다. 그러다가 "블로그를 되게 구성을 해서 꾸준히 쓰고 계신 분이 계시더라구요~" 이래서 '우왕.. 대단하다.' 이 생각하며 듣고 있었는데 강사님이 그 분 취미가 사진찍기라고 하시는 것이다 !! 세상에.. 난가..? 이러면서 갑자기 숨길 수 없는 미소 발사 ㅋㅋㅋㅋㅋㅎㅋㅎ 좋게 봐주셔서 너무 감사할 따름이다.. 난 이제 구독자(?) 생겼으니 책임감을 가지고 더 열심히 공부하고 기록해야겠다.
한 주동안 수업 듣느라 고생하였고 주말 잘 보내고 다음주도 파이팅해서 수업 잘 따라가야지 !! :)
