Computer Science34 [자료구조] 이진트리 (Binary Tree) 이진트리(Binary Tree)란?이진트리(Binary Tree)란 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질때 이진트리라고 한다.최대 2개의 자식노드를 가질때이기 때문에 자식이 없을수도 있고, 한개만 있을수도 있다 이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현한다.그래서 같은 루트에 같은 자식노드 하나를 가지고있어도, 자식노드의 위치가 왼쪽과 오른쪽이 다르다면 이 두 트리는 서로 다른 트리가된다.아래 그림은 A라는 같은 루트노드를 가지고있지만, 자식노드의 위치가 왼쪽,오른쪽 다르기때문에 두개의 트리는 별개의 트리(서로 다른 트리)가 된다. 이진트리(Binary Tree)의 종류1. 정 이진트리(Full Binary Tree / Strict Binary Tree) 이.. 2024. 7. 26. [자료구조] 트리(Tree)란? 배열, 리스트, 스택과 큐, 해시테이블과 같은 자료구조는 데이터의 이전 데이터나 다음 데이터의 순서가 존재하는 선형 자료구조에 해당한다.이러한 구조는 특정 데이터를 검색할때 순서대로 데이터를 찾아야하는 문제점과,데이터를 저장하기위해 일정한 공간을 미리 할당해야하는 등의 제한적인 구조를 가지고있어 복잡한 문제를 해결하는데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 계층적 문제란 계층적 속성을 갖는 자료는 선형구조로 표현하기가 어렵다는 것을 뜻한다순환 종속성 문제란 두개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 뜻하는데, 이또한 선형구조로 표현하기에는 어려움이 있다. 따라서 이러한 단점들을 개선하기위해 비선형 자료구조가 나오게되었다비선형 자료구조는 크게 트리와 .. 2024. 7. 26. 정렬 알고리즘[Quick Sort] Quick sort 란? Quick sort는 최선,평균 시간복잡도가 O(n log n)이고, 최악의 경우에는 O(n^2)인것을 확인할 수 있다.그리고 메모리는 O(n log n)인것을 확인할 수 있다 Quick sort는 이름에서도 나타나듯이 평균적으로 매우 빠른 수행속도를 자랑하는 정렬방법이다. Quick sort도 Merge sort와 같이 분할정복법을 사용한다. 그러나 Merge sort와 달리 리스트를 균등하게 분할할 필요는 없다.Quick sort도 Merge sort와 같이 시간복잡도가 O(n log n)인데, Quick sort가 훨씬 짧은 시간이 걸린다는것을 알 수 있다. 왜그럴까??이는 "참조지역성의 원리"로 설명할 수 있다!Quick sort는 알고리즘 특성상 동일한 배열 내에서 자리.. 2024. 7. 22. 정렬 알고리즘[Merge Sort] 정렬알고리즘을 살펴보기전에 먼저 시간복잡도에 대해서 알아볼 필요가 있다시간복잡도에 대한 내용을 정리했었어서 링크만 첨부하도록 하겠다시간복잡도란?간단하게 한줄로 요약해보면시간복잡도란 "입력값과 연산수행시간의 상관관계를 나타내는 척도" 를 말한다즉, "문제를 해결하는데 걸리는 시간과 입력의 합수관계"이다. 시간복잡도는 최악을 기준으로 "빅오 표기법"으로 표시하여 성능을 예측하는데,시간복잡도가 빠른순으로 보면 아래와 같이 나타낼 수 있다O(1) O(log n) O(n) O(n log n) O(n^2)O(1)이 시간복잡도가 가장 좋고(가장 빠르고), O(n^2)이 가장 안좋은것(가장 느림)을 알 수 있다 Merge sort 란?이제 5개의 정렬알고리즘이 있는 표를 보면서 Merge Sort에 대해서 알아.. 2024. 7. 22. 알고리즘[시간복잡도] 시간복잡도란?우리는 일상생활에서 거의 알고리즘을 사용한다예를들어 출퇴근할때 어떻게가야 효율적으로 갈수있을지 생각하는것도 알고리즘이라고 할 수 있다.이때 우리가 중요하게 생각하는것이 "속도"다. 시간복잡도란 "입력값과 연산수행시간의 상관관계를 나타내는 척도" 를 말한다즉, "문제를 해결하는데 걸리는 시간과 입력의 합수관계"이다. 시간복잡도 표현방법?점근적 표기법으로 시간복잡도를 나타내는데, 아래 3가지가 있다최상의 경우 : 오메가 표기법 (Big-Ω Notion)평균의 경우 : 세타 표기법 (Big-θ- Notion)최악의 경우 : 빅오 표기법 (Big-O Notion)평균인 세타표기법을 사용하는것이 가장 좋다고 생각할 수도 있는데, 평가하기 까다롭다고한다.시간복잡도는 최악을 기준으로 "빅오 표기법"으로.. 2024. 7. 22. 프로그래머스 알고리즘 문제[나누어 떨어지는 숫자] # 문제 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요. # 제한사항 arr은 자연수를 담은 배열입니다. 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다. divisor는 자연수입니다. array는 길이 1 이상인 배열입니다. # 입출력 예 입출력 예#1 arr의 원소 중 5로 나누어 떨어지는 원소는 5와 10입니다. 따라서 [5, 10]을 리턴합니다. 입출력 예#2 arr의 모든 원소는 1으로 나누어 떨어집니다. 원소를 오름차순으로 정렬해 [1, 2, 3, 36]을 리턴합니다. 입출력 예.. 2024. 3. 25. 이전 1 2 3 4 5 6 다음
