알고리즘(19)
-
[Algorithm] 쿼드트리 개념 및 코드
📌 쿼드트리란 무엇인가? 이진트리에 대해선 들어보셨을 겁니다. 한 개의 부모 노드에서 두 개의 자식 노드가 파생되는 구조의 자료구조입니다. 파이썬으로 구현하면 이렇게 생겼습니다. 🎨 이진 트리 구현 (python) class Node: def __init__(self): self.item = item self.left = None self.right = None 쿼드트리는 이진트리의 응용 버전입니다. 한 개의 부모 노드에서 네 개의 자식 노드가 파생되는 구조가 쿼드트리입니다. 쿼드트리는 이진트리처럼 나무가지로 표현할 수도 있습니다. 📌 쿼드트리 정의 하. 지. 만 쿼드트리는 3D 데이터를 표현하기 위한 자료구조인 '장면 그래프(Scene Graph)'에 해당합니다. 상하 개념이 없고, 3차원 세계를 4개..
2022.06.28 -
[Algorithm] 이분 탐색(Binary Search) 개념 및 코드(python)
순서대로 나열되어 있는 배열이 있습니다. 이 배열에서 target 값을 찾으려 하는데, 배열 요소가 100만개라 모두 비교하면 시간이 많이 걸립니다. 이때 더 빠르게 target 값을 찾을 순 없을까요? 이 필요성을 채워주는 것이 이분 탐색 알고리즘입니다. 📌 이분 탐색 정의 이분 탐색은 정렬된 배열을 1/2씩 줄여서 타겟 값을 찾아나가는 알고리즘입니다. 이분 탐색의 프로세스는 다음과 같습니다. (1) 배열의 중간 값을 찾는다. (2) target 값과 중간 값을 비교하여 (low, same, high)큰지, 작은지, 같은지를 판단한다. (3) target이 작다면 중간 값 이전의 배열을, 크다면 중간 값 이후의 배열을 대상으로 다시 이분 탐색을 진행한다. (4) 만약 같다면, 중간 값이 바로 targe..
2022.06.20 -
[BOJ] #1912번: 연속합
문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 예제 입력 1 10 10 -4 3 1 5 6 -35 12 21 -1 예제 출력 1 33 예제 입력 2 10 2 1 -4 3 4 -4 6 5 ..
2022.05.26 -
[BOJ] #9461번: 파도반 수열
문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 예제 입력 1 2 6 12 예제 출력 1..
2022.05.26 -
[BOJ] #25083: 새싹
문제 아래 예제와 같이 새싹을 출력하시오. 입력 입력은 없다. 출력 새싹을 출력한다. ,r'"7 r`-_ ,' ,/ \. ". L_r' `~\/ | | 풀이 무턱대고 print()를 써버리면, 새싹 안에 있는 따옴표들을 제대로 처리해줄 수 없다. 큰/작은따옴표 앞에 \(역슬래시)를 써줘야 문자 따옴표로서 처리할 수 있다. print(" ,r\'\"7") print("r`-_ ,\' ,/") print(" \. \". L_r\'") print(" `~\/") print(" |") print(" |")
2022.05.17 -
[Algorithm] 동적계획법 (Dynamic Programming) 개념 및 구현
동적계획법 Dynamic Programming 이번 포스팅에선 동적계획법 알고리즘을 살펴보겠다. 동적계획법은 "한 번 계산한 문제는 다시 계산하지 않는다"라는 신념을 가진 녀석이다. 메모리를 조금 써서 속도를 비약적으로 상승시키는 것이 핵심이다. Let's Go 동적계획법이 아니라면? 보통은 단순 재귀. 동적계획법의 성능을 확인할 수 있는 문제가 있다. 바로 피보나치 수열이다. 피보나치 수열을 동적계획법이 아닌 단순 재귀를 사용하여 구현하면 다음과 같다. def fibo(x): if x == 1 or x ==2: return 1 else: return fibo(x-1) + fibo(x-2) 위의 코드로 피보나치 수열을 구한다고 생각해보자. --- fibo(5)를 구하기 위해선, fibo(4)와 fibo(..
2022.05.03