일반적인 이진 트리에서, 많은 노드들이 자식 노드를 하나만 가지거나 전혀 가지지 않는 경우가 많습니다. 이진 트리의 많은 부분에 빈 공간이 생기며, 트리를 순회 (recursion)할 때 이 빈 공간을 효율적으로 사용하지 못하는 문제가 있습니다. 스택 없이 이진트리의 연산을 구현하는데에 2가지 방법이 있습니다.1. node 객체에 부모를 가리키는 레퍼런스 필드를 추가로 선언하고 순회2. 노드의 null 레퍼런스 사용 = 스레드 이진 트리스레드 이진 트리(Threaded Binary Tree)는 이러한 문제를 해결하기 위해 고안된 자료구조입니다. 스레드 이진 트리는 트리의 노드들이 자식 노드가 없는 경우, 그 노드의 포인터를 다른 유용한 노드에 연결하여 메모리 공간을 효율적으로 사용합니다. 이 연..

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 ..

이진 탐색 = UpDown 게임 순차 탐색은 처음부터 끝까지 보면서 탐색하므로 O(N)의 시간이 걸림. 이진 탐색은 배열을 절반으로 계속해서 나누어 mid값이 목표값이 될 때까지 나누게 됨. O(logN)의 시간이 소요됨 다만, 이진 탐색은 이미 정렬되어있는 배열에서 탐색해야한다. 그렇지 않으면 정상적으로 동작하지 않음. 이진탐색 구현 - python으로 구현하였다. def BinarySearch (arr,target): left = 0 right = len(arr)-1 while(True): mid = (left+right)//2 if(arr[mid] == target): return mid elif(arr[mid] < target): left = mid+1 else: right = mid-1 targ..

1. 전체 값 중 가장 작은 값을 찾음 2. 해당 값을 맨 첫번째에 배치함 3. 첫번째 값을 제외하고 가장 작은 값을 찾아 두번째에 배치함 4. 두번째, 세번째, ... n-1번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함. ✨선택정렬의 시간 복잡도 버블 정렬 : 중간에 정렬이 완료된 것이 확인되면 정지 선택 정렬 : 반드시 n-1,n-2,...,2,1 번의 비교 연산을 수행해야함. 약 n*(n-1)/2번의 연산을 필요로 함 = O(N^2) ✨선택정렬의 구현 python으로 구현해보겠다. def selection_sort(arr): length = len(arr) for i in range(length-1): minindex = i for j in range(i+1,length): if a..

for문이 1억번 도는데 1초정도의 시간이 소요됨 - 제한 시간이 1초인 문제를 풀 때 대략 1억 이하의 시간복잡도를 보이는 솔루션이면 통과 가능하다 N