2143 => 1234처럼 만들어야 하므로 먼저 str로 받고 원소 각각을 비교하면 된다.
🧐 백준 2108 (통계학 _ statistics 라이브러리 이용)
🤫해결의 실마리
🤔 수학 통계 내장함수 statistics (https://python.flowdas.com/library/statistics.html) 이 문제의 경우, 최빈값을 구하기 위해 count함수를 사용하게 될 경우, 이로 인해 시간초과가 걸리게 된다. 따라서 아래의 통계학관련 statistics 라이브러리의 multimode()함수를 이용해 최빈값을 구해준다.
import statistics as st
num = [int(input()) for _ in range(int(input()))]
mode =st.multimode(num)
if len(mode) > 1:
mode.remove(min(mode))
print(int(sum(num)/len(num)))
print(round(st.median(num)))
print(min(mode))
print(max(num) - min(num))
🧐 백준 10814,11650, 11651 (C++의 pair와 같은 자료구조가 필요해!) ★★★★★
🤫해결의 실마리 1. python의 sort는 stable 정렬을 한다.
파이썬은 기본적으로 stable_sort이기에 나이 기준 정렬을 해도 가입한 순서는 그대로!
🤫해결의 실마리 2. 2차원 리스트의 경우, 하나의 for문으로 접근할 수 있다!
파이썬은 다음과 같이 2차원 배열의 경우, 한번에 요소에 접근할 수 있다.
arr = list(input().split() for _ in range(int(input())))
for x, y in arr:
print(x, y) => arr[0][0], arr[0][1]
🤔Algorithm 과정 굳이 int로 받지 않아도 어차피 '20' < '21' 이므로 정렬한 person리스트를 for문을 이용해 접근한다. 이때, 정렬할 때, key = lambda식을 이용해 a[0], 즉 나이를 기준으로 정렬하는 방법을 사용한다.
🤫solution_10814
# 파이썬의 sort함수는 기본적으로 stable정렬을 한다.
person = list(input().split() for _ in range(int(input())))
# str로 받아도 원소값을 int로 받아 비교가 가능하다.
for x, y in sorted(person, key = lambda a: int(a[0])):
print(x, y)
10814와 마찬가지로 해결
🤫solution_11650
num = [list(map(int, input().split())) for _ in range(int(input()))]
# num에는 다음과 같은 형태로 저장됨
# [[3, 4], [1, 1], [1, -1], [2, 2], [3, 3]]
# for문으로 2차원 리스트 요소 출력
# [1, -1] [1, 1] [2, 2] [3, 3] [3, 4]
for x, y in sorted(num):
print(x, y)
🤫solution_11651
num = [list(map(int, input().split())) for _ in range(int(input()))]
# 맨 뒤의 원소 a[1]을 기준으로 정렬 후 a[0]을 기준으로 정렬
for x, y in sorted(num, key = lambda a: (a[1], a[0])):
print(x, y)
단, 이 문제에서 유의할 점은 python은 정렬에서 기준 여러 개 세울 수 있다는 점이다. 위에서 처럼 말이다.
# 맨 뒤의 원소 a[1]을 기준으로 정렬 후 a[0]을 기준으로 정렬
sorted(num, key = lambda a: (a[1], a[0])):
🧐 백준 18870 (메모리에 대한 접근)
🤫해결의 실마리 1. 메모리 제한이 여유롭다??
🤔 이 문제는 메모리 제한이 512MB로 여유로운데, 이에 대해 살펴볼 필요가 있다. - 메모리 제한이 많음 = 순서를 따로 저장(hash)하지 않으면 시간초과가 발생할 것이라 유추 - 순서만 간단히 비교하면 되기에 set으로 중복을 없애고 sort를 진행하면 더 간단히 해결 가능. 🤔사실 문제에서 말하는 바는 등수를 출력하는 것과 동일!
🤫해결의 실마리 2. 딕셔너리 자료구조
🤔 Dictionary. -key-value 형태로 이루어진 자료구조로 값과 데이터의 대응관계를 표현할 때, powerful하다. -이때, 핵심은 key값은 중복될 수 없다는 점이며 아래의 코드를 예시로 들어 보겠다.
# x_set에는 [-10, -9, 2, 4] 원소가 들어가있는 set리스트이다.
x_dict = {x_set[i] : i for i in range(len(x_set))}
#x_dict = { -10: 0, -9: 1, 2: 2, 4: 3 }
# print(x_dict[-9]) # key값을 이용한 value, 1 출력
🤔Algorithm 과정 1. 입력값을 저장하는 x리스트와 2. x리스트의 원소들이 겹치지 않도록 set을 만들어 정렬시켜준다. 3. 오름차순 정렬이 된 set에 index를 맵핑해주면 그것이 비로소 순위가 되므로 4. set_element : index의 맵핑을 위해 딕셔너리를 사용해준다. 5. 그 후 x리스트를 돌면서 해당 원소와 일치하는 값과 맵핑한 딕셔너리의 value값(인덱스, 순위 값)을 출력
🤫solution_18870 (시간초과)
N = int(input())
x = list(map(int, input().split()))
x_prime = []
for i in x:
cnt = 0
for j in set(sorted(x)):
if i > j:
cnt += 1
x_prime.append(cnt)
print(*x_prime)
처음 짠 코드로 문제점은 이중 for문을 이용하여 if문을 2번 돌리면 시간복잡도가 O(n^2)이다. 이 문항의 경우 시간복잡도가 O(nlog n)의 정렬 알고리즘이 필요하다.
🤫solution_18870
N = int(input())
x = list(map(int, input().split()))
x_set = sorted(list(set(x)))
x_prime = []
# x_set의 [-10, -9, 2, 4]에 index를 맵핑하여 딕셔너리로(순위)
# cf. 딕셔너리는 해시를 이용해 데이터 저장
x_dict = {x_set[i] : i for i in range(len(x_set))}
#x_dict = {-10: 0, -9: 1, 2: 2, 4: 3}
# print(x_dict[-9]) # 1 출력
for i in x:
print(x_dict[i], end = " ")
🤔 Algorithm 과정 1. num이라는 빈 리스트에 입력된 M ~ N까지의 숫자를 넣는다. 2. 약수의 개수를 세는 cnt라는 변수를 선언, 0으로 초기화한다. 3. 소수를 담을 리스트 dec을 선언한다. 4. num리스트의 원소를 차례로 돌면서 i % j == 0 즉, 약수일 때, cnt값을 증가시킨다. 5. 이렇게 약수의 개수가 담긴 cnt변수에 대해 만약 약수의 개수가 2개라면(cnt == 2) 소수인것! 따라서 소수라면 dec 리스트에 원소를 추가해주고 cnt==0이라면 소수가 없는 것이므로 0을 출력!
🤫solution_2581
M, N = int(input()), int(input())
num = []
for i in range(N-M+1):
num.append(i+M)
dec = []
for i in num:
cnt = 0
for j in range(1, i+1):
if i % j == 0:
cnt += 1
if cnt == 2:
dec.append(i)
if len(dec) == 0:
print(-1)
else:
print(sum(dec))
print(min(dec))
🧐 백준 1929 (에라토스테네스의 체) _ 앞으로 계속 이 문제에서 파생하여 문항을 해결함
🤫해결의 실마리
🤔 에라토스테네스의 체 (Sieve of Eratosthenes)
에라토스테네스의 체 원리는 다음과 같다. 1. 소수가 아닌 1을 지운다. 2. 2의 배수를 지운다. 3. 앞서 지운 2의 배수가 아닌 것들 중 최소값인 3의 배수를 지운다. 4. 앞서 지운 2, 3의 배수가 아닌 값들 중 최소값인 5의 배수를 지운다. 5. 이 과정을 반복하여 걸러지는 것들이 비로소 소수가 된다. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 이러한 에라토스테네스의 체는 "특정 구간이 주어졌을 때" 매우 빠르게 소수를 도출할 수 있다. 위의 2581번처럼 풀면 시간복잡도는 O(n)으로 비교적 시간이 오래 걸린다. 하지만 에라토스테네스의 체의 시간복잡도는 O(nlog(log n))으로 매우 빠르게 도출이 가능하다. 또한 약수의 경우, 2*4, 4*2 처럼 반복이 되기 때문에 가장 중요한 것은 범위의 마지막 수의 루트 값까지만 반복함으로 시간을 더욱 줄일 수 있다!
🤔Algorithm 과정 알고리즘과정은 위에서 설명하는 에라토스테네스의 방식을 차용하였다. 또한 코드에 대한 설명은 아래 그림으로 대체하겠다.
🤫solution_1929
m, n = map(int, input().split())
num = [i for i in range(max(2, m), n+1)] # m ~ n사이 숫자를 넣은 리스트 (단, 1은 제외)
dec_sqr_n = [] # n의 제곱근까지의 범위안에서 소수를 집어 넣을 리스트
for i in range(2, int(n**0.5) + 1): # 2에서 n의 제곱근까지만 반복
if i in num:
dec_sqr_n.append(i)
num = [j for j in num if j % i != 0]
print(*(dec_sqr_n + num), sep = "\n")
🧐 백준 4948 (에라토스테네스의 체)
🤫해결의 실마리
🤔에라토스테네스의 체(Sieve of Eratosthenes) 🤔Algorithm 과정 위 1929와 거의 동일한 방식으로 풀었지만 방법은 다음과 같다. 1. n의 범위 사이의 자연수를 저장하는 num 리스트를 생성한다. (1 ≤ n ≤ 123456) 2. 리스트 num을 1929번 풀이처럼 소수만 존재하도록 만들어준다. 3. 1929와 같은 방식으로 n의 범위사이에 존재하는 모든 소수가 담긴 decimal이라는 리스트를 생성해준다. 4. 0이 들어오기 전까지 while문을 이용해 입력을 받아주고 5. decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력해준다.
🤫solution_4948 (시간초과)
def decimal(N):
n = N+1
num = [i for i in range(n, 2*N + 1)]
dec_half = []
for i in range(2, int((2*N)**0.5) + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j % i != 0]
return len(dec_half+num)
num = -1
while True:
num = int(input())
if num == 0:
break
else:
print(decimal(num))
처음 짠 코드로 1929와 비슷하게 함수를 생성하여 풀었으나 시간초과가 발생하였다. 시간복잡도를 염두하지 않고머리를 장식으로 두고 문제에 접근한 결과라 생각할 수 밖에 없다. 함수에서 2중 for문을 사용한 것을 while문에서 계속 받으니 그럴 수 밖에...
🤫solution_4948
from math import sqrt
# 1 <= n <= 123456 사이 자연수를 담은 리스트 생성
num = [i for i in range(2, 123456 * 2)]
# 리스트 num을 이전처럼 소수만 있게 만들어주기.
dec_half = []
for i in range(2, int(sqrt(123456*2)) + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j%i != 0]
decimal = dec_half + num
n = -1
while True:
n = int(input())
if n == 0:
break
# decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력
print(len([i for i in decimal if n < i <= 2*n]))
🧐 백준 9020 (에라토스테네스의 체)
🤫해결의 실마리
🤔에라토스테네스의 체(Sieve of Eratosthenes) 🤔Algorithm 과정 두 소수의 차이가 가장 작은 것의 의미를 생각해보면 다음과 같다. 소수간의 차이가 작을수록 최대값의 절반과 가까워진다! 16으 예로 들자면 다음과 같다. [3, 13], [5, 11] => 3 5 (8) 11 13
따라서 핵심은 시간초과가 걸리지 않으려면 소수의 절반만 훑어야 한다.
🤫solution_9020 (시간초과)
T = int(input())
n = [int(input()) for _ in range(T)]
num = [i for i in range(2, 10001)]
dec_half = []
for i in range(2, 100 + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j % i != 0]
decimal = dec_half + num
for i in n:
dec = []
for j in range(len(decimal)):
for k in range(j, len(decimal)):
if i == decimal[j] + decimal[k]:
dec.append([decimal[j], decimal[k]])
print(*dec[-1])
처음 짠 코드로 문제점은 소수의 전체를 계속 훑으면서 비교를 진행하기 때문에 위의 알고리즘보다 2배 이상의 시간이 걸릴 가능성이 높다. 먼저 위의 코드를 짠 과정은 다음과 같다. 1. 먼저 범위에 해당하는 모든 소수를 담는 리스트를 생성하고 2. 그 리스트 안에서 두 소수간의 덧셈이 입력값과 동일한 것을 찾아서 dec이라는 리스트에 넣는다. 3. dec에는 [[3, 5]], [[3, 7], [5, 5]], [[3, 13], [5, 11]] 처럼 들어간 것이므로 4. 각 리스트의 마지막 인덱스에 해당하는 리스트가 차이가 가장 작은 소수 리스트인것. 이를 for문을 이용해 출력하였다.
🤫solution_9020
num = [i for i in range(2, 10000 + 1)]
dec_half = []
for i in range(2, 100 + 1):
if i in num:
dec_half.append(i)
num = [j for j in num if j%i != 0]
decimal = dec_half + num
T = int(input())
for i in range(T):
n = int(input())
n_half = n // 2
for j in range(n_half, 1, -1):
if j in decimal and n - j in decimal:
print(j, n - j)
break
# cf-1 pop
a = [1,2,1,3,4,5,1]
removed = a.pop(1) # 1번째 index 삭제 단, return 가능
print(a) # [1, 1, 3, 4, 5, 1]
print(removed) # 2 <-- pop한 원소를 return 가능
# cf-2 del -> pop과 다르게 리스트의 범위를 지정해 삭제 가능
a = [1,2,1,3,4,5,1]
del a[:2]
print(a) # [1, 3, 4, 5, 1]
#cf-3 remove -> 위와 달리 지우고자 하는 인덱스가 아닌 값을 입력
for _ in numbers :
numbers.remove(3)
🤫solution_1427
# 입력: 999998999
num = list(map(int, input())) # 공백없이 입력받을 때, list에 저장하는 법
print(*sorted(num, reverse = True) , sep = '')
# sep=''를 통해 원소간의 구분자인 공백을 없애줌으로
# 9 9 9 9 9 9 9 9 8 을
# 999999998 로 출력
# cf. end옵션을 사용하면 그 뒤에 나오는 출력값과 구분을 짓는 구분자 역할을 한다.
print(*sorted(num, reverse = True) , end = " hello ")
print(num)
# 9 9 9 9 9 9 9 9 8 hello [9, 9, 9, 9, 9, 8, 9, 9, 9] 가 출력
🤫solution_1676
def fac(n):
if n <= 1:
return 1
else:
return n * fac(n - 1)
N = int(input())
n = fac(N)
# 숫자를 리스트에 한자리씩 넣기 (숫자->문자열)
str_num = str(n)
str_list = list(str_num)
cnt = 0
for i in reversed(str_list):
if i == '0':
cnt += 1
else:
break
print(cnt)
🤫solution_2577
num = []
for i in range(3):
n = int(input())
num.append(n)
mul = 1
for i in range(3):
mul *= num[i]
str_x = list(str(mul))
int_x = list(map(int, str_x))
out_ls = []
for i in range(10):
out_ls.append(int_x.count(i))
for i in range(10):
print(out_ls[i])
🧐 백준 1292 , 4458 풀이 및 사용함수
🤫해결의 실마리
🤔리스트 사용의 핵심!인덱스 슬라이싱 인덱스 슬라이싱에 대한 응용방법을 아래 해설을 통해 볼 수 있는데,[:]를 이용한다.
🤫solution_1292
A, B = map(int, input().split())
num_sequences = []
for i in range(1000):
for j in range(i):
num_sequences.append(i
print(sum(num_sequences[A-1:B]))
🤫solution_4458
for i in [input() for _ in range(int(input()))]:
print(i[:1].upper() + i[1:])
🧐 백준 1157 풀이 및 사용 함수
🤫해결의 실마리
🤔 원소가 겹치지 않아? set 자료구조 주로 사용하는 리스트로 set을 변환하는 방법은 다음과 같다.
a_set = set(a)
lst = []
for i in a_set:
lst.append(a.count(i))
🤫solution_1546
a = list(str(input()).upper())
a_set = set(a)
cnt = []
for i in a_set:
cnt.append(a.count(i))
if cnt.count(max(cnt)) <= 1:
print(max(a, key = a.count))
else:
print("?")
🧐 백준 1292 , 4458 풀이 및 사용함수
🤫해결의 실마리
🤔리스트 사용의 핵심! 인덱스 슬라이싱 인덱스 슬라이싱에 대한 응용방법을 아래 해설을 통해 볼 수 있는데, [:]를 이용한다.
🤫solution_1292
A, B = map(int, input().split())
num_sequences = []
for i in range(1000):
for j in range(i):
num_sequences.append(i
print(sum(num_sequences[A-1:B]))
🤫solution_4458
for i in [input() for _ in range(int(input()))]:
print(i[:1].upper() + i[1:])
🧐 백준 2309, 2822 풀이 및 사용함수
🤫해결의 실마리
🤔정렬을 스스로 해주는 내장함수, sorted를 이용하자!
정렬 함수는 다음 2가지를 사용할 수 있다.
a.sort()
sorted(a)
둘의 차이는 바로 반환의 여부이다. a.sort의 경우, 반환을 해주지 않기에 print문에 넣어주면 오류가 발생하게 된다. 하지만 sorted의 경우, 값의 반환이 이루어질 수 있어서 print문에서도 오류가 발생하지 않는다.
dwarf = [int(input()) for _ in range(9)]
for i in range(len(dwarf)):
for j in range(i+1, len(dwarf)):
if (sum(dwarf) - (dwarf[i] + dwarf[j])) == 100:
dwarf1, dwarf2 = dwarf[j], dwarf[i] # out of index range 조심
dwarf.remove(dwarf1)
dwarf.remove(dwarf2)
break
else:
continue
print(*sorted(dwarf), sep = "\n")
🤫 solution_2822
score = [int(input()) for _ in range(8)]
total = list(sorted(score, reverse=True))
print(sum(total[:5]))
idx_list = []
for i in range(5):
idx_list.append(score.index(max(score)) + 1)
score[score.index(max(score))] = -100
print(*sorted(idx_list))
# sorted(idx_list) => [3, 4, 5, 6, 8]
# *sorted(idx_list) => 3 4 5 6 8
🧐 백준 11047 풀이
🤫solution_11047 (Greedy Algorithm)
N, K = map(int, input().split())
coin = sorted([int(input()) for _ in range(N)], reverse=True)
cnt = 0
while K != 0:
for i in range(N):
if coin[i] > K:
i -= 1
else:
frequency = K // coin[i]
K -= coin[i] * frequency
cnt += frequency
print(cnt)
🤔 단일 입력 ( a = input() 처럼 사용할 때는 default가 str로 아래와 같이 type을 표시할 수 있다.)
a = int(input())
🤔123456과 같이 공백없이 입력을 list로 받을 때 (a를 list가 아닌 float변수로 받고자 하면 map으로 시작)
num = list(map(int, input()))
🤔1 2 3 4와 같이 띄어쓰기를 기준으로 입력을 list로 받을 때 (a를 list가 아닌 float변수로 받고자 하면 map으로 시작)
- 공백을 기준으로 입력받은 애들을 잘라서 int로 만든 뒤(map이 반복되는 애들을 특정 자료형으로 바꿔준다.)
- 이를 list로 감싸줘서 int형의 반복적인 것들이 리스트화 되는 것이다.
a = list(map(float, input().split()))
🤔 위와 달리 enter를 기준으로 아래처럼 입력받을 때
1
2
3
4
a = [int(input()) for i in range(10)]
🤔num이라는 리스트에 TestCase라는 숫자만큼 리스트 공간을 생성 (2차원)
1 2
3 4
5 6
TestCase = int(input())
num = [list(map(int, input().split())) for _ in range(TestCase)]
# 위의 코드는 앞으로 다음과 같이 사용
num = [list(map(int, input().split())) for _ in range(int(input()))]
이를 다른 언어로 생각해보면 num [ TestCase ][ list(map(int, input().split())) ] 위와 같은 느낌이라 생각하면 된다.
🧐 백준 1546에서 사용한 함수
🤫해결의 실마리
🤔 최대값, 최소값을 반환하는 함수 max, min
1. 인자 1개일 때 => max(list_name)
2. 인자 2개일 때 => max(arg1, arg2) # arg에서 가장 큰 값을 출력, list라면 list 자체를 출력
3. key나 lambda를 이용 => max(num, key = num.count) # 최빈값을 구하는 식
그렇다면 2번째로 큰 값이나 작은 값은 어떤 방식으로 구하면 될까? 1. 정렬을 해준다. => sort 사용 2. sort 후 1번 인덱스 값을 출력해주면 된다.
num = [int(input()) for _ in range(9)]
num.sort(reverse=True)
print(num[1])
🤔뒤집어 주는 함수reverse
for i in reversed(str_list):
if i == '0':
cnt += 1
else:
break
위의 코드처럼 reversed를 for문에 넣어 기존 원소를 반대방향에서 접근할 수 있다.
🤔리스트에 새로운 요소를 추가하는 함수append, insert
list_name.append(x)는 list의 맨 끝에 객체 x를 추가한다.
list_name.insert(idx, x)는 list의 idx에 객체 x를 추가한다.
🤔특정 값의 길이를 구하는 함수len
len(list_name) 는 list_name의 길이를,
len(string) 은 string의 길이를 구할 수 있다
🤫 solution_1546
N = int(input())
score = list(map(float, input().split()))
M = max(score)
new_score = []
for i in range(N):
new_score.append(score[i]/M*100)
new_mean = sum(new_score) / len(new_score)
print(new_mean)
🤫solution_1676
def fac(n):
if n <= 1:
return 1
else:
return n * fac(n - 1)
N = int(input())
n = fac(N)
# 숫자를 리스트에 한자리씩 넣기 (숫자->문자열)
str_num = str(n)
str_list = list(str_num)
cnt = 0
for i in reversed(str_list):
if i == '0':
cnt += 1
else:
break
print(cnt)
🧐 백준 2562 , 10797사용함수
🤫해결의 실마리
🤔리스트에서 조건에 맞는 인덱스를 찾는 함수ls.index(조건)
ls = []
ls.index(max(ls))
🤔리스트에서 조건에 맞는 개수를 찾는 함수 ls.count(조건)
num.count(day)
🤔리스트에 특정 값이 존재하는지 확인하는 법 if a in ls
if item in list:
print('리스트에 값이 있습니다.')
else:
print('리스트에 값이 없습니다.')
🤔리스트에 특정 값이 없는지 확인하는 법 if a not in ls
if item not in list:
print('리스트에 값이 없습니다.')
else:
print('리스트에 값이 있습니다.')
🤫solution_2562
num = [int(input()) for _ in range(9)]
print(max(num), num.index(max(num))+1, sep = " \n")
🤫solution_10797
day = int(input())
num = list(map(int, input().split()))
if day in num:
print(num.count(day))
else:
print(0)
🧐 백준 2506 풀이 및 사용함수
🤫 해결의 실마리
🤔리스트에 저장된 value 기준의 for문을 이용하자!
for i in lst:
if (i == 1):
. . .
for i in range(len(list_name))은 list의 길이만큼 for문을 순회하는 것으로 i의 값이 0, 1, 2, 3, . . . , list길이 만큼 나오지만
for i in lst: 의 경우 만약 lst = [10, 30, 345, 123]이라면 4회 돌긴 하지만 i의 값이 10일때, 30일때로 돌게 된다. 즉, i에 리스트의 값이 되입되면서 list 원소를 이용한 접근할 수 있다.
🤫 solution_2506
num = int(input())
ox = list(map(int, input().split()))
sum, cnt = 0, 0
for i in ox:
if (i == 1):
cnt += 1
sum += cnt
else:
cnt = 0
print(sum)
🧐 백준 2576, 9085 풀이
🤫 solution_2576
num = [int(input()) for _ in range(7)]
sum, ans = 0, 0
odd_list = []
for i in range(7):
odd = num[i] % 2 != 0
if odd:
odd_list.append(num[i])
sum += num[i]
if len(odd_list) == 0:
print(-1)
else:
print(sum, min(odd_list), sep = "\n")
🤫solution_9085
T = int(input())
sum_T = []
for i in range(T):
N = int(input())
sum_T.append(sum(list(map(int, input().split()))))
print(sum_T[i])
🧐 Algorithm_왜 틀리는거지... 1. 소문자와 대문자의 구별을 없애기 위해 소문자를 대문자로 바꿔준다. 2. 알파벳을 총 25개이므로 각각의 알파벳의 개수를 세주기 위한 count배열 생성 3. count한 값이 2개 이상이라면(max와 동일한 count값이 있다면) ? 출력 4. 그게 아니라면 max값에 해당하는 index에 해당하는 알파벳 출력
1번.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
getline(cin, str);
// 1. 소문자와 대문자의 구별을 없애야 함
for (int i = 0; i < str.length(); i++){
if (str[i] >= 'a' && str[i] <= 'z')
str[i] = str[i] - 'a' + 'A';
}
// 2. 알파벳은 총 25개(Z-A = 25)이므로 count를 위한 배열을 생성 및 초기화해줘야함
int count[26]; for (int i = 0; i < 26; i++) count[i] = 0;
for (int i = 0; i < str.length(); i++){
int idx_number = str[i] - 65;
count[idx_number]++;
}
char c;
int max = -1;
for (int i = 0; i < 26; i++){
if (count[i] == 0)
continue;
else if (count[i] > max){
max = count[i];
c = (char)(i + 65);
}
else if (count[i] == max){
c = '?';
}
}
cout << c;
}
2번.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
getline(cin, str);
// 1. 소문자와 대문자의 구별을 없애야 함
for (int i = 0; i < str.length(); i++){
if (str[i] >= 'a' && str[i] <= 'z')
str[i] = str[i] - 'a' + 'A';
}
// 2. 알파벳은 총 25개(Z-A = 25)이므로 count를 위한 배열을 생성 및 초기화해줘야함
vector<int> alpha_count(26); for (int i = 0; i < 26; i++) alpha_count[i] = 0;
for (int i = 0; i < 26; i++){
int idx_number = str[i] - 65;
alpha_count[idx_number]++;
}
int max = *max_element(alpha_count.begin(), alpha_count.end());
int cnt = count(alpha_count.begin(), alpha_count.end(), max);
int index = max_element(alpha_count.begin(), alpha_count.end()) - alpha_count.begin();
if (cnt >= 2)
cout << "?";
else if (cnt < 2)
cout << (char)(index + 65);
}
🧐 Algorithm_한줄에 입력을 모두 공백없이 받기 1. 먼저 공백없이 입력을 받아 저장하는 string 변수 str과 2. string을 char배열에 넣기 위한 작업을 진행한다. char c[str.length()+1] 이라는 배열을 생성해주고 이 배열에 str에 저장된 문자열을 집어넣어 주기 위해 copy함수를 사용해준다.
3. 그 후 char 형의 5를 int 형의 5로 바꿔줘야 하므로 다음과 같은 방법을 이용해 준다. 9 = '9'-'0' (= 57 - 48) 위와 같은 방법을 이용하면 c[i] - '0'은 해당 숫자와 동일한 값을 갖게 된다.
4. 이후 최종적으로 sum이라는 변수에 최종적인 값들의 합을 저장해주면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int num; cin >> num;
string str; cin >> str;
int sum = 0;
char c[str.length() + 1];
str.copy(c, str.length() + 1);
int arr[str.length() + 1];
for (int i = 0; i < str.length(); i++) {
arr[i] = c[i] - '0';
}
for (int i = 0; i < str.length(); i++) {
sum += arr[i];
}
cout << sum;
}
🧐 Algorithm 1. 먼저 등차수열이어야 하므로 자리수간의 공차가 같아야 하기에 a-b와 b-c의 값이 동일해야함. 2. 이를 위해 함수 hansu를 만들었고 이를 100의자리수에서 사용. 3. 100~999까지 기준일 때 등차수열조건을 만족시켜야 하므로 다음과 같이 함수를 사용한다.
#include <iostream>
#include <algorithm>
using namespace std;
bool hansu (int num){
int a = num / 100;
int b = (num - a*100) / 10;
int c = num % 10;
return a-b == b-c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int cnt = 0;
int num; cin >> num;
if (num <= 99){
cout << num;
}
else if (num >= 100 && num <= 999) {
for (int i = 100; i <= num; i++) {
cnt += hansu(i);
}
cout << cnt + 99;
}
else
cout << 144;
}
🧐 Algorithm _ 소수를 찾는 법 1. a % b == 2라는 식은 약수를 구하는 식이며 2. 이 약수의 개수를 세는 cnt라는 변수를 이용해 x의 약수개수를 구하고 3. 소수의 특징 (약수의 개수가 1과 자기자신)을 이용해 약수 개수가 2인 자연수 값들을 세준다.
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
int num; cin >> num;
int count = 0;
for (int i = 0; i < num; i++) {
int cnt = 0;
int x; cin >> x;
for (int j = 1; j <= x; j++)
if (x % j == 0)
cnt++;
if (cnt == 2)
count++;
}
cout << count << endl;
return 0;
}
🧐 Algorithm _소수를 찾는 법 1. a % b == 2라는 식은 약수를 구하는 식이며 2. 이 약수의 개수를 세는 cnt라는 변수를 이용해 x의 약수개수를 구하고 3. 소수의 특징 (약수의 개수가 1과 자기자신)을 이용해 약수 개수가 2인 자연수 값들을 세준다.
이를 이용해 값들의 전체 합을 구해주고 가장 최소값은 작은 순서대로 vector에 넣어줬으므로 당연히 vector의 첫번째 원소에 들어있는 값이 최소값이 된다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
int M, N; cin >> M >> N;
int sum = 0;
vector<int> v;
for (int i = M; i <= N; i++) {
int cnt = 0;
for (int j = 1; j <= i; j++)
if (i % j == 0)
cnt++;
if (cnt == 2){
v.push_back(i);
sum += i;
}
}
if (v.size() == 0)
cout << -1 << endl;
else {
cout << sum << endl;
cout << v[0] << endl;
}
}
정렬은 오름차순, 내림차순과 같은 방식으로 특정 필드값인 key를 기준으로 value간의 정렬을 진행해 주며 다음 2가지로 나뉜다.
단순, 비효율적 방법:삽입, 선택, 버블 정렬 ==> 대개 자료의 개수가 적을 때 사용 복잡, 효율적인 방법: 힙, 합병, 퀵 정렬 ==> 반드시 자료의 개수가 많다면 효율적 알고리즘을 사용해야 함.
🧐 간단하지만, 비효율적인 정렬 방법
👉 삽입 정렬 (insertion Sort)
삽입정렬은 마치 카드놀이 새 카드를 받는 것 처럼 정렬한 카드들 사이의 올바른 자리에 넣는 것이다.
삽입정렬 방식은 다음과 같이 진행된다.
🤨 insertion sort Algorithm
insertionSort(A, n)
for i <- 1 to n-1 do key <- A[i]; j <- i-1; while j ≥ 0 and A[j] > key do A[j+1] <- A[j]; j <- j-1; A[j+1] <- key
void insertionSort (int A[], int n) {
for (int i = 0; i < n; i++) {
int key = A[i];
int j;
for (j = i-1; j >= 0 && A[j] > key; j--)
A[j+1] = A[j];
A[j+1] = key;
}
}
👉 선택 정렬 (Selection Sort)
가장 이해하기 쉬운 정렬방법으로 오른쪽 리스트가 공백상태가 될 때까지 오른쪽 리스트에서 왼쪽리스트로 가장 작은 숫자를 선택해 이동시킨다.
이렇게 입력배열 이외에 다른 추가 메모리를 요구하지 않는 정렬방법을 제자리 정렬이라 한다.
🤨 selection sort Algorithm
selectionSort (A, n)
for i <- 0 to n-2 do least <- A[i], A[i+1], . . . , A[n-1] 중 가장 작은 값의 idx; A[i]와 A[least]의 교환; i++;
void selectionSort (int A[], int n) {
for (int i = 0; i < n-1; i++) {
int least = i;
for (int j = i+1; j < n; j++)
if (A[j] < A[least])
least = j;
swap(A[i], A[least]);
}
}
👉 버블 정렬 (Bubble Sort)
마치 거품이 일어나듯 인접한 2개의 인덱스 값들을 서로 비교하여 큰 값을 오른쪽에 두도록 서로 swapping 하는 것으로 과정은 아래와 같다.
정렬은 오름차순, 내림차순과 같은 방식으로 특정 필드값인 key를 기준으로 value간의 정렬을 진행해 주며 다음 2가지로 나뉜다.
단순, 비효율적 방법:삽입, 선택, 버블 정렬 ==> 대개 자료의 개수가 적을 때 사용 복잡, 효율적인 방법: 힙, 합병, 퀵 정렬 ==> 반드시 자료의 개수가 많다면 효율적 알고리즘을 사용해야 함.
🧐 복잡하지만, 효율적인 정렬 방법
👉 힙 정렬 (Heap Sort)
힙 (heap)은 완전 이진트리(complete binary tree)의 일종으로 우선순위 큐를 위해 만들어진 자료구조다.
힙(heap)은 요소들이 완전히 정렬된 것은 아니지만일종의 반 정렬상태를 유지한다. 이로 인해삽입 삭제의 시간복잡도가 O(log n)으로 다른 방법보다 훨씬 유리하다.
이런 힙은여러 개의 값들 중 최댓값과 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조이다. 이를 위해부모 노드의 key 값 > 자식 노드의 key 값 을 항상 만족하도록 만들어졌다. (보통 최대힙으로 가정하는 편) 단, BST와는 다르게Heap tree는 중복된 값을 허용한다.
- 위는 힙에 대한 설명으로 힙정렬은 다음과 같은 방식으로 진행한다.
1. 정렬할 배열을 먼저 최소 힙으로 변환한다. 2. 가장 작은 원소부터 차례대로 추출한다.
#include <queue>
#include <functional> //최소 힙을 사용하기에 써줘야 함
using namespace std;
// 최대 힙을 사용한 내림차순 정렬
void heapSortDec(int arr[], int n) {
priority_queue<int> maxHeap;
for (int i = 0; i < n; i++) {
maxHeap.push(arr[i]);
}
// maxHeap을 이용해 내림차순으로 정렬
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.top();
maxHeap.pop();
}
}
// 최소 힙을 사용한 오름차순 정렬
void heapSortInc(int arr[], int n) {
priority_queue<int, vector<int>, greater<int> > minHeap;
for (int i = 0; i < n; i++) {
minHeap.push(arr[i]);
}
// minHeap을 이용해 오름차순으로 정렬
for (int i = 0; i < n; i++) {
arr[i] = minHeap.top();
minHeap.pop();
}
}
👉 합병 정렬 (Merge Sort)
합병정렬은 분할 정복(divide and conquer)기법을 바탕으로 두고 있다.
🤨 Divide and Conquer란?
1. 하나의 리스트를 2개의 균등한 크기로 분할 (점점 작은 sub problem을 만드는 방법) 2. 분할을 계속 지속해서 1개의 원소로 나눈 후 정렬 진행 3. 두 원소씩 다시 합쳐 전체가 정렬된 리스트를 만드는 방법
🤨merge Algorithm
merge(A, left, mid, last) b1 <- left; e1 <- mid; b2 <- mid + 1; e2 <- right; sorted 배열을 생성; index <- 0; while b1 ≤ e1 and b2 ≤ e2 do if (A[b1] < A[b2]) then sorted[idx] <- A[b1]; b1++; idx++; else sorted[idx] <- A[b2]; b2++; idx++; 요소가 남아있는 부분배열을 sorted로 복사; sorted를 A로 복사;
🤨merge sort Algorithm
mergeSort (A, left, right) if left < right mid = (left + right) / 2; mergeSort(A, left, mid); mergeSort(A, mid + 1, right) merge(A, left, mid, right)
#define Max_Size 1024
static void merge(int A[], int left, int mid, int right) {
int i, j, k = left, l;
static int sorted[Max_Size];
for (i = left, j = mid + 1; i <= mid && j <= right; )
sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];
if (i > mid)
for (l = j; l <= right; l++, k++)
sorted[k] = A[l];
else
for (l = i; l <= mid; l++, k++)
sorted[k] = A[l];
for (l = left; l <= right; l++)
A[l] = sorted[l];
}
void mergeSort (int A[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}
}
👉 퀵 정렬 (Quick Sort)
평균적으로 매우 빠른 속도를 자랑하는 정렬방법으로 위의 합병정렬같은 분할 정복(divide and conquer)기법을 바탕으로 두고 있다.
다만 합병정렬과는 달리 리스트를 균등하게 분할하지 않고 리스트 안의 한 요소를 pivot으로 선택한다.
퀵정렬의 과정은 아래와 같이 진행된다.
🤨 퀵 정렬 과정
1. 리스트에서 하나의 원소, pivot을 고른다. 2. pivot앞에는 보다 값이 작은 모든 원소들이, pivot 뒤에는 보다 값이 큰 모든 원소들이 오도록 pivot을 기준으로 리스트를 둘로 나눈다(분할). 분할을 마친 후 pivot은 더 이상 움직이지 않는다. 3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
이를 위해 중요한 3개의 함수가 사용된다. - quickSort: 퀵정렬 알고리즘을 이용해 배열의 left ~ right를 오름차순으로 정렬. - partition: 퀵정렬에서 가장 중요한 함수로 pivot을 설정, 데이터를 left, right로 크기에 따라 이동시킴. - swap: 조건에 따라 pivot기준으로 왼쪽과 오른쪽의 값들을 서로 바꿔주기 위한 함수
https://coding-factory.tistory.com/615
#include <iostream>
using namespace std;
static int partition(int A[], int left, int right) {
int low = left;
int high = right + 1;
int pivot = A[low];
do {
do {
low++;
} while (low <= high && A[low] < pivot);
do {
high--;
} while (high >= left && A[high] > pivot);
if (low < high)
swap(A[low], A[high]);
} while (low < high);
swap(A[left], A[high]);
return high;
}
void quickSort (int A[], int left, int right) {
if (left < right){
int q = partition(A, left, right);
quickSort(A, left, q - 1);
quickSort(A, q + 1, right);
}
}
우선순위 큐는 다양한 방법(배열, 연결리스트, ...)으로 구현할 수 있지만 가장 효율적인 구조는 힙(Heap)이다.
이런 우선순위 큐는 어떤 요소가 먼저 삭제될 것인지에 따라 다음 2가지로 나뉜다.
최대 우선순위 큐: 우선순위가 가장 높은 것 먼저 삭제 최소 우선순위 큐: 우선순위가 가장 낮은 것 먼저 삭제
※ 힙 (Heap)
힙 (heap)은 완전 이진트리(complete binary tree)의 일종으로 우선순위 큐를 위해 만들어진 자료구조다.
힙(heap)은 요소들이 완전히 정렬된 것은 아니지만 일종의 반 정렬상태를 유지한다. 이로 인해 삽입 삭제의 시간복잡도가 O(log n)으로 다른 방법보다 훨씬 유리하다.
이런 힙은 여러 개의 값들 중 최댓값과 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조이다. 이를 위해 부모 노드의 key 값 > 자식 노드의 key 값 을 항상 만족하도록 만들어졌다. (보통 최대힙으로 가정하는 편) 단, BST와는 다르게 Heap tree는 중복된 값을 허용한다.
- 최대 힙 (max heap)
key(부모) ≥ key(자식)
- 최소 힙 (min heap)
key(부모) ≤key(자식)
✯ 힙의 기본 틀
왼쪽 자식의 index = 부모 index * 2 오른쪽 자식의 index = 부모 index* 2 + 1
∴ 부모의 index = 자식의 index / 2
※ MaxHeap의삽입연산 (insert)
힙에 새로운 요소가 들어오면 1. 힙의 마지막 노드에 이어서 새 노드를 삽입 2. 삽입 후 새 노드를 부모노드와 교환하여 힙의 성질을 만족시켜준다.
✯ BST의 insert Algorithm
insert (key)
heapSize <- heapSize + 1;
i <- heapSize;
node[i] <- key;
while i != 1 and node[i] > node[PARENT(i)] do
node[i] ↔ node[PARENT(i)]; // 노드를 서로 교환
i <- PARENT(i);
※ MaxHeap의삭제연산 (delete)
1. 먼저 root노드 삭제 후, 빈 루트에 힙의 마지막 노드를 가져 온다. (레벨순회 순 마지막 노드) 2. 순차적으로 강등 진행 (자식들 중 더 큰 값과 교환 진행)
✯ BST의 delete Algorithm
remove()
item <- A[1];
A[1] <- A[HeapSize];
i <- 2;
while i ≤ heapSize do
if i <heapSize nad A[LEFT(i)] > A[RIGHT(i)]
then largest <- LEFT(i);
else largest <- RIGHT(i);
if A[PARENT(largest)] > A[largest]
then break;
A[PARENT(largest)] ↔ A[largest];
i <- LEFT(largest);
return item;
※ MaxHeap 구현
- HeapNode.h
#include <iostream>
#define MAX_ELEMENT 200 // heap array size
using namespace std;
template <typename T>
class Node{
private:
int key;
T data;
public:
Node(){ key = 0; }
Node(int key, T _data){
this->key = key;
this->data = data;
}
~Node(){}
// getter/setter
int getKey(){ return key; }
void setKey(int key){ this->key = key; }
T getData(){ return data; }
void setData(T data){ this->data = data; }
};
template <typename T>
class MaxHeap{
private:
Node<T> node[MAX_ELEMENT];
int size; // heap 요소 개수
public:
MaxHeap(){ size = 0; }
~MaxHeap(){}
// search node
Node<T>& getParent(int index){
return node[index/2];
}
Node<T>& getLeftChild(int index){
return node[index*2];
}
Node<T>& getRightChild(int index){
return node[index*2+1];
}
// 삽입
void insert(int key, T data){
if(isFull()){
cout << "Heap is Full" << endl;
return;
}
int index = ++size; // 힙트리 마지막 노드의 다음 위치에서 시작
// 힙트리를 거슬러 올라가며 부모 노드와 비교
while(index != 1 && key > getParent(index).getKey()){
node[index] = getParent(index);
index /= 2;
}
// 최종 위치에 데이터 삽입
node[index].setKey(key);
node[index].setData(data);
}
// 삭제
T remove(){
if(isEmpty()){
cout << "Heap is Empty" << endl;
exit(EXIT_FAILURE);
}
Node<T> itemNode = node[1]; // root node (삭제 대상)
Node<T> lastNode = node[size--]; // 힙트리의 마지막 노드
int index = 1; // 마지막 노드의 index (root 부터 시작)
// root 부터 내려가며 자식 노드와 비교
while(index <= size){
if(index*2 > size){ // leaf node인 경우 (자식 노드가 없는 경우)
break;
}
else if(index*2 == size){ // 자식노드가 하나인 경우
if(lastNode.getKey() < getLeftChild(index).getKey()) {
node[index] = getLeftChild(index);
index *= 2;
}
else
break;
}
else{ // 자식노드가 두개인 경우
int leftChildKey = getLeftChild(index).getKey();
int rightChildKey = getRightChild(index).getKey();
// 둘 중 key가 더 큰 자식노드와 교환
if(lastNode.getKey() < leftChildKey || lastNode.getKey() < rightChildKey){
node[index] = leftChildKey > rightChildKey ? getLeftChild(index) : getRightChild(index);
index = leftChildKey > rightChildKey ? index*2 : index*2+1;
}
else
break;
}
}
node[index] = lastNode; // 마지막 노드를 최종 위치에 저장
return itemNode.getData(); // 삭제 노드의 data 반환
}
// 출력
void display(){
int level = 1;
for(int i=1; i<= size; i++){
if(i == level){
cout << endl;
level *= 2;
}
cout << node[i].getData() << "(" << node[i].getKey() << ") ";
}
cout << '\n' << "-------------------------" << endl;
}
bool isEmpty(){ return size == 0; }
bool isFull(){ return size == MAX_ELEMENT - 1; }
};
search (root, key)
if root == null
then return null;
if key = KEY(root)
then return root;
else if key < KEY(root)
then return search(LEFT(root), key);
else return search(RIGHT(root), key);
key값으로 node를 탐색하는 함수로 2가지 방식으로 구현이 가능하다.
- 순환적인 방법
BinaryNode *search(BinaryNode *n, int key){
if (n == NULL) return NULL;
if (key == n->getData()) return n; // key == 현재 node의 data
else if (key < n->getData()) return search(n->getLeft(), key); // key < 현재 node의 data
else return search(n->getRight(), key); // key > 현재 node의 data
}
- 반복적인 방법 (효율성의 측면에서 훨씬 우수)
BinaryNode *search(BinaryNode *n, int key){
while(n != nullptr){
if(key == n->getData())
return n;
else if(key < n->getData())
n = n->getLeft();
else
n = n->getRight();
}
return nullptr;
}
※ BST의 삽입연산 (insert)
BST에서 삽입을 위해 탐색이 선행되어야 한다!
( ∵ BST에서는 같은 key값을 갖는 node가 없어야 하기 때문! )
( ∵ BST에서는탐색에 실패한 위치 = NULL값 = new node를 insert하는 위치 )
✯ BST의 insert Algorithm
insert (root, n)
if KEY(n) == KEY(root)
then return;
else if KEY(n) < KEY(root) then
if LEFT(root) == null
then LEFT(root) <- n;
else insert(LEFT(root), n);
else
if RIGHT(root) == null
앞의 두 연산보다 더욱 중요한 연산으로 BST에서 가장 복잡한 연산이다. 다음 3가지의 경우를 고려해야 하기 때문이다.
case1. 삭제하려는 node가 leaf node인 경우. --> 그냥 삭제하면 되서 가장 간단! case2. 삭제하려는 node가 왼쪽이나 오른쪽 sub tree중 하나만 갖는 경우 --> 해당 sub tree를 부모로! case3. 삭제하려는 node가 양쪽 sub tree 모두 갖는 경우 --> 가장 복잡!
➣ case 1. 삭제 node가 leaf node
i) 부모 노드를 찾아서 ii) 부모 노드의 link 영역을 nullptr로 만든다. iii) leaf node를 최종적으로 동적으로 해제한다. 즉, 부모 노드를 반.드.시! 알아야 한다!
➣ case 2. 삭제 node가 sub tree 하나만 갖고 있음
i) 해당 노드는 삭제하고 ii) 유일한 자식을 부모 노드에 붙여준다. 즉, 부모와 자식노드를 둘 다! 알아야 한다!
➣ case 3. 삭제 node가 sub tree 모두 갖고 있음
가장 핵심은 "삭제되는 노드와 가장 값이 비슷한 노드"가 핵심! i) left sub tree의 최하단우측 node와 right sub tree의 최하단좌측 node 중 선택 (위 그림에서 30과 50중 선택) (오른쪽 서브트리의 제일 작은 값을 선택했다 가정) 이때, 여러 부모 및 자식 노드의 정보가 필요해서 매우 구현이 복잡해진다.
※ BST 구현
- BinaryNode.h
#include <iostream>
class BinaryNode{
protected:
int data;
BinaryNode* left;
BinaryNode* right;
public:
BinaryNode(int val = 0, BinaryNode *l = nullptr, BinaryNode *r = nullptr) : data(val), left(l), right(r) { }
void setData(int val) { data = val; }
void setLeft(BinaryNode* l) { left = l; }
void setRight(BinaryNode* r) { right = r; }
int getData() const { return data; }
BinaryNode* getLeft() const { return left; }
BinaryNode* getRight() const { return right; }
bool isLeaf() const { return left == nullptr && right == nullptr; }
};
트리의 높이를 h라 할 때, 일반적인 선형자료구조의 경우 O(h)가 된다. 이진트리의 경우, 보통 트리의 높이가 log h가 되므로 평균적인 시간복잡도는 O(log n)으로 매우 탁월함을 보여준다.
다만 이런 이진탐색트리의 경우 트리가 간혹 좌우로 불균형해져 트리의 높이가 log n이 만들어 지지 않는 경우가 발생할 수 있다. 이를 보완하는 방법으로 트리의 높이를 항상 log n으로 한정시키는 AVL 트리가 있다. Adelson Velskii Landis tree는 이진탐색트리의 노드의 불균형 문제를 해결한 트리로 밑에서 설명하겠다.
※ AVL 트리 (AdelsonVelskiiLandis Tree)
AVL 트리는 왼쪽과 오른쪽 sub tree간의 높이차가 1 이하인 BST이다. 이를 통해 O(log n)의 시간을 항상 보장한다!
탐색연산은 BST와 동일하지만 삽입, 삭제의 경우가 균형이 깨지기에 AVL 트리는 삽입과 삭제에 추가적 연산을 진행한다.
이런 균형이 깨진 트리를 다시 균형있게 만드는 방법으로 다음 4가지 방법이 있다.
새로 삽입된 노드 N과 N에서 가장 가까운 조상 노드 A에 대해 ‣ LL 타입: N이 A의 왼쪽 sub tree의 왼쪽 sub tree로 삽입 ‣ LR 타입: N이 A의 왼쪽 sub tree의 오른쪽 sub tree로 삽입 ‣ RR 타입:N이 A의 오른쪽 sub tree의 오른쪽 sub tree로 삽입 ‣ RL 타입:N이 A의 오른쪽 sub tree의 왼쪽 sub tree로 삽입
‣ LL 회전: 오른쪽으로 회전 ‣ LR 회전: 왼쪽-오른쪽으로 회전 ‣ RR회전: 왼쪽으로 회전 ‣ RL 회전: 오른쪽-왼쪽으로 회전
✯ AVL Tree의 Rotate Algorithm
☞ 단순 회전 알고리즘(LL, RR)
rotate_LL(A)
B <- A의 왼쪽 자식
B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
A를 B의 오른쪽 자식 노드로 만든다.
rotate_RR(A)
B <- A의 오른쪽 자식
B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.
A를 B의 왼쪽 자식 노드로 만든다.
☞ 이중 회전 알고리즘 (RL, LR)
rotate_RL(A)
B <- A의 오른쪽 자식
rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
rotate_LR(A)
B <- A의 왼쪽 자식
rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
rotate_LL(A)
