Algorithm14 알고리즘 | 이분탐색 개념과 예제 + 심화 📌 개념 다지기 이분 탐색 탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다. 두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편이다. ✔️탐색하는 방법 배열이 정렬(sort)되어 있어야한다. left와 right를 배열의 양 끝으로 설정한다. mid = (left + right) / 2 로 설정하여, mid 값이 기준값보다 작거나 큰지 확인한다. (오름차 배열 정렬되어있을 때) mid 값이 기준값 보다 작다면, left를 (mid+1)로 설정한다. (오름차 배열 정렬되어있을 때) mid 값이 기준값 보다 크다면, right를 (mid-1)로 설정한다. left > right 가 될 때 까지 2,3 번을 반복한다. ✏️이분.. 2021. 8. 26. 프로그래머스 | Level 2. 거리두기 확인하기 ✅ 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81302 ✏️ 조건 두 사람의 맨해튼 거리가 2 초과여야 거리두기를 지킨 것이다. 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 두 사람 사이에 파티션이 있다면, 지나갈 수 없으므로 거리두기를 지킨 것이다. 대기실은 5개이고, 각 대기실의 크기는 5x5 ✏️ My Solution - DFS 📌 접근법 DFS로 접근 사람의 위치 정보를 DFS에 보내서 해당 위치에서 거리 2 안에 사람이 있는지 확인. 두 사람의 거리가 맨해튼 거리가 아니라면, 무조건 0을 반환해야함. 파티션이 있는 경우.. 2021. 8. 24. [자료 구조] 트리(Tree) - 2. 파이썬 구현 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌 노드 클래스 만들기 ✔️ Node 는 data값과 brach에 대한 정보를 가지고 있다. class Node: def __init__(self, value): self.value = value self.left = None self.right = None 📌 이진 탐색 트리 삽입/ 탐색 구현 ✔️ 이진 탐색 트리를 control 하는 class를 생성한다. => NodeMgmt class NodeMgmt: def __init__(self, head): # 제일 위에있는 root node를 설정 self.head = head def insert(self, value): # root node 부터.. 2021. 6. 25. [자료 구조] 트리(Tree) - 1.구조 이해 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌 트리(Tree)란 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 그 중에서 노드의 Branch가 최대 2개인 경우를 이진 트리라고 부른다. ✔️ 이진 트리 종류 이진 탐색 트리 완전 이진 트리 (Heap에서 사용) ... ✔️ 이진 트리에서 알아야 하는 용어 노드(Node) : 트리에서 데이터를 저장하는 기본 요소 (그림에선 동그라미임. data + branch 정보) 루트 노드(Root Node) : 트리 맨 위에 있는 노드 레벨 (Level) : 최상위 노드를 Lv0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄. 부모 노드 (Parent .. 2021. 6. 25. 이전 1 2 3 4 다음
