전산직 자료구조 정리(ing)

빅오

간단하게 예를들자면

 

은 내가 만든 알고리즘의 시간 효율성(running time) 을 의미하고 충분히 큰 값인 n과 상수 k에 대해

 

 

가 성립한다.

 

완전 이진트리 : 끝에서 부터 없애

포화 이진트리 : 자식이 다 2개씩 차있어야함

 

일단 AVL트리 .. 

회전 

LL,RR 은 시계,반시게로 돌리고

LR,RL은 왼쪽 돌렸다 오른쪽돌리거나 , 오른쪽 돌리거나 왼쪽으로 돌린다. 삽입은 똑같이 한다.

삽입한 후에 회전할건지 판단함 

https://www.zerocho.com/category/Algorithm/post/583cacb648a7340018ac73f1

(Algorithm) 자료구조(AVL 트리(tree))

 

 

https://www.youtube.com/watch?v=ZfCUwMih70A 

삽입 하는건 레드노드다 

레드노드는 연속될수가 없다 

루트노드는 블랙이다. 

루트노드에서 단말노드까지 블랙노드 수는 같다

 

 

B-트리 

새 노드를 추가할때 오버플로우 나면 가운데 것이 올라간다. 하지만 처음에 루트에 오버플로우 나는건 아래로 내려간다. 

그러다가 아래에 있는 것이 오버플로우 나서 올라가서 루트가 오버플로우 날때는 루트가 위에 루트를 하나 더 만든다.

4번

여기에서

7이 삽입되면 7,13,15로 13이 올라가는데 루트가 오버플로우된다. 이때 더 상위루트가 생긴다 

이 개념이다.

 

리프에서 삭제할때 언더플로우 나면 위에 있던게 왠만해선 내려간다. 그담에 내려가서 원래잇던게 언더플로우나면 그 위에거랑 통합해버린다.(재구조화) = 동료들도 최소개수만큼 있어야 함 그래야 재구조화 시킨다 아니면 통합하면 되니까

 

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

[자료구조] 그림으로 알아보는 B-Tree

 

 

B+트리 

이게 더 애매함 

https://kookyungmin.github.io/study/2018/07/29/data_structure_02/

[자료구조] 2.B+-tree

 

답 4번 ㅋㅋ 풀이 봐야함 

-허프만 트리

만드는 법

1. 빈도수가 가장 적은 것 2개 선택하여 묶는다.( 같은것이 여러개 있으면 아무거나 선택해도 됨)

2. 다시 가장 빈도수가 가장 적은 것을 2개 선택한다 ( 앞에서 묶은 것도 포함해서 판단)

3. 이러한 방법으로 숫자를 더해가면서 마지막엔 다 합쳐진 하나로 모인다

이걸 뒤집으면 2진 트리가 된다.

왼쪽으로 가면 0 오른쪽이면 1로 허프만 코드가 만들어진다. 

그렇게 압축이 된다. 그래서 깊이가 3이고 젤왼쪽이면 000이다. 이게 3개 들어있으면 총 9비트가 사용이 됨 

 

-디지털 탐색 트리

 

순서대로 넣는다고 하면 1이 루트가 되고 001이다. 

삽입하면서 깊이가 깊어지는데 이때마다 left to right로 비트를 옮겨가면서 0이면 왼쪽 1이면 오른쪽으로 간다

5는 101이니까 첫비트가 1이다(100)그래서 오른쪽으로 가서 붙는다

그래서 이런식으로 붙는다.

 

- 연결리스트 

연결, 삽입 등등 

원형, 이중 리스트..

리스트 역순으로 바꾸기 팁 

r = q

q = p 

p = p->link

q-Link = r ; 마지막 빼고는 다 대각선으로 내려온다. 

 

- 수식 표기법 (전,중,후위)

중위-> 후위변환 하기 그리고 변환과정

변환할때 스택은 하나만 사용하는데 연산자만 들어간다 즉 연산자 임시저장장소이다

괄호는 (부터 쭉 넣엇다가 ) 나오면 스택방식으로 빼서 후위표기에 쓰임 

-큐 

일반 큐 : front,rear = -1

원형 큐 : front,rear = 0

 

- 트리

완전이진트리(k-1레벨 까지 채워짐,왼쪽부터),포화이진트리 구분

트리 순회 방법(pre,in,post)

 

- 최소,대 힙

리프노드에 순서대로 삽입된다. 부모와의 관계만 따져서 상위 노드로 올라가서 루트 노드가 최소 또는 최대 값이 된다.

3번

-dfs,bfs

 

- spanning tree와 mst를 찾는법 

크러스칼(비용이 적은 간선부터 하나씩 추가시킴), 프림즈(한 점으로부터 시작해서 이어지는 작은거 추가)

노드가 n개일때 간선 n-1개다! 

 

 

- 이행적 폐쇠 행렬, 반사 이행적 폐쇠(같은것도 1)

 

- 최단경로 

다익스트라, 플로이드-워셜

 

- 정렬

퀵,힙,병합이 젤 빠름

버블 정렬 : 매번 첨 부터 뒤에까지 쭉 가면서 크기에 맞게 들어가있는지 판단.

선택 정렬 : 최소값을 골라 맨앞과 교환 , 그담 최소값 찾아서 두번째랑 교환 .

삽입 정렬 : 첫번째 놈을 기준으로 뒤에놈들 가져와 비교하고 앞뒤로 넣고 이동시킨다. 

1번

 

- 퀵 정렬 : 피봇을 정하고 피봇 기준 작은거 왼쪽 큰거 오른쪽, 피봇 기준 나눠진 두부분에 대해 똑같이 진행 

low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터(8)을 찾으면 멈춘다.
high는 오른쪽에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다.

low와 high가 가리키는 두 데이터를 서로 교환한다.
이 탐색-교환 과정은 low와 high가 엇갈릴 때까지 반복한다.

명심해야될 것이 이게 엇갈리고 난 다음에 pivot이랑 low 또는 high의 위치가 교환되어야 한다.

왜? pivot이 오른쪽에 있다 치자 이건 정렬되어야 하는 놈이다. 이것보다 큰놈이 high니까 위치가 바뀌는게 맞다

만약에 왼쪽에 있으면 low랑 바뀌어야 한다.

아 시발 또 답 안적어놧네

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

힙 정렬 : 완전 이진트리에 넣고 부모노드가 자노드보다 크도록, 이거 넣을때 크기 안따지고 순서대로 넣는다

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

2원 병합 정렬 : 되돌아오면서 정렬이됨 

기수 정렬 : 분배에 의한 정렬. 여분의 기억장치 필요(1의자리수 대로 정리하고, 10의 자리수 대로 정리하고.. 마지막엔 젤 높은 자리수 정렬)

쉘 정렬

 

위상정렬은 전체적인 흐름에 맞아야 한다. b-> d, c->d 이런게 잇을때 순서가 cdb이런식으로 되면 안된다. 상관없을거같지만 연관해서 봐야됨

 

- 해시함수 종류

제산 함수

중간제곱

폴딩법

숫자분석

이때 충돌이 나면 해결책이 필요 

그중 하나는 이차 조사법으로, 해당 충돌난 index + 이차함수(x.^2)같은거를 사용 ex> index = 1이면 1+1, 1+4 ,1+9이렇게 넣는다.

 

20년도 7급서울시, 3번 맞췃으나 이유 명확x

 

1번

3번

 

1번