분류 전체보기
-
[알고리즘] 기하 알고리즘 - 2차원 트리Computer Science/Algorithm 2021. 12. 14. 04:14
2차원 트리 이진 트리 형태를 가지며, 동적으로 변화하는 트리 범위 탐색에 편리하게 사용할 수 있도록 기하학적 공간을 나눔 만드는 과정 이진 탐색 트리를 만드는 과정과 유사 이진 탐색트리와 다른 점은 이진 트리의 레벨에 따라 y축과 x축을 번갈아 가면서, 한번은 y좌표값을 기준으로 삽입하고, 한번은 x좌표값을 기준으로 삽입하는 것임 2차원 트리 만드는 과정 1. 해당 위치가 x좌표 or y좌표인지 확인 2. 해당 위치에 맞는 좌표와 새로 삽입할 좌표와 비교 3. 위치 선정 4. x좌표 or y좌표자리인지 확인 5. 새로운 좌표를 알맞은 좌표모양으로 그려죽; 한번은 y좌표값을 기준으로 삽입하고, 한번은 x좌표값을 기준으로 삽입해야하므로, 삽입 시 쉽게 판별할 수 있도록 다른 모양으로 그려줍니다. 삽입 과정..
-
[알고리즘] AVL 트리Computer Science/Algorithm 2021. 10. 24. 03:26
AVL 트리 러시아의 수학자 Adelson - Velskii 와 Landis가 고안한 높이 균형 이진 탐색 트리 오른쪽 서브트리와 왼쪽 서브트리의 높이 차가 2이상이 되면 회전을 통해 트리의 높이 차를 1이하로 유지 높이차 = 오른쪽 서브트리의 높이 - 왼쪽 서브트리의 높이 이진 탐색 트리를 기반으로 하기 때문에 삽입 시엔 이진 트리 처럼 노드를 삽입한다. AVL 트리의 높이 차 AVL 트리에선 노드 삽입 시, 회전이 필요한 경우 2가지가 있습니다. 경우 1: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 1자인 경우 -> 단일 회전 단일 회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전 경우 2: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 >, 이중 회전 이중 회..
-
[Python] 2309 일곱 난쟁이Algorithm/백준 2021. 10. 15. 02:43
1. 문제 📚 2. 입출력 예 📋 3. 알고리즘 ✅ 2명만 제외하면 100이 되니, 이중 for문을 이용하여 모든 경우의 수 중, 일곱명의 키 합 - (두개를 더한 값) = 100이면 그 두개만 -1로 변경해주어 출력해주었다. 4. 소스코드 💻 import sys height_list = [] for i in range(9): height_list.append(int(sys.stdin.readline())) height_sum = sum(height_list) is_exist = False for i in range(len(height_list) - 1): for j in range(i + 1, len(height_list)): if height_sum - (height_list[i] + height_l..
-
[Python] 백준 11650 - 좌표 정렬하기Algorithm/백준 2021. 10. 12. 20:45
1. 문제 📚 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ sorted 함수를 이용하여 정렬한다. ❗️ list를 sort 할 경우는 맨 앞을 기준으로 정렬한다. 4. 소스코드 💻 import sys input = sys.stdin.readline N = int(input()) nums = [] for i in range(N): [a, b] = map..
-
[Python] 입국심사Algorithm/프로그래머스 2021. 6. 3. 02:52
1. 문제 📚 2. 입출력 예 📋 3. 알고리즘 ✅ 코테의 이진 탐색 문제는 탐색범위가 큰 상황에서 탐색을 가정하는 문제가 많다. 따라서 탐색 범위가 클 경우 이진 탐색으로 문제에 접근해보자 ! 1. 일을 하는 데 소요하는 시간 min, max 정하기 min = 1 max = 가장 오래 걸리는 심사대 * 일의 개수 2. 각 입국 심사대에서 처리 한 일들이 n의 값이 되는 지 확인해보기 각 입국 심사대에서 일한 개수 = mid // n 3. mid 값 조정하기 - mid / time 이 n의 값보다 크다면, mid를 줄인다. - mid / time 이 n의 값보다 작다면, mid를 늘린다. 마지막 mid 값이 우리가 구하는 최소 값이 된다. 4. 소스코드 💻 def solution(n, times): st..
-
[Python] 백준 2193번 이친수Algorithm/백준 2021. 5. 17. 23:59
1. 문제 📚 2. 입출력 예 📋 3. 알고리즘 ✅ Dp 문제이므로 규칙 또는 점화식을 찾는다 N / 끝의 수 0 1 출력 값(갯수) 1 0 1 1 2 1 0 1 3 1 1 2 4 2 1 3 5 3 2 5 6 5 3 8 규칙을 보면, N이 1과, 2일 땐 1이며 그 이외엔 그 전에 값 2개를 합친 값과 출력 값이 같다는 규칙을 찾을 수 있다. 4. 소스코드 💻 n = int(input()) nums = [1] * n if n == 1 or n == 2: print(1) else: for i in range(2, n): nums[i] = nums[i-1] + nums[i-2] print(nums[n-1])