도전하는 일반인

들어가기 전에 트리의 노드에 숫자를 매기는 순회에 대해 살펴보도록 하겠습니다. 학습 목표 여러 가지 순회 방법을 이해하고 직접 해볼 수 있습니다. 핵심 단어 순회 트리:순회 Trees Traversal Pre order traversal: - visit root node - visit left child - visit right child In order traversal: - visit left child - visit root - visit right child Post order traversal: - visit left child - visit right child - visit root 전위 순회 (Pre order traversal): 루트 노드에서 시작하여 왼쪽 자식 노드에 갔다가 오른쪽 자..

들어가기 전에 완전 트리와 정 트리에 대해 살펴보도록 하겠습니다. 학습 목표 완전 트리와 정 트리의 정의를 설명할 수 있습니다. 핵심 단어 완전 트리 정 트리 트리:완전 트리와 정 트리 Complete / Full Every non leaf has two children except for the last row & the last row is filled left -> right Every non leaf has two children & all the leaves are on the same level 완전 트리 (Complete Tree): 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리입니다. 정 트리 (Full Tree): 모든 잎이 ..

들어가기 전에 힙을 이용하여 숫자 배열을 정렬하는 힙 정렬 알고리즘에 대해 살펴보도록 하겠습니다. 학습 목표 힙 정렬 알고리즘의 원리를 이해하고 직접 해 볼 수 있습니다. 핵심 단어 힙 정렬 알고리즘 시간 복잡도 힙:정렬 힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 합니다. 영상에서와 같이, 임의의 숫자들을 나열하고 힙 규칙에 맞게 TrickleDown을 반복하면 그 숫자들이 정렬됩니다. 힙 정렬 알고리즘의 시간 복잡도는 O(nlogn)O(nlogn) 입니다. 두 수를 비교해서 하나를 고르는 방식으로 숫자를 골라내기 때문입니다. (총 n개의 숫자를 logn개의 숫자와 비교합니다.) 숫자들의 순서를 바꿔 정렬하기 때문에 데이터의 복사본을 만들 필요가 없다는 점이 힙 정렬의 장점입니다..

들어가기 전에 힙에서 데이터를 제거하는 과정을 코드로 구현하도록 하겠습니다. 학습 목표 TrickleDown 함수를 이해하고 직접 구현할 수 있습니다. 핵심 단어 힙 TrickleDown 힙:TrickleDown 함수 루트 제거 과정을 코드로 작성하면 다음과 같습니다. 생각해보기 1) 루트의 정보를 없애는 대신 swap 함수를 이용하여 제거하면 어떤 점이 좋나요? 나의 생각: root에 있는 값을 lastposition으로 옮겨주기 때문에 remove를 계속하면 오름차순 정렬이 된다. 출처 : https://www.boostcourse.org/cs204/lecture/626045?isDesc=false

들어가기 전에 힙에서 새로운 데이터를 추가하는 과정을 코드로 구현하도록 하겠습니다. 학습 목표 TrickleUp 함수를 이해하고 직접 구현할 수 있습니다. 핵심 단어 힙 TrickleUp 생각해보기 1) 위 코드에서 lastposition 변수를 사용하는 이유는 무엇인가요? 나의 생각 : lastpostion변수는 root와 얼마나 떨어져있는지 확인하는 용도로 쓰인다. 배열의 요소가 몇개인지 확인하기 위함이다. 출처 : https://www.boostcourse.org/cs204/lecture/626044?isDesc=false

들어가기 전에 배열에 대해 살펴보도록 하겠습니다. 학습 목표 배열과 연결 리스트의 차이점을 이해할 수 있습니다. 핵심 단어 배열 시간 복잡도 배열에는 순서가 있습니다. 그래서 첫 부분을 제거하거나 추가하려면, 요소들을 하나씩 뒤로 옮겨야 하고 시간 복잡도는 O(n)O(n) 입니다. 스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서 기본적인 배열을 사용하지 않습니다. 연결 리스트에서는 배열 맨 앞을 가리키는 head 포인터를 사용합니다. 그래서 리스트의 첫 부분을 제거하거나 추가하는 과정의 시간 복잡도가 상수입니다. 더 효율적인 알고리즘인 연결 리스트는 스택과 큐를 하는 데 사용합니다. 배열은 연결 리스트보다 전형적으로 빠르고 메모리도 덜 차지합니다. 그러나 배열은 크기가 정해져 있습니다. 생각해보기 ..

들어가기 전에 원형 연결 리스트에 대해 살펴보도록 하겠습니다. 학습 목표 원형 연결 리스트를 이해하고 원형 연결 리스트인지 확인하는 방법을 설명할 수 있습니다. 핵심 단어 원형 연결 리스트 시간 복잡도 원형 연결 리스트 원형 연결 리스트는 마지막 next 포인터가 연결 리스트의 노드를 가리키는 연결 리스트입니다. 원형 연결 리스트의 마지막 next 포인터가 head를 가리키는지 확인하는 방법은 다음과 같습니다. - head에서 시작하여 t==null이 될 때까지 반복한다면, 시간복잡도는 O(n)O(n) 입니다. - tail 포인터를 사용할 경우, 시간복잡도는 O(1)O(1) 입니다. 마지막 next 포인터가 임의의 노드를 가리킨다면 확인하는 방법은 다음과 같습니다. - tail에서 시작하여 tail 포인..

들어가기 전에 단일 연결 리스트에 previous 포인터를 추가한 이중 연결 리스트에 대해 살펴보도록 하겠습니다. 학습 목표 이중 연결 리스트를 이해하고 장단점을 설명할 수 있습니다. 핵심 단어 이중 연결 리스트 시간 복잡도 이중 연결 리스트 이중 연결 리스트는 단일 연결 리스트에 바로 전의 노드를 가리키는 previous 포인터를 추가한 연결 리스트입니다. removeLast 메소드를 사용할 때, 단일 연결 리스트는 tail 포인터가 있더라도 O(n)O(n) 의 시간 복잡도로 모든 노드를 한 번씩 거쳐야 한다는 단점이 있었습니다. 하지만 이중 연결 리스트는 tail 포인터가 가리키는 노드에서 previous 포인터가 가리키는 노드를 찾으면 되기 때문에 시간 복잡도가 O(1)O(1) 이 됩니다. 이중 연..

들어가기 전에 반복자에 대해 살펴보도록 하겠습니다. 학습 목표 반복자를 이해하고 Iterator 인터페이스를 활용할 수 있습니다. 핵심 단어 반복자 Iterator 인터페이스 반복자 배열의 각각의 원소를 출력할 때, 다음과 같이 코드를 작성합니다. 혹은, 다음과 같이 나타낼 수 있습니다. 하지만 객체에서 두 번째 방식으로 반복문이 동작하도록 하기 위해서는 Iterator 인터페이스를 구현해야 합니다. Iterator 인터페이스를 구현하는 코드는 다음과 같습니다. } 생각해보기 1) hasNext는 노드의 어떤 정보를 반환할까요? 나의 생각 : 현재 가리키고 있는 노드에 반환할 데이터가 있으면 true를 반환해 준다. 출처 : https://www.boostcourse.org/cs204/lecture/62..

들어가기 전에 연결 리스트의 메소드를 테스트하는 방법에 대해 살펴보도록 하겠습니다. 학습 목표 연결 리스트의 메소드를 테스트하는 방법을 이해할 수 있습니다. 핵심 단어 연결 리스트 연결리스트 테스트 연결리스트를 직접 만들어 지금까지 배운 메소드를 테스트할 수 있습니다. ListI 인터페이스를 구현한 LinkedList를 테스트하는 방법은 다음과 같습니다. 생각해보기 1) 위 Tester 코드에서 노드의 숫자들은 어떻게 채워지고 지워지나요? 숫자들의 순서를 반대로 바꾸려면 어떻게 해야 될까요? 나의 생각 : 위 Tester코드는 뒤로 갈수록 숫자가 작아지게 채워지고 있다. 숫자들의 순서를 반대로 바꾸려면 list.addLast()를 넣어주면 된다. 출처 : https://www.boostcourse.org..