bereben

트리 트리는 노드와 가지로 구성되어 있다. 각 노드는 가지를 통해 다른 노드와 연결된다.루트 트리의 가장 위에 있는 노드를 루트노드라고 한다. 루트트리는 한개만 존재한다.리프 가장 아래쪽에 있는 노드를 리프라고 한다. 리프는 단말 노드(terminal node), 외부노드(external node)라고도 한다. 리프노드는 더이상 뻗어 나갈 가지가 없는 마지막 노드를 말한다.비단말 노드 리프를 제외한 노드를 비단말 노드(non-terminal node)라고 한다. 다른 말로는 내부 노드(internal node)라고도 불린다.자식 어떤 노드와 가지로 연결되어 있는 아랫쪽 노드를 자식이라 한다. 자식은 여러개 존재할 수 있다. 리프는 자식이 없다.부모 어떤 노드와 가지로 연결되어 있는 위쪽 노드를 부모라고 ..

아이고 이진탐색문제를 푸는데 bisect없이 풀어 보겠다고 도전했지만 보기 좋게 실패했다. 그래서 공부도 하고 라이브러리 의존도를 낮추기 위해 파이썬의 bisect의 bisect_left를 구현했다. 구조 bisect에는 대표적으로 bisect_left와 bisect_right가 있다. bisect_left와 bisect_right는 둘 다 배열에서 value가 들어갈 수 있는 적절한 위치를 반환하는 함수이다. 규칙 두 함수는 이진탐색을 할 때 이러한 규칙을 가진다. bisect_left : value arr[index] 예시 배열에 10 20 30 40 50 있다고 하자. 이 배열에서 25가 들어갈 위치를 찾을 때 배열 안에 같은 값이 없..

문제 제약사항 1

리스트란? 순서가 있는 데이터를 늘어놓은 자료구조를 말한다. 종류로는 선형리스트와 연결리스트가 있다. 1. 단순 배열 연결리스트 단순 배열로 연결 리스트를 만들 경우 삽입, 삭제할 때마다 뒤에 데이터를 모두 옮겨야 하므로 효율적이지 않다.2. 포인터를 이용한 연결 리스트 연결 리스트에서 각각의 원소를 노드라고 한다. 이 노드는 데이터와 다음 노드를 가르키는 포인터로 이뤄져 있다. 그래서 일반적인 경우 이러한 방법으로 연결 리스트를 구현한다.class Node: def __init__(self, val): self.val = val self.next = None def printNode(node): while node is not None: print(node.val, end = ' ') n..

링크 문제 최소값과 최대값을 포함하는 서브어레이는 총 몇개인가? 제약사항 2

문자열 검색이란? 어떤 문자열안에 다른 문자열이 있는지 검사하고 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다.1. 브루트 포스법 선형 검색을 단순하게 확장한 알고리즘이라 단순법이라고 한다.원리 만약 텍스트 apple에서 패턴 ple을 검색하는 방법이다. 첫번째 시작부분인 a에서부터 패턴의 총 개수인 3개를 검사한다. 다르다면 한칸 이동하여 반복 수행한다. 만약 패턴이 모두 맞다면 시작하는 인덱스를 출력하며 종료한다. 2. KMP법 브루트 포스법은 틀린 패턴이 있으면 한칸만 이동하고 다시 검색을 한다. 하지만 KMP법은 버리지 않고 활용하는 알고리즘이다.원리 버리지 않고 활용을 하지만 몇번째 문자열부터 다시 검사를 할지 판단하는 표를 만들어 재활용이 가능하다는 장점이 있으나 보이어 무어법보다 느..

5. 셸 정렬 단순 삽입 정렬의 장점을 살리고 단점을 보완하여 더 빠르게 정렬하는 알고리즘기존의 문제점 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다. 개선방법 정렬할 배열의 원소를 그룹으로 나눠서 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다. 원리 4- 정렬, 2- 정렬, 1-정렬 즉, 배열 전체에 적용을 시킨다. 이를 h-정렬이라 한다. 배열에서 h만큼 떨어진 원소를 그룹시켜 각 그룹별로 정렬을 수행한다. h를 4, 2, 1로 감소시키며 정렬을 수행한다. h값을 효율적으로 선택하는 법 h를 효율적으로 선택해야 각 그룹을 선택할 때 보다 충분히 섞일 수 있다. 그렇기에 h값이 서로 배수가 안되도록 선택해야 한다. h의 값을 1부터 선택해..

정렬이란? 값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 작은 데이터를 앞쪽부터 늘어놓은 것을 오름차순 큰 데이터를 앞쪽부터 늘어놓은 것을 내림차순이라 한다. 정렬 알고리즘에서 교환, 선택, 삽입은 핵심 개념이다.1. 버블 정렬 이웃한 원소를 비교하여 작은값을 앞으로 큰값을 뒤로 교환하는 정렬을 말한다.코드 구현 arr = [6,4,3,7,1,9,8] for i in range(len(arr)): for j in range(len(arr)-i-1,i,-1): if arr[j-1] > arr[j]: arr[j], arr[j-1] = arr[j-1], arr[j] 2. 세이커 정렬(버블 정렬 개선) 정렬이 거의 완료된 배열을 버블정렬하면 빠르게 완료하기가 어렵다. 가장 큰..

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 한개이다. 특정한 한개의 노드에서 나머지 노드의 최단 거리를 찾을 때 사용한다. 다익스트라 알고리즘의 원리는 이와 같다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3, 4를 반복한다. 즉, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 찾아 해당노드에서의 다른 노드의 거리를 비교해 갱신하는 것을 반복하는 것이 핵심이다. 그래서 이것을 빠르게 사용하기 위해서는 우선순위 큐를 사용하여 방문하지 않은 노드를 리스트에 삽입 후 사용하면 빠르게 접근할 수 있다. 구현 imp..

재귀란? 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 경우를 말한다. 특징 : 스택처럼 마지막에 들어간 것이 첫번째로 종료가 된다. 장점 : 재귀를 사용하면 코드가 간결해진다.!!! 단점 : 너무 깊이 들어가면 오류가 날 수도 있다. 처리할게 많아지면 구조가 많이 복잡해진다. 1) 팩토리얼 def fact(n): if n > 0: return n * fact(n - 1) else return 1 fact(5) 순서 fact(5) = 5 * fact(4) ==> fact(4)로 진입 fact(4) = 4 * fact(3) ==> fact(3)로 진입 fact(3) = 3 * fact(2) ==> fact(2)로 진입 fact(2) = 2 * 1 ==> 종료 2 리턴 fact(..