방송대 컴퓨터과학과10 방송대 자료구조 교재 요약 제9 장 - 힙 제9장 힙) 개관)힙은 부분적으로 정렬된 완전 이진 트리 형태다. 부모 노드와 자식 노드 간의 관계를 노드 값의 크기에 의해 정의한다.노드 간의 관계에서 부모 노드가 자식 노드보다 크면 최대힙이라고 하며, 부모 노드가 자식 노드보다 작으면 최소힙이라고 한다.힙에서 노드를 삭제하거나 삽입할 경우에는 완전 이진 트리 형태를 계속 갖추어야 한다. 완전 이진 트리!!! Complete Binary Tree!!! 리프 노드에서 왼쪽에서 오른쪽으로 정렬!!!전 이진 트리!!! Full Binary Tree!!! 자식 노드의 수가 0 아니면 2개!!!포화 이진 트리!!! Perfect Binary Tree!!! 모든 자식 노드가 최대 2개 꽉 꽉 차 있다!!!...전에도 얘기한 바 있지만 영어 번역 진짜 마음에 안 .. 2024. 5. 2. 방송대 자료구조 교재 요약 제8 장 - 스레드 트리 제8 장 스레드 트리) 개관)이진 트리를 순회할 때 방문하지 않고 지나쳐 온 노드는 스택에 저장한다.이러면 스택 관리하기가 번거로운데 이런 번거로움을 없앤 트리가 스레드 트리다.(네...? 이 괴랄한 건 뭐죠...)정해진 순회 방법에 따른 방문 순서를 유지하는 포인터를 스레드라고 한다.이 스레드 포인터를 갖는 이진 트리가 스레드 트리다....스레드는 오른쪽 스레드, 왼쪽 스레드, 2가지가 있다.오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킨다.왼쪽 스레드는 그 노드의 선행 노드를 가리킨다....스레드 트리는 두 가지 방법으로 구현할 수 있다.한 가지는 스레드를 저장하는 포인터를 추가하는 방법이다....내가 여기까지 읽고 도저히 이해가 안 돼서 유튜브 영상을 하나 보고 왔다.http.. 2024. 5. 1. 방송대 자료구조 교재 요약 제7 장 - 트리 제7 장 트리) 개관)트리에서는 용어를 정확하게 아는 것이 중요하다. 이렇게 생긴 게 트리다.좀 덜 구체적인 트리 이미지를 가지고 오고 싶었는데 이게 제일 먼저 나와서...교재에는 이진 트리 외에 언급하지 않으니 일단 이걸 쓰자.아, 이미지를 하나 찾았다. 트리에서도 학습할 내용이 방대하다.나야 책 보면서 나름대로 기록한다고 드문드문 쓰고 있지만 트리에 대해서 제대로 공부하고 싶으면바로 위에 있는 링크에서 필요한 내용을 꼭 꼼꼼히 보는 걸 추천한다.CS 공부를 하려면 한글 블로그에서 뭘 찾으면 절대 안 되고 😊... 제대로 정리된 해외 사이트를 이용하시라...아무튼, 트리에서 저기 동그란 걸 노드라고 한다.차수(Degree)는 노드에 달린 자식의 개수다.트리에 속한 모든 노드의 차수가 2 이하인 트리를.. 2024. 5. 1. 방송대 자료구조 교재 요약 제6 장 - 연결 리스트의 응용 제6 장 연결 리스트의 응용) 개관)...학습 목표)1. 단순 연결 리스트와 이중 연결 리스트의 장단점을 이해한다.2. 원형 연결 리스트의 장점을 이해한다....자바에서는 연결 리스트가 이중 연결 리스트로 기본 세팅되어 있다.이걸 단순 연결 리스트나 원형 연결 리스트로 구현하는 방법에 대해서는 내가 찾아 보질 않았는데...어쨌든 C를 사용하는 이 책에서는 '단순 연결 리스트', '이중 연결 리스트', '원형 연결 리스트'를 다 본다.... 볼 때는 쉽다. 그런데 이걸 C로 한 땀 한 땀 구현해야 한다면...전신에 식은 땀이 난다....1. 연결 리스트의 변형...2. 원형 연결 리스트교재에서는 '변형된 원형 연결 리스트도 있다', '~하는 수도 있지만 이 교재에서는 다루지 않는다'라며 연결 리스트의 다양.. 2024. 5. 1. 방송대 자료구조 교재 요약 제5 장 - 연결 리스트 제5 장 연결 리스트) 개관)리스트는 배열과 달리 원소들 간의 논리적인 순서를 표현하기 위한 자료구조다.개인적으로 이 표현이 정말 리스트라는 자료구조의 핵심 중의 핵심이라 생각한다.원소들 간의 순서가 논리적으로 지켜진다면 각 원소가 저장되는 물리적인 위치는 어디든 상관이 없다.배열을 이용하여 리스트를 구현하면(== ArrayList) 원소의 논리적인 순서를 지키기 위해 원소의 이동이 많아진다.따라서 그것보다 포인터 변수를 이용한 연결 리스트(링크드 리스트, LinkedList)를 이용한다.포인터 변수를 사용하고 메모리 할당을 동적으로 하면 리스트 구현 프로그램의 실행에 필요한 메모리의 낭비를 막을 수 있고 프로그램 수행도 효율적으로 할 수 있다. 학습 목표에서 중요한 것리스트와 배열의 차이점이 뭔가요? .. 2024. 4. 30. 방송대 자료구조 교재 요약 제4 장 - 큐 제4 장 큐) 개관)큐는 줄을 서는 순서에 따라서 공평하게 서비스하는 경우에 많이 사용된다.자원의 할당을 받으려는 작업들 간의 순서를 관리하는 경우도 마찬가지다.큐의 입력 연산 시에는 수행 전에 정의된 큐의 크기와 저장된 데이터를 항상 확인해야 한다.크기보다 더 많은 자료를 입력하면 에러가 발생하기 때문이다.삭제 연산을 하기 전에 큐가 비어 있진 않은 지 확인해야 하는 것도 같은 맥락이다.+ 뒤에 큐를 이용한 CPU 할당 방법과 원형 큐에 대한 이야기가 나온다. 정처기에 나올 것 같은 문제..!FCFS 스케줄링(FIFO 스케줄링): 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해 주는 기법RR(Round Robin) 스케줄링 기법: 작업(프로그램)이 도착한 순서대로 CPU가 할당되지만.. 2024. 4. 30. 방송대 자료구조 교재 요약 제3 장 - 스택 제3 장 스택) 개관)스택은 '입출력 순서'를 자료들 간의 관계로 표현하는 자료구조다.스택은 입력이 가장 늦게 된 자료가 가장 먼저 출력되는 관계를 표현한다.그래서 왔던 길을 되돌아가야 하는 미로찾기나 깊이 우선 탐색에 많이 사용되고,예전에 처리했던 값을 역순으로 되돌아가며 찾아내서 처리해야 하는 후위식의 계산에 많이 사용된다.사칙연산에도 주로 사용한다.더보기내가 여기까지 정리하면서 확신이 드는 게 방송대 교재는 실물로, 꼭 사는 게 좋은 거 같다.편입학 초기에는 책을 꼭 사야 하나, 실물 책을 사느냐 eBook을 사느냐 같은 고민을 많이 하는데실물 책을 사야 편하게 형광펜 등으로 체크도 하고, 필기도 하면서 여러 번 볼 수 있다.방송대 컴퓨터과학과 교재 중 기본 CS와 관련 있는 책은 다회독 해도 절대.. 2024. 4. 29. 방송대 자료구조 교재 요약 제2 장 - 배열 2장 개관을 읽는데 모든 줄이 킬링 포인트라서 내가 차마 여기에 다 옮기지를 못 하고 있다.옮기자면 분량이 너무 많고 저작권도 신경 쓰인다.정광식 교수님의 강의를 만족하며 들었기 때문에 더욱 그렇다. 제2 장 배열) 개관)희소행렬이란? 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 희소행렬이라 한다.위 2차원 배열의 모든 행과 열을 다 메모리에 올리면 공간 낭비가 심하다.그래서 값이 0이 아닌 것만 행,열,값 형태로 정리한다. 1. 배열의 정의배열은 인덱스 순으로 표현되는 메모리 영역이다.배열의 원소는 모두 같은 자료형으로 각자 해당 자료형의 값과 같은 크기의 기억 공간을 갖는다.배열의 각 원소의 메모리 주소의 순서가 배열의 인덱스의 순서와 일치해 첫 번째 원소가 위치하는 메모리 주소.. 2024. 4. 29. 방송대 자료구조 교재 요약 제1 장 - 강태원·정광식 공저 더보기개인 공부를 위해 진행한 요약입니다.자료구조에 대해 알고 싶은 분은방송대에서 자료구조 강의를 사거나(단돈 15,000원) 교재(eBook이면 단돈 11,000원, 구판은 실물 도서인데 9,400원(내용 차이 거의 없음))를 구입하는 것을 권장합니다.둘 다 퀄리티가 나쁘지 않습니다.정말 좋다고 말하지 않는 건, 시중 자료구조 책을 많이 보지 않아 비교대조군이 부족하기 때문.머리말)프로그램은 자료구조를 조합해서 만든다. 그래서 프로그램을 효율적으로 만들고 싶다면 자료구조를 알아야 한다.대학 학부과정에서 반드시 알아야 하는 자료구조는 다음과 같다.1. 자료구조의 의미와 개념, 자료구조의 가장 중심 개념인 추상화2. 프로그래밍 언어에서 기본적으로 제공하거나 정의하여 사용하는 자료구조와 그것들을 여러 개 붙.. 2024. 4. 29. 2024년도 방송대 컴퓨터과학과 기말시험 대비를 실시한다 자료구조알고리즘디지털논리회로인공지능C프로그래밍Java프로그래밍순으로 기말시험 대비 정리를 실시한다. 자료구조는 2학기 수업으로, 1학기에 들을 수 없어서 내가 따로 돈 주고(단독 15,000원!!!) 들었다.파이썬프로그래밍기초는 쉬워서 정리 안 할 거다. 2024. 4. 28. 이전 1 다음
