모여서 각자 코딩/2019 동계 모각코
-
[2019 동계 모각코] 회고모여서 각자 코딩/2019 동계 모각코 2022. 3. 13. 00:10
저의 동계 모각코의 목표는 2학년 1학기에 전공 중 자료구조를 모각코 기간동안 공부하기로 한것입니다. 미리 공부함으로써 개강 후에 자료구조를 쉽게 받아들일 수 있도록 하기 위해서 였습니다. 선배의 도움을 받아 자료구조에서 중요한 부분들을 먼저 공부하고 어려운 부분을 이해하고자 하였습니다. 결과적으로 자료구조 중에서 연결리스트, 이중연결리스트, 스택 구현, 이진트리, 완전이진트리, 히프, 해쉬테이블에 대해서 공부했습니다. 우선 모각코 시작 때 세운 목표와 같이 자료구조 중에 중요하다고 생각하는 부분들은 다 공부하게 되어서 뿌듯했습니다. 이론을 이해한 뒤에 지난 자료구조 강의의 실습자료들을 해보면서 깊게 이해할 수 있었고 코드 작성시에 중요한 점들도 많이 알게 되었습니다. 모여서 공부를 함으로써 공부에 ..
-
[2019 동계 모각코] 6차시 - 결과모여서 각자 코딩/2019 동계 모각코 2022. 3. 13. 00:09
해시테이블 1. 자료구조 두가지 접근 패턴 1) 순차접근 : 연결리스트에 의해서 제공된다. : 한쪽 끝에서 시작해 각 원소를 하나씩 살펴보면서 목표에 도달하거나 다른 끝에 도달할 때까지 탐색을 진행한다. 2) 직접접근 : 배열에 의해서 제공된다. : 인덱스 i를 이용해서 직접 a[i]원소를 찾는다. : 하지만 원소의 인덱스에 대해서 알고있어야한다. 2. 해시테이블 원소의 인덱스에 대해 사전지식없이 직접 접근할 수 있게한다. 원소의 내용으로부터 원소의 인덱스를 계산하는 해시함수를 이용한다 해시(hash) : 원소들이 아무런 순서없이 마구 뒤섞여 있다는 의미 3. 개방주소법 해당원소가 해시값에 의해 인덱스된 슬롯에 항상 배치되지않고 테이블의 임의에 장소에서 끝날수 있다. 1) 선형조사 : 충돌 - 해당 ..
-
[2019 동계 모각코] 5차시 - 결과모여서 각자 코딩/2019 동계 모각코 2022. 3. 13. 00:08
완전이진트리와 히프 알고리즘 1. 완전이진트리 이해 완전이진트리란 이진트리에서 리프가 왼쪽부터 순서대로 채워지는 것이다. 부모의 인덱스가 i 라면 자식의 인덱스는 2i+1, 2i+2가 된다. 2. 히프 알고리즘 완전이진트리에서 리프-루트로 가는 경로가 오름차순 또는 내림차순으로 되어있는 것이다. 맥스히프 : 오름차순으로 되어있는 완전이진트리 히프화 : 히프 특성을 만족하도록 원소들을 재배열 1) 히프화메소드 - Max_heapify() : 부모와 자식간의 크기를 비교하여 원소를 배열하고 재귀를 통해 부모에서 리프까지 재배열한다. 2) 삽입메소드 - push(), pushSort() : 트리의 맨마지막에 삽입하고 부모와 비교하며 리프-루트경로로 원소를 재배열한다. push(int x) - 크리를..
-
[2019 동계 모각코] 4차시 - 결과모여서 각자 코딩/2019 동계 모각코 2022. 3. 13. 00:06
이진트리 이진트리 구조를 이해하고 구현하는 것을 목표로 함 이진트리를 구현하는 BinaryTree클래스를 작성했고 이 클래스는 트리 삽입 메소드, 트리 탐색 메소드, 후위순환 메소드, 트리 깊이 계산 메소드로 구성된다. 1) 필드 변수와 생성자 left와 right는 key를 기준으로 왼쪽, 오른쪽으로의 연결을 나타낸다. 2) 삽입메소드 : BinaryTree형의 포인터를 만들어 삽입할 자리에 이동해 삽입한다. : key의 값보다 작은 수는 왼쪽에 큰수는 오른쪽에 삽입한다. 트리는 key값을 기준으로 왼쪽과 오른쪽으로 나누어져 경우를 나누는게 중요한 것을 느꼈다. 3) 탐색메소드 : 탐색할 값을 key값과 비교하며 포인터를 이동시켜 찾는다. 4) 후위순회 메소드 : 재귀를 이용하여 트리를 ..
-
[2019 동계 모각코] 3차시 - 결과모여서 각자 코딩/2019 동계 모각코 2022. 3. 13. 00:03
연결리스트를 이용한 stak구조 구현 & 응용 연결리스트를 이용하여 stack구조를 구현한 클래스를 작성하고 그 클래스를 이용하여 사칙연산으로 이루어진 문자열을 입력받았을 때 괄호 쌍들의 인덱스 값을 반환하고 괄호쓰기가 맞는지 틀린지 결정하는 클래스를 작성한다. stack을 구현한 클래스는 연결리스트에 노드를 삽입하는 메소드와 노드를 삭제하고 값을 반환하는 메소드로 이루어진다. 1) 삽입메소드 - add() : 제일 최근에 삽입된 노드를 head로 하여 삽입한다. 2) 삭제메소드 - pop() : 제일 마지막에 삽입된 노드를 삭제하고 삭제한 노드의 값을 반환한다. 사칙연산에서 괄호의 인덱스값과 괄호쓰기가 맞는지 결정하기 위한 클래스 : 사칙연산을 입력받아 글자 하나씩 배열에 저장하고 반복문을 통해 괄호의..