junga's record

💡 구간 합 수들의 나열에서 특정 구간의 합을 의미한다. 보통 배열에서 i ~ j 인덱스 사이의 값들의 합을 구하는데 사용한다. 반복문을 사용하여 i ~ j 사이의 값을더하는 알고리즘의 시간복잡도는 O(n)이다. 구간 합 알고리즘을 사용하여 구간 합을 구하는 경우 O(1)의 성능을 갖는다. 합 배열 이용 S[i] = A[0] + A[1] + … + A[i - 1] + A [i] 합 배열 S를 만드는 공식 : S[i] = S[i - 1] + A[i] i ~ j 구간 합을 구하는 공식 : S[j] - S[i - 1] index 0 1 2 3 4 5 기존 배열 A 15 13 10 7 3 12 합 배열 S 15 28 38 45 48 60 ex) A[2] ~ A[4]의 구간 합 구하기 A[0] 부터 A[4] 까지..

💡 배열 (Array) 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조다. 동일 타입의 데이터를 저장하며, 인덱스를 사용하여 값에 바로 접근할 수 있다. 배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없다. 중간에 특정 요소를 삽입 및 삭제하는 경우, 특정 요소로부터 뒤에 있는 모든 요소들을 이동시켜주어야 한다. 삽입 및 삭제에 비용이 많이 들게된다. 배열의 시간 복잡도 Operation average case worst case read O(1) O(1) insert O(n) O(n) delete O(n) O(n) search O(n) O(n) 💡 연결 리스트 (Linked List) 리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조다. 포인터로 연결되어..

이진 탐색 트리 이진 트리로 만들어진 탐색을 위한 자료구조로 4가지 조건을 가진다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 서브 트리들도 이진 탐색 트리를 유지한다. 중복된 키를 허용하지 않는다. 왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드 탐색 찾고자 하는 데이터를 루트 노드부터 비교 시작 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동 찾는 데이터가 없으면 null 반환 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다. 삽입 탐색과 마찬가지로 루트부터 비교 시작 (중복 키 발견 시 추가 없이 종료) 삽입키가 현재 노드의 키보다 작으면 왼쪽으로 이동 삽입키가 현재 노드의 키보다 크면 오른쪽으로 이..

\ 트리(Tree)란? 노드와 링크로 구성된 자료구조(그래프의 일종) 계층적 구조를 나타낼 때 사용한다. 노드(Node): 트리 구조의 자료 값을 담고 있는 단위 에지(Edge): 노드 간의 연결선 (=link, branch) 루트 노드(Root): 부모가 없는 노드, 가장 위의 노드 잎새 노드(Leaf): 자식이 없는 노드 (=단말) 내부 노드(Internal): 잎새 노드를 제외한 모든 노드 부모(Parent): 연결된 두 노드 중 상위의 노드 자식(Child): 연결된 두 노드 중 하위의 노드 형제(Sibling): 같은 부모를 가지는 노드 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합 높이(Height): 트리에서 가장 큰 레벨 값..