수학과의 개발자 도전기

공부기간: 2021.09.06~10.15

총 34일 동안 공부했다.

목표: 

1. 정보처리기사 인강 완강하기

2. 기출풀기

3. 푼 문제 오답

4. 내용복습

5. 데일리 실기 다회독

6. 족보/파이널 모의고사

실행: 

1. 9월 26일에 완료 

2. 10월 8일 완료

3,4. 10월 11일 완료

5. 10월 12일 완료

6. 10월 15일 완료(10.12~10.15)

공부양으로는 인강 1회독, 개념 3회독, 기출 2회독, 데일리 실기 4회독, 약술형 1회독, 파이널 모의고사 35회 풀기 했다. 

개념은 3회독 부터는 중요한 부분 위주(sql,프로그래밍,보안,테스트,uml,sw 기초)로 정리하고 정리본을 봤다 

공부한 날짜: 2021.09.30

-이진트리: 모든 노드가 최대 2개의 자식을 가질 수 있는 트리

예시) 수식이진트리(수식을 트리 형태로 표현하여 계산하게 함), 이진 탐색 트리(아주 빠른 데이터 검색을 가능하게 함)

ㄴ 이진트리의 특징: 노드의 최대차수 2(가능한 값 0,1,2)

ㄴ 이진트리의 종류: 포화이진트리, 완전 이진트리,높이 균형 트리,완전 높이 균형 트리

-포화 이진트리: 모든 노드가 자식을 둘씩 가지고 있는 이진트리. 잎 노드들이 모두 같은 깊이에 존재한다는 특징을 가짐

-완전 이진트리: 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 것이 특징

-높이 균형 트리: 루트 녿를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진트리

-완전 높이 균형 트리: 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위트리의 높이가 같은 이진트리

-이진트리의 순회 :트리 내의 노드들 사이를 돌아다니는 것을 말함 

순회에는 전위순회,중위순회,후위순회가 있다 

1. 전위 순회: 루트 노드부터 잎 노드까지 아래 방향으로 방문하는 순회

(1) 루트 노드부터 시작해서 아래로 내려오면서

(2) 왼쪽 하위 트리를 방문하고 끝나면

(3) 오른쪽 하위트리 방문

2.중위 순회: 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문하는 순회

(1) 왼쪽 하위 트리부터 시작 : 가장 왼쪽의 '잎 노드'부터 시작한다는 말

(2) 루트

(3) 오른쪽 하위 트리 

노드-부모노드-형제노드 순서 

중위 순회가 쓰이는 예: 수식트리

3.하위 순회:

(1) 왼쪽 하위트리부터 시작

(2) 오른쪽 하위트리

(3) 루트노드 순서 

공부한 날짜: 2021.09.16

-트리는 나무를 닮은 자료구조이다.

-계층 데이터, 수식표현, 집합, 데이터 탐색에도 사용되는 활용도가 높은 자료구조 

-운영체제의 파일 시스템, xml의 dom(document object model),검색 엔진, 디비도 트리 자료구조에 기반해서 구현됨

-트리 용어

뿌리: 가장 위에 있는 노드 

가지: 루트와 잎 사이에 있는 모든 노드

잎: 가지 끝에 매달려 있는 노드 

관계: 부모,자식 관계가 있다 

경로(path) : 한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여있는 노드들의 순서 

길이(length) : 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수를 의미 

깊이(depth): 루트 노드에서 해당 노드까지의 경로 길이를 의미함 

레벨(level): 깊이가 같은 노드의 집합 

높이(height) : 가장 깊은 곳에 있는 잎 노드까지의 깊이 

차수(degree) : 자식 노드의 개수, 트리의 차수 = 가장 많은 자식노드를 가진 노드의 차수 

-트리 표현하기 

1. 중첩된 괄호

: 같은 레벨의 노드들을 괄호로 같이 묶어 표현하는 방법 

2. 중첩된 집합

: 트리가 하위트리의 집합이라는 관계를 잘 보여주는 표현

3. 들여쓰기

:자료의 계층적인 특징을 잘 나타냄 

-노드 표현하기

(부모와 자식,형제 노드를 서로 연결짓는 방법)

1. N-link

: 노드의 차수가 n일 때, 노드가 n개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법(정확히는 잘 이해가 가지 않음,,)

차수가 노드마다 달라지는 트리에는 적용하기 어려움

2.왼쪽자식-오른쪽 형제 표현법

:한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 됨

왼쪽 자식 노드의 주소를 얻은 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 계속해서 얻어 나가면  결국에는 모든 자식노드를 얻을 수 있음

-트리 구현하기 (leftchild,rightsibling 방법으로 구현했음)

1. 노드 선언 

2. 함수 선언 

3. 트리 노드 생성 

생성 함수 구현시 malloc으로 자유저장소에 newnode 공간 확보하는 것 잊으면 안됨! 그리고 newnode 주소 반환하는 것도. 

4. 트리 노드 제거 

5. 트리 제거 

destroytree 구현부에 destroytree를 쓰는 것으로 보아 재귀함수인가? 하는 생각이 듦.

tree를 제거할 때는 root를 파라미터로 넣고 rightsibling,leftchild를 제거하는 방식으로 감 

6. 자식노드 추가하기 

자식 노드는 parent의 leftchild의 rightsibling으로  연결해야하므로 그거 Null 여부 확인한 다음에 연결. 

7. 트리 출력

공부한 날짜: 2021.09.15

-링크드 큐(Linked Queue)의 각 노드는 앞 노드에 대한 포인터를 이용해 구성되어 있기 때문에 / 삽입은 새 노드의 포인터에 후단을 연결하고, / 제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두어 들이는 것으로 구현이 끝남 

-큐의 크기가 예측가능하고 고성능이 필요한 버퍼와 같으 사례에서 링크드 큐가 순환 큐보다 더 유용.

-링크드 큐 구현