본문 바로가기

분류 전체보기39

[알고리즘] 트리, 이진트리 안녕하세요. 벌써 3번째 글이군요...⭐.. 사실 이 블로그는 꾸준히 쓸 생각을 안했는데 요즘 알고리즘에 대해 깊이 있는 학습이 필요할거 같아서 ㅠㅠ 하튼 다들 취준생 화이팅입니다. 트리의 개념 그래프의 일종, 비선형 구조 원소들 간의 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 용어 정리 노드 (node) - 트리의 원소 위 트리의 노드 : A, B, C, D, E, F, G, H, I, J, K 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) - 트리의 시작 노드, 부모가 없는 노드 위 트리의 루트 노드 : A 형제 노드 (sibling node) - 같은 부모 노드의 자식 노드들 위 .. 2021. 7. 6.
[알고리즘] 이분 탐색 이분탐색이란 무엇일까? 정렬된 자료를 반으로 나누어 탐색하는 방법 시간 복잡도 : O(log N) 코드 분석 def binary_search(left, right, target): while left target: right = mid - 1 else: left = mid + 1 return None 움직여야 하는 값, 즉, 이 값을 움직여야 겠다. 를 정렬 자료의 중간 값이 찾고자 하는 값인지를 검사 아니면 대소관계를 비교하여 left와 right를 이동 맞으면 함수를 끝낸다. STEP 00 (기본) STEP 01 (중간 값 > Target) STEP 02 (중간 값 < Target) STEP 03 (중간 값 == Target) 종료 백준 참고 문제 https://www.acmicpc.net/probl.. 2021. 6. 9.
[알고리즘] 투 포인터 투 포인터 (Two Pointers) 알고리즘이란? 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻을 수 있음 쓰는 이유? 시간 복잡도 단축이 제일 크다. 보통 이중 for 문을 사용하여 구하는 데, 시간 복잡도가 O(N^2) 으로 Input 값이 커지면 상당히 커진다. 투 포인터를 사용하면 시간 복잡도가 O(N+M)으로 상당히 많이 단축 된다. 부분 합이 5인 연속된 수열의 수를 구해보자! 5 1 2 3 2 5 5 1. 이중 for 문 n = int(input()) arr = list(map(int, input().split())) x = int(input()) ans = 0 for i in range(n).. 2021. 6. 9.

티스토리툴바