1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
큐
- 선입출 방식
- 전 데이터를 저장하고 주어진 순서에 따라 순서를 바꾸지 않고 해결할 때 가장 사용을 많이 하는 자료구조다.
- 문제에서 원이나 순서, 입력 순서 등의 키워드가 언급될 때 처음 순서를 저장하고 싶을 때 쓴다.
- 파이썬의 경우 큐는 collection의 deque를 이용, popleft() 등을 통해 구현이 가능해서 리스트를 쓴다.
- 보통 in 함수를 사용해서 if의 조건문을 구성해서 이것이 있는지 없는지 체킹하는 방식이 주류다.
예제) 교육과정 설계(큐)
현수는 1년 과정의 수업계획을 짜야 합니다.
수업중에는 필수과목이 있습니다. 이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있습니다.
만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어지면 필수과목은C, B, A과목이며
이 순서대로 꼭 수업계획을 짜야 합니다.
여기서 순서란 B과목은 C과목을 이수한 후에 들어야 하고, A과목은 C와 B를 이수한 후에 들어야 한다는 것입니다.
현수가 C, B, D, A, G, E로 수업계획을 짜면 제대로 된 설계이지만
C, G, E, A, D, B 순서로 짰다면 잘 못 설계된 수업계획이 됩니다.
수업계획은 그 순서대로 앞에 수업이 이수되면 다음 수업을 시작하다는 것으로 해석합니다.
수업계획서상의 각 과목은 무조건 이수된다고 가정합니다.
필수과목순서가 주어지면 현수가 짠 N개의 수업설계가 잘된 것이면 “YES",
잘못된 것이면 ”NO“ 를 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 줄에 한 줄에 필수과목의 순서가 주어집니다. 모든 과목은 영문 대문자입니다.
두 번째 줄에 N(1<=N<=10)이 주어집니다.
세 번 째 줄부터 현수가 짠 N개의 수업설계가 주어집니다.(수업설계의 길이는 30이하이다)
수업설계는 같은 과목을 여러 번 이수하도록 설계해도 됩니다.
▣ 출력설명
수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력합니다.
▣ 입력예제 1
CBA
3
CBDAGE
FGCDAB
CTSBDEA
▣ 출력예제 1
#1 YES
#2 NO
#3 YES
▣ 입력예제 2
AFC
1
AFFDCCFF
▣ 출력예제 2
#1 YES
해설)
주어진 스트링 객체(필수 교육과정)의 순서를 지키면서 인덱싱을 하기 위해서는 deque화 시켜 큐와 같이 사용 해야한다.
검사할 계획에 1. 만약 검사할 교육과정의 원소가 필수 교육과정에 포함되어 있다면 -> 2. 필수 교육과정의 앞 원소를 popleft()한 것이(여기서 popleft()를 이미 한 상태이니 순서가 지켜진다.) for문을 도는 원소와 같지않다면 = NO
이외에 만약 필수 교육과정 큐에 원소가 남아 있다면 NO, 없다면 YES 이런 로직이 된다.
need = input()
n = int(input())
# 파이썬에서는 for - else 가 있다.
# 입력 순서 그대로 지켜야한다. -> 큐
# 아니다 선위 -> 후위 같이 순서를 바꿔야한다. -> 스택
# for문과 같이 사용되는 else문은
# for문이 break 등으로 중간에 빠져나오지 않고
# 끝까지 실행 됐을 경우 else문이 실행되는 방식으로 진행됩니다.
for i in range(n):
plan = input()
# 스트링 객체를 넣어도 deque함수를 쓸 수 있다.
dq = deque(need)
for x in plan:
# in 외워두기, 핵심
# x가 C B A 에 있냐?
if x in dq:
if x!=dq.popleft():
print(f"#{i+1} NO")
break
# break가 즐어간 if문이 실행이 되지 않았을 때 실행
# 정상적으로 출력한 뒤에 마지막 체크시 사용
else:
if len(dq)==0:
print(f"#{i+1} YES")
else:
print(f"#{i+1} NO")
해쉬 Hash
- Key - Value 방식, 각언어마 자바에서는 Map, 파이썬에서는 Dictionary 형식의 데이터 구조가 있다.
- 키와 벨류를 저장하여 특정 데이터를 조회할 때 키를 통해 조회할 때 사용한다.
- 문제에서 사전 형식과 같이 단어를 찾거나 단어의 특정 횟수 체킹, 아나그램(이것도 특정 문자 횟수 체킹이다.)에 사용한다.
- 파이썬의 경우 해쉬는 Dictionary 데이터 구조로 구현이 가능해서 {}, dict()를 사용해서 구현한다.
- 특정 문자나 단어가 속해있는지, 혹은 문자의 출현횟수를 체킹하기 때문에 dict.items(), dict[word] = dict.get(word,0)+1 과 같은 함수를 쓴다.
예제) 아나그램(해쉬)
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만
그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다.
즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다.
▣ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다.
단어의 길이는 100을 넘지 않습니다.
▣ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.
▣ 입력예제 1
AbaAeCe
baeeACA
▣ 출력예제 1
YES
해설)
아나그램을 확인하므로 두 단어가 주어질 때 각 단어들에 대한 딕셔너리들을 선언하고 문자-횟수로 체킹을 해야한다. 그러고나서 두 딕셔너리를 서로 비교하면서 in함수를 통해 같은 키가 존재하는지, 존재한다면 그에 대한 벨류값이 같은지 체킹한다.
혹은 하나의 딕셔너리를 선언하고 첫 단어 때는 문자마다 류값을 1씩 더하고, 두번째 단어애서는 문자마다 벨류값을 1씩 빼주면서 결과적으로 딕셔너리의 모든 값들이 0이 되어있으면 YES 아니면 NO를 체킹한다.
# 해쉬 -> 딕셔너리
# 자바 해쉬맵 -> 딕셔너리
# 어떻게 보면 json이다.
word_one = input()
word_two = input()
dct_one = {}
dct_two = {}
# for char in word_one:
# dct_one[char] = 0
# for char in word_one:
# dct_one[char]+=1
# 위 계산이 아래에서 한 방에 해결된다.
# char라는 키가 있으면 1을 더하고 없으면 0을 기본값으로 넣어라
for char in word_one:
dct_one[char] = dct_one.get(char,0)+1
# for key, val in dct_one.items():
# print(key,val)
# print("\n")
# for char in word_two:
# dct_two[char] = 0
# for char in word_two:
# dct_two[char]+=1
# 위 계산이 아래에서 한 방에 해결된다.
# char라는 키가 있으면 1을 더하고 없으면 0을 기본값으로 넣어라
for char in word_two:
dct_two[char] = dct_two.get(char,0)+1
# for key, val in dct_two.items():
# print(key,val)
# 핵심 알고리즘
# 키값만 접근하고 싶다.
# 큐도 그렇고 in이라는 함수가 중요하다.
# in을 생각하면 어디 어디에 있냐 이게 떠올려진다.
for i in dct_one.keys():
# word_one에는 있는데 word_two에는 없으면 안된다.
# 아나그램은 모든 원소들이 같이 존재해야하는 것이다.
if i in dct_two.keys():
# 갯수 비교
if dct_one[i] != dct_two[i]:
print("NO")
break
else:
print("NO")
break
# 정상 케이스
else:
print("YES")
# 위랑 아래를 비교해봅시다.
print("\n")
Hash = {}
# 개선 코드
for char in word_one:
Hash[char] = Hash.get(char,0)+1
print(Hash)
for char in word_two:
Hash[char] = Hash.get(char,0)-1
# 이러면 하나의 딕셔너리를 이용해서 풀 수 있다.
print(Hash)
for x in word_one:
if Hash.get(x) != 0:
print("NO")
break
else:
print("YES")
힙 Heap
- 완전이진트리로 구현된 자료구조로 최소힙 정렬일 때는 자식 노드보다 작은 수가 부모노드가 되고 최대힙 정렬일 때는 자식 노드보다 값이 큰 수가 부모 노드가 된다.
- 파이썬의 경우 힙은 heapq클래스의 heappop(), heappush()으로 구현이 가능해서 리스트 선언 후 두 함수를 통해 구현한다.
- 이진트리의 힙 정렬이 필요할 때 사용한다. 기본적으로 파이썬에서 heapq클래스는 최소힙을 가정하고 함수를 돌린다.
- 즉, 최대 힙을 구현할 때는 heappush()할 때 - 부호를 붙여서 정렬하고 빼낼 때 -(heapq.heappop())와 같이 빼내면 최대힙 효과를 보여줄 수 있다는 것이다.
예제) 최대힙(힙)
최대힙은 완전이진트리로 구현된 자료구조입니다.
그 구성은 부모 노드값이 왼쪽자식과 오른쪽 자식노드의 값보다 크게 트리를 구성하는 것입니다.
그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 큰 값이 저장되어 있습니다.
예를 들어 5 3 2 1 4 6 7순으로 입력되면 최대힙 트리는 아래와 같이 구성됩니다.
최대힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요.
1) 자연수가 입력되면 최대힙에 입력한다.
2) 숫자 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.)
3) -1이 입력되면 프로그램 종료한다.
▣ 입력설명
첫 번째 줄부터 숫자가 입력된다. 입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정수형 범위에 있다.
▣ 출력설명
2) 연산을 한 결과를 보여준다.
▣ 입력예제 1
5
3
6
0
5
0
2
4
0
-1
▣ 출력예제 1
6
5
5
# 최대힙은 최소힙에서 약간 변경만 하면 된다.
import heapq as hq # 파이썬에서는 힙큐라는 것이 존재한다.
# heapq는 기본적으로 최소 힙으로 작동한다.
# 최대힙의 효과를 내려면 입력을 할 때 부호를 바꿔버려야한다.
# 예를 들어 3과 4를 넣어버리면 최소힙일 때는 그대로 3 - 4 가 되겠지만
# 마이너스 부호를 붙여서 넣으면 -3 - -4가 되어 한 번 스왑을 해야한다.
# -> -4 - -3
# 그다음 hp.heappop()을 할 때 다시 마이너스를 붙여서 꺼내면
# -(-4) = 4 가 되어서 정상 출력이 된다.
# 즉 힙큐에서 저장하고 있을 때는 모든 원소가 - 부호를 가지고 있는 것이다.
# 그 상태로 힙정렬을 하면 부호가 없는 상태에서는
# 최대힙의 성질을 가지고 있는 것이다.
a = []
while True:
n = int(input())
if n == -1:
break
if n == 0:
if len(a) == 0:
print(-1)
else:
print(-(hq.heappop(a))) # 이 때가 중요
else:
hq.heappush(a, -n) # 이 떄가 중요
# 즉 이진트리의 힙 로직은 최소힙인데
# 입력과 출력에서 부호를 반대로 바꾸어 주기 때문에
# 결과적으로 최대 힙의 효과를 내는 것이다.