밍경송의 E.B

이 글은 시험이 갑자기 15시간정도 남은 사람이 내용 정리를 위해 적는 글입니다. *[C언어로 쉽게 풀어쓴 자료구조] 책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다.🎅 🎅정렬 : 데이터들을 특정순서로 정리하는 것. (수업에서는 non-decreasing order 위주로 다룸) 예에.. 모든 경우에 최적인 정렬 알고리즘은 없다! -> 정렬할 대상의 개수/ 수행시간/ 가용한 mem 또는 disk 크기 고려 필요 ㄴ평가기준 | 비교 횟수와 이동 횟수의 많고 적음 7가지 정렬에 대해서 다뤄보겠습니다. 빠르게 ..' 1 선택정렬(selection sort) 🎅 초기) 비어있는 왼쪽리스트와 정렬이 필요한 오른쪽리스트 -> 완성) 왼쪽리스트에 정렬된 리스트가 오고, 오른쪽리스트는 비어있는 상태 노란색이..

이 글은 시험이 1일 어쩌고정도 남은 사람이 내용 정리를 위해 적는 글입니다. *[C언어로 쉽게 풀어쓴 자료구조] 책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다.🦭 신장트리 : 그래프 내의 모든 정점을 포함하는 트리 (|V|-1개의 |E|를 가짐) 🦭 MST(최소비용신장트리) 🦭 : 그래프의 모든 정점들을 가장 적은 수의 간선과 비용(가중치 그래프의 경우) 으로 연결 -> 전체적으로 비용 감소 목적*if weight가 동일한 간선이 있다면, 여러 MST가 나올 수도 있음! 더보기그래프 G = (V,E)의 MST G' = (V',E')의 조건1) V = V'2) E'은 E의 부분 집합, |E'| = |V| -1 (no cycle in G') 3) Sum(weight of edges in E')..

이 글은 시험이 2일 23시간정도 남은 사람이 내용 정리를 위해 적는 글입니다. *[C언어로 쉽게 풀어쓴 자료구조] 책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다.🐶 🐶그래프 : 연결되어 있는 객체 간의 관계를 표현하는 자료구조 (tree도 그래프의 특수한 경우*뒤에서 다룸) G = ( V, E ) 정점(node, verticle) - V(G) : 그래프G의 정점들의 집합 개수: |V| 간선(edge, link) - E(G) : 그래프 G의 간선들의 집합 개수: |E| ⚠️cf 오일러 문제 : 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제 * 다리(edge,link)는 한 번씩만 지나야 함, 육지(node,vertex)는 여러 번 지나도 됨 => 오일러 정리 : 모든 정점에 ..

이 글은 시험이 15시간정도 남은 사람이 내용 정리를 위해 적는 글입니다. *[C언어로 쉽게 풀어쓴 자료구조] 책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다. 아 또 바꾸고 싶음! 🫥👑 요걸로 하겠다 👑 원형 연결 리스트 : 마지막 노드의 링크가 첫번쨰 노드를 가리키는 리스트 * 장점: 임의 노드에서 다른 모든 노드로 접근이 가능, 리스트의 맨 앞/뒤의 노드 삽입/삭제 용이 🫥헤드 포인터가 마지막 노드를 가리키게 구성하면 ! 리스트의 처음/마지막에 노드를 삽입하는 연산이 O(1) *이름은 head지만 첫번째 노드를 가리키지 않음에 주의! 🫥연산 1) 처음에 삽입 더보기 //생략// node->link = head->link; head->link = node; 2) 끝에 삽입 더보기 //생략/..

이 글은 시험이 17시간정도 남은 사람이 내용 정리를 위해 적는 글입니다. *[C언어로 쉽게 풀어쓴 자료구조] 책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다. 이걸로 계속 가겠음.🪸😎 🪸 리스트 *배열과 연산 비교 - 배열은 i번째 요소를 찾기 쉽지만, 리스트의 경우 순차적으로 탐색해야 하기 때문에 시간이 오래 걸림. 🪸 리스트 구현 방법 1) 배열을 이용한 구현 (순차적 표현) *장점 : 구현이 간단하고 속도가 빠름. *단점 : 중간에 데이터를 삽입/삭제할 때 기존 데이터를 이동해야 함. 😎 get_entry() 와 insert_last()의 경우 O(1) 소요 😎 pos에 있는 요소 insert() , delete()의 경우 최악: O(n) 소요 -insert() : 마지막 항목(size..

이 글은 시험이 19시간정도 남은 사람이 내용 정리를 위해 적는 글입니다. *[C언어로 쉽게 풀어쓴 자료구조] 책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다. 이걸로 계속 가겠음.🪸😎 🪸 특징 : 선입선출(FIFO) - 들어오는 문과 나가는 문이 다름. - enqueue : 큐의 끝(rear)에 요소를 추가함. - dequeue : 큐의 앞(front)에서 요소를 제하고 반환함. * peek() : 큐의 앞에서 요소를 읽어 반환함 (제거하지 않음) 🪸 선형큐 : 배열을 선형으로 사용하여 큐를 구현한 것 *front : 가장 최근에 제거된 data가 저장됐던 위치 *rear : 가장 최근에 들어온 data의 위치 * 초기 상태의 front , rear의 값은 -1 * 공백 상태의 경우 fron..