베이즈 정리는 두 확률 변수의 사전 확률과 사후 확률사이의 관계를 나타내는 정리이다. 뭔 개소리임? ㅈㅅ 나도 이해를 못했음. 사전 확률(기존 믿음)과 새로운 정보(증거)를 결합하여 사후 확률(갱신된 믿음)을 계산하는 확률론적 방법이라고 하는데 이것도 확 와닿는 얘기는 아니었습니다.
이거 공식은 되게 심플... 할수도 있고 아닐수도 있음.
공식이 이게 다인데 보통 P(B)는 안준다. 그래서 저걸 또 전확률의 정리? 그걸 써서 구해야된다. 근데 저 바는 뭔데요? 조건부확률(P(A|B) = 어떤 사건(B)이 이미 일어났다는 전제 하에, 다른 사건(A)이 일어날 확률)이다. 그 생선님이 유튜브에 올린거 보면 비유를 개찰떡으로 해놨는데 봅시다.
어떤 게임의 가챠 확률표에서 SSR 확률이 0.001%이고 SSR 캐릭터가 다섯일 때 전체 캐릭터 풀에서 내가 원하는 SSR이 나올 확률하고 SSR을 뽑았을 때 내가 원하는 SSR이 나올 확률하고 다르잖아요. 전체 확률에서 내가 원하는 쓰알을 뽑을라면 0.001에 1/5을 곱해야되지만 이미 쓰알을 뽑았을때는 쓰알들 '중에서' 하나 내가 원하는거 딱 나오면 되니까 1/5지.
비슷하게 소드실드 5성 2% 미로치 확정굴도 '5성이 떴을때' 2%인 조건부확률이다. 그래서 실제 확률은 진짜 낮기때문에 날짜를 돌려가면서 그 개노가다를 하는 것이다. 시드 계산인가 있지 않냐고? 이벤굴은 그거 안된다.
# 베이즈 정리: 어떤 사건이 서로 배반하는 원인 둘에 의해 일어난다고 할 때 실제 사건이 일어났을 때 이것이 두 원인 중 하나일 확률을 구하는 정리
# 공식: P(A|B) = P(B|A) * P(A) / P(B)
# P(A): 사전확률
# P(B): 주변 우도(marginal likelihood)
# P(A|B): B의 값이 주어졌을 때 A의 사후 확률(여기서 구해야 하는 거))
# P(B|A): A가 주어졌을 때 B의 조건부 확률
# P(B|not A): A가 주어지지 않았을 때 B의 조건부 확률
# 함수 매개변수: P(A), P(B|A), P(B|not A) 순서대로 입력해주세요
def bayes_theorem(prior, sensitivity, false_positive):
# P(B)
# P(B) = P(B|A) * P(A) + P(B|not A) * P(not A) (전확률의 정리인가 있음 아무튼)
marginal_likelihood = (prior * sensitivity) + ((1 - prior) * false_positive) # P(B)를 계산해야 함
# P(A|B)
# P(A|B) = P(B|A) * P(A) / P(B) (위에 공식 써있음)
posterior = (prior * sensitivity) / marginal_likelihood
return posterior
result = bayes_theorem(0.01, 0.95, 0.05)
print(f"P(A|B): {result:.2%}")
그래서 이게 전체 코드인데... 나는 텍스트 ''로 쓰는데 제미나이는 ""로 쓰데...? 안티그래비티 자동완성도 그렇고...
# 모듈
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm # 넌 뭐냐
from Bio import Entrez, SeqIO # 왼쪽: 일단 털어보자/오른쪽: 시퀀스 다루려면 필요합니다. 필수임.
from Bio import AlignIO # 서열 분석해줄 친구
from Bio import Phylo # 트리 그릴라면 필요해요
from Bio.Phylo.TreeConstruction import DistanceCalculator, DistanceTreeConstructor
import io # 누구세요?
import subprocess # 서브 프로세스(이건 또 뭐여...)
from collections import Counter
import re
# 그래프를 그리기 위한 기본 설정
plt.rcParams['font.family'] = 'Nanumbarunpen' # 나눔바른펜(본인 기본 고딕 싫어함)
# plt.rcParams['font.family'] = 'AppleGothic'
plt.rcParams['font.size'] = 14
plt.rcParams['axes.unicode_minus'] = False
# 사전세팅
Entrez.email = "blackholekun@gmail.com" # 이메일
muscle_exe = "/opt/homebrew/bin/muscle" # 이거 경로 있어야 써요(which 치면 나옴)
여긴 다 아니까 넘어갑시다. 본인은 고딕 자체를 딱딱해서 별로 안 좋아하지만 특히나 기본 고딕(맑은고딕, 애플고딕)을 증말 싫어하고 그나마 뭐 제출하는 자리에서 타협보는게 나눔고딕, 나눔스퀘어, 프리텐다드다. 기본고딕은 뭔가 기깔나지 아니함.
# 인플루엔자 H3N2 서열 가져오기
# 쿼리 조건: 인플루엔자 A, 특정 아형, HA 유전자, 최근 1년(2025), 호스트가 사람
query = f"Influenza A virus AND H3N2 AND HA[Gene Name] AND 2025[PDAT] AND Homo sapiens[Host]" # 사람독감 찾으려면...
# 1. ID 리스트 가져오기
handle = Entrez.esearch(db="nucleotide", term=query, retmax=160)
record = Entrez.read(handle)
id_list = record["IdList"]
handle.close()
# 2. 실제 서열 데이터 가져오기 (FASTA 형식)
fetch_handle = Entrez.efetch(db="nucleotide", id=id_list, rettype="fasta", retmode="text")
sequences = list(SeqIO.parse(fetch_handle, "fasta"))
fetch_handle.close()
# 3. 저장
with open("influenza_h3n2.fasta", "w") as f:
SeqIO.write(sequences, f, "fasta")
print(f"성공적으로 {len(sequences)}개의 서열을 가져왔습니다.")
print("----------")
for record in sequences[:3]:
print(f"ID: {record.id}")
print(f"Description: {record.description}")
print(f"Length: {len(record.seq)} bp\n")
쿼리가 좀 길죠? 일단 쿼리 내용을 뜯어보자.
Influenza A virus AND H3N2 AND HA[Gene Name] AND 2025[PDAT] AND Homo sapiens[Host]
1. Influenza A virus AND H3N2: 인플루엔자 H3N2(인플루엔자 바이러스는 밖에 나와있는 해마글루티닌과 뉴라미니데이스 번호로 지칭함... H5N1: 해마5 뉴라1)
2. HA[Gene Name]: 해마글루티닌으로 찾는다는 얘기다. 이놈은 게놈에 헤마글루티닌, 뉴라미니데이스, 뉴클레오프로틴, M1, M2, NS1, NS2(NEP), PA, PB1, PB1-F2, PB2가 있고 인플루엔자 데이터가 급나 많기때문에... 그리고 다른거 섞여들어가면 MSA 개발살남.
3. 2025[PDAT]: 작년에 유행했던 것들. 저걸 안 달면 온갖가지 시즌에 유행했던 인플루엔자 데이터가 다 나온다.
4. Homo sapiens[Host]: 숙주가 사람인... 그니까 사람한테 감염되는 바이러스 정보. 저거 안 하면 어떻게 되냐고요? 개 인플루엔자 나옵니다.
# 사전통계-어느 지역 데이터를 얼마나 긁어왔는가?
locations = []
for record in sequences:
# Description에서 괄호 안의 지역 정보 추출 (예: A/Shanghai/...)
match = re.search(r'A/([^/]+)/', record.description)
if match:
locations.append(match.group(1))
# 지역별 빈도수 확인
location_counts = Counter(locations)
print("--- 수집된 데이터 지역 분포 ---")
for loc, count in location_counts.most_common():
print(f"{loc}: {count}개")
갖고 온 데이터에서 유행한 지역 비율을 구하는 코드이다. 콜로라도 몇건, 상하이 몇건, 이런 식으로.
--- 수집된 데이터 지역 분포 ---
Rhode Island: 36개
Michigan: 21개
New York: 16개
Wisconsin: 11개
Pennsylvania: 11개
Izmir: 10개
Massachusetts: 9개
Virginia: 7개
North Carolina: 7개
Tennessee: 7개
Shanghai: 6개
Colorado: 6개
Maryland: 6개
California: 5개
Minnesota: 5개
Washington: 4개
Vermont: 4개
Texas: 3개
North Dakota: 3개
Nebraska: 3개
New Jersey: 3개
Nevada: 2개
Missouri: 2개
West Virginia: 2개
Oregon: 2개
Jinan: 1개
Utah: 1개
New Mexico: 1개
Connecticut: 1개
Yigo: 1개
Ohio: 1개
New Hampshire: 1개
Louisiana: 1개
Kentucky: 1개
야 이건 웬일로 글자제한 안짤리네. (네이버 얘기)
# 지역별 라벨링(함수)
def clean_flu_labels(sequences):
for record in sequences:
# 1. 지역 추출 (A/지역/...)
loc_match = re.search(r'A/([^/]+)/', record.description)
location = loc_match.group(1) if loc_match else "Unknown"
# 2. 연도 추출 (4자리 숫자)
year_match = re.search(r'/(\d{4})', record.description)
year = year_match.group(1) if year_match else "XXXX"
# 3. 새로운 ID 생성 (예: 2023_Shanghai_H3N2)
# 나중에 트리에 그릴 때 가독성을 위해 짧고 강렬하게!
record.id = f"{year}_{location}"
record.description = record.id # 설명도 통일
return sequences
# 라벨 정리 실행
labeled_sequences = clean_flu_labels(sequences)
# 확인
for r in labeled_sequences[:5]:
print(r.id)
이건 내가 갖고 온 데이터가 언제, 어디서 유행한 인플루엔자에 대한 데이터인지 라벨링하는 절차다.
print('MSA start... ')
# MSA 분석 시-작
try:
result = subprocess.run([muscle_exe, "-align", "influenza_h3n2.fasta", "-output", "influenza_h3n2_muscle_aligned.fasta"], check=True, capture_output=True, text=True)
print("Completed. ")
except subprocess.CalledProcessError as e:
print(f"MSA failed: {e}")
finally:
alignment = AlignIO.read("influenza_h3n2_muscle_aligned.fasta", "fasta")
# 오래 걸리니까 이거 돌려놓고 잠깐 바람 쐬고 오십쇼
오래걸리니까 이거 돌려놓고 똥 함 때리고 오시면 되겠습니다. 저 예외처리에 파이널리는 마지막에 해야 하는거다.
print("====== MSA Result ======")
alignment = AlignIO.read("influenza_h3n2_muscle_aligned.fasta", "fasta") # FASTA 니네 확장자가 몇개냐...
for record in alignment:
print(f"{record.id[:15]:<15} : {record.seq[:100]}")
# 엔트로피 점수 도출
def get_top_variable_sites(alignment, top_n=5):
length = alignment.get_alignment_length()
variability = []
for i in range(length):
column = alignment[:, i]
# 가장 많이 등장하는 염기 비율 계산
most_common_ratio = column.count(max(set(column), key=column.count)) / len(column)
variability.append((i, 1 - most_common_ratio))
# 변이율이 높은 순으로 정렬
return sorted(variability, key=lambda x: x[1], reverse=True)[:top_n]
top_sites = get_top_variable_sites(alignment)
print("--- 변이가 집중된 주요 포지션 ---")
for pos, score in top_sites:
print(f"Position {pos}: 변이율 {score*100:.1f}%")
그 엔트로피… 여기서도 함 해봅시다. 한타때도 얘기했지만 바이러스라고 해서 아무데나 막 변이하지 않습니다. 증식에 영향을 안 끼치는 것도 있고 잘못하면 지가 X되는 변이도 있거든…
--- 변이가 집중된 주요 포지션 ---
Position 1734: 변이율 56.5%
Position 16: 변이율 50.0%
Position 17: 변이율 50.0%
Position 18: 변이율 50.0%
Position 19: 변이율 50.0%
백몇개 돌렸을때랑 다른데?
align = AlignIO.read("influenza_h3n2_muscle_aligned.fasta", "fasta")
length = align.get_alignment_length()
n_seqs = len(align)
entropy_list = []
for i in range(length):
col = align[:, i]
# 각 자리의 염기 조성 확인
chars = set(col)
probs = [col.count(c) / n_seqs for c in chars]
# 샤논 엔트로피 계산 (변이의 척도)
entropy = -sum(p * np.log2(p) for p in probs if p > 0)
entropy_list.append(entropy)
plt.figure(figsize=(20, 6))
plt.plot(entropy_list, color='darkblue', linewidth=1)
plt.fill_between(range(length), entropy_list, color='skyblue', alpha=0.4)
plt.title("H3N2 HA Sequence Entropy (Prediction Map)", fontsize=15)
plt.xlabel("Amino Acid Position")
plt.ylabel("Entropy (Mutation Intensity)")
plt.grid(axis='y', linestyle='--', alpha=0.7)
plt.show()
빗이야 뭐야... 쩌기 1750 언저리 보이시죠? 500 좀 가서 하나 더 있고. 저기가 엔트로피가 높다는 얘기는 변이율이 높다는 얘기다. 그니까 슈뢰딩거도 까봐야 안다 이거지.
# 트! 리!
calculator = DistanceCalculator('identity')
dm = calculator.get_distance(alignment)
constructor = DistanceTreeConstructor(calculator, 'nj')
tree = constructor.build_tree(alignment)
terms = tree.get_terminals()
x_limit = max([tree.distance(t) for t in terms])
fig = plt.figure(figsize=(20, 60), dpi=150) # 난 해상도 설정도 될 줄 몰랐고...
ax = fig.add_subplot(1, 1, 1)
for clade in tree.get_terminals():
original_name = str(clade.name)
if '_' in original_name:
parts = original_name.split('_')
clade.name = f"[{parts[0]}] {parts[1]} ({original_name})"
else:
clade.name = original_name
Phylo.draw(tree, axes=ax, do_show=False, label_func=lambda x: "", show_confidence=False)
# 내가 진짜 이것때문에 제미나이랑 급나 씨름했는데 색깔이 안바껴요.
# 이름도 몇번이나 했는데 ID만 줄창떠요. 아오.
for i, node in enumerate(terms):
y_pos = i + 1 # 가지의 y축 위치
x_pos = tree.distance(node) # 가지가 끝나는 x축 위치
orig_name = str(node.name)
# 이름 가공: [연도] 지역 (ID)
if '_' in orig_name:
p = orig_name.split('_')
# 혹시 이미 가공된 이름이라면 중복 방지
display_text = f" ◀ [{p[0]}] {p[1]}" if '[' not in orig_name else f" ◀ {orig_name}"
else:
display_text = f" ◀ {orig_name}"
# 가지 끝(x_pos)에 바로 텍스트를 박습니다.
ax.text(x_pos, y_pos, display_text,
va='center', ha='left',
fontsize=14, color=color,
fontweight='bold' if "LC909067" in orig_name else 'normal')
ax.set_xlim(0, x_limit * 1.8)
ax.set_ylim(0, len(terms) + 2)
ax.set_axis_off() # 축 숫자 빠잉
plt.rc('font', size=14) # 내부 글꼴 사이즈
plt.rc('axes', titlesize=20) # 제모옥은 이 크기로 하겠습니다
plt.title("Influenza A (H3N2) HA Phylogenetic Tree by Region/Year")
plt.tight_layout()
plt.savefig("Influenza_H3N2_Final_Tree.png", dpi=300, bbox_inches='tight')
plt.xlabel("Genetic Distance (Substitutions per site)")
plt.show()
길고 아름다운 트리를 볼 준비가 되셨습니까?
안됐어도 봐야됨.
종으로 필터링 안했을때는 생뚱맞게 개 독감 하나 튀어나와서 저기 어디 지 혼자 떨어져있었음.
# 사람을 공격하는 바이러스만 찾습니다
human_terms = [t for t in tree.get_terminals() if 'canine' not in str(t.name).lower()]
# 유전적 거리순으로 정렬
human_distances = [(tree.distance(t), t.name) for t in human_terms]
human_distances.sort(key=lambda x: x[0], reverse=True)
print("=== 🚨 독감 변종 TOP 5 ===")
print("-" * 70)
print(f"{'순위':<4} | {'ID':<12} | {'변이도':<8} | {'신상 정보'}")
print("-" * 70)
for i, (dist, name) in enumerate(human_distances[:5], 1):
target_id = str(name)
found_info = "정보 없음"
# alignment 데이터에서 상세 지역/연도 정보 매칭
for record in alignment:
if target_id in record.description or target_id in record.id:
full_info = record.description if record.description else record.id
if '_' in full_info:
parts = full_info.split('_')
found_info = f"[{parts[0]}] {parts[1].split(' ')[0]}"
else:
# description에서 연도/지역 추출 시도 (괄호 안 정보 등)
found_info = full_info.split('virus (')[1].split(')')[0] if '(' in full_info else full_info
break
print(f"{i:<5} | {target_id:<12} | {dist:.4f} | {found_info}")
print("-" * 70)
print("※ 변이도가 높을수록 기존 면역 체계를 회피할 가능성이 큽니다.")
=== 🚨 독감 변종 TOP 5 ===
----------------------------------------------------------------------
순위 | ID | 변이도 | 신상 정보
----------------------------------------------------------------------
1 | PV570275.1 | 0.0891 | A/Shanghai/B623090301/2023(H3N2
2 | PQ483286.1 | 0.0630 | [PQ483286.1 Influenza A virus (A/Jinan/JN] 06/2019(H3N2))
3 | OP847955.1 | 0.0575 | A/Izmir/45/2019(H3N2
4 | OP848003.1 | 0.0493 | A/Izmir/7/2020(H3N2
5 | PV570299.1 | 0.0493 | A/Shanghai/B622090701/2022(H3N2
----------------------------------------------------------------------
※ 변이도가 높을수록 기존 면역 체계를 회피할 가능성이 큽니다.
뭐 이거 막 절대적인 척도 이런거 아니고 해마글루티닌 긁어서 봤더니 쟤가 변이도가 제일 높더라 이런겁니다. 올해 독감 백신은 제약사에서 알아서 음 이놈이군 해서 백신 만들거니까 이거 너무 맹신하지 마십쇼.
우리 여기서 MSA 돌릴 FASTA파일 저장했죠? 후편에서는 그걸로 분석을 돌릴건데… 아… 이거 트리땜에 개노가다했음… 그것도 트리 얘기하면서 얘기해드리겠음.
# 바이러스 DNA가 세그먼트별로 섞여있습니다. (S, M, L)
# 이거 분류 안하면 MSA 뻑나요.
s_segments = [rec for rec in vir_sequence if 1600 <= len(rec.seq) <= 2000]
SeqIO.write(s_segments, "hantavirus_segmemt_s.fasta", "fasta")
# 세그먼트 ID를 이름으로 바꾸는 절차라고 보시면 됩니다.
for rec in s_segments:
rec.id = f"{rec.id}_{len(rec.seq)}"
print("Completed.")
바이러스 DNA를 세그먼트별로 나눠야 한다. 왜죠? 하나의 바이러스가 여러 개의 파일(segment)로 나뉘어 있는 유전체니까요. 저게 스몰 미디엄 라지가 길이별로 다 다른데 안 나누고 묶어서 MSA 돌리잖아요? 그러면 컴퓨터가 장난 똥때리나 마!!! 하면서 갭을 긴 놈한테 맞춰서 결과가 개발살납니다.
print('MSA start... ')
# MSA 분석 시-작
try:
result = subprocess.run([muscle_exe, "-align", "hantavirus_segmemt_s.fasta", "-output", "Hantavirus_alignment_s.afa"], check=True, capture_output=True, text=True)
print("Completed. ")
except subprocess.CalledProcessError as e:
print(f"MSA failed: {e}")
2차 똥타임을 가질 수 있는 절호의 찬스. 이게 개수가 많아지면 MSA 하는데도 시간이 엄청 걸립니다. 얘는 좀 덜하긴 함… 인플루엔자는 하나 돌리는데 2~3분 걸리더라… 100갠가 갖고왔는데…
# 다 됐으면 몇 개만 확인해보자.
print("====== MSA Result ======")
alignment = AlignIO.read("Hantavirus_alignment_s.afa", "fasta") # FASTA 니네 확장자가 몇개냐...
for record in alignment:
print(f"{record.id[:15]:<15} : {record.seq[:50]}")
결과를 확인할 수 있는 코드이다. 보고 싶은 시퀀스 길이를 조절하고 싶으시다고요? record.seq[:50]를 조절하십쇼.
# 코어 시퀀스는 어디? (바이러스라고 앞뒤 안가리고 다 변형하는거 아님)
def calculate_conservation(alignment):
length = alignment.get_alignment_length()
scores = []
for i in range(length):
column = alignment[:, i]
most_common = max(column, key=column.count)
score = column.count(most_common) / len(column)
scores.append(score)
return scores
scores = calculate_conservation(alignment)
print(f"해당 구간의 평균 보존율: {np.mean(scores)*100:.2f}%")
# 변이 핫스팟 찾기 (엔트로피 분석)
variation_scores = [1 - s for s in scores] # 위에서 계산한 그거
# 핫스팟 시각화
plt.figure(figsize=(15, 5))
plt.plot(variation_scores, color='red', alpha=0.7)
plt.fill_between(range(len(variation_scores)), variation_scores, color='red', alpha=0.2)
plt.title("Viral Variation Hotspots (Potential Immune Evasion Sites)")
plt.xlabel("Sequence Position")
plt.ylabel("Mutation Frequency (Entropy)")
plt.show()
이건 또 뭐임? 바이러스가 변이율이 개삽쩌는건 다들 아시죠? 근데 얘네들도 앞뒤 안가리고 일단 변이부터 하고 보지는 않는다. 덮어놓고 변이했다가 게놈에 문제생겨서 증식을 못하거나 껍질이 제대로 안 만들어지거나 하면 바이러스 입장에서는 ㄹㅇ 초유의 사태이기 떄문이다. 그래서 얘들도 건드려도 되는 부위와 건드리면 안 되는 부위가 있거든요? 거기를 엔트로피 분석을 통해서 보는거다.
...빗이여? 근데 엔트로피는 열역학 아니예요? 그게 왜 갑자기 여기서 나옴? 뭐 바이러스가 변이할때마다 엔트로피 증가함? 아니 그거 아님. 섀넌 엔트로피, 혹은 정보 엔트로피라고 하는건데 확률변수의 불확실성(uncertainty)을 정량화하는 척도를 의미한다. 근데 엔트로피랑 저거랑 뭔 상관이냐고? 변이가 많다는 건 염기가 다르다는거잖아요. 그럼 저기에 A가 오는지 T가 오는지 G가 오는지 C가 오는지 몰라요. 이거는 슈뢰딩거도 박스 까봐야 알아. 그럼 막대기가 낮은 부분은요? 상대적으로 변이가 덜 되는거다. 어쩌면 막대가 상대적으로 낮은 부분이 변이하면 바이러스 입장에서 개망하는 부분일수도 있지...
# Phylogenic tree
# 1. 거리 계산
calculator = DistanceCalculator('identity')
dm = calculator.get_distance(alignment)
# 2. Phylogenic tree 생성(NJ)
constructor = DistanceTreeConstructor(calculator, 'nj')
tree = constructor.build_tree(alignment)
# 이름이 모예요
clean_name_dict = {}
for record in vir_sequence:
# "Hantaan virus" 같은 종 이름만 추출
species_name = record.description.split("segment")[0].split(",")[0].strip()
# 너무 긴 학명 단어는 제거 (가독성 향상)
species_name = species_name.replace("orthohantavirus", "").strip()
clean_name_dict[record.id] = species_name
for leaf in tree.get_terminals():
found = False
for original_id, clean_name in clean_name_dict.items():
if original_id.split('.')[0] in leaf.name.replace('_', '.'):
leaf.name = str(clean_name) # 확실하게 문자열로 변환해서 주입
found = True
break
if not found:
leaf.name = leaf.name.split('_')[0]
# Inner 노드 소멸
for clade in tree.find_clades():
if not clade.is_terminal():
clade.name = None
# Phylogenic tree 시각화
fig = plt.figure(figsize=(26, 25), dpi=100)
axes = fig.add_subplot(1, 1, 1)
Phylo.draw(tree, axes=axes, do_show=False, show_confidence=False, label_func=lambda x: str(x.name) if x.is_terminal() else "")
# 오케이 트리 봐봐
plt.rc('font', size=10) # 내부 글꼴 사이즈
plt.rc('axes', titlesize=20) # 제모옥은 이 크기로 하겠습니다
plt.title("Hantavirus S-Segment Phylogenetic Tree") # 근데 이제 이걸 곁들인
plt.xlabel("Genetic Distance (Substitution per site)", fontsize=12)
plt.ylabel("Viral Strains", fontsize=12)
plt.tight_layout()
plt.savefig("Hantavirus_Final_Tree.png", dpi=300, bbox_inches='tight')
plt.show()
이게 왜 시간을 이렇게 잡아먹었냐... 일단 처음에 그려진 트리가 어떻게 생겼는지 보여드림.
이게 Phylogenic tree다. 근데 안이쁘죠? 저기 이너 어쩌고 보이는것도 그렇고, 폰트는 무슨 현미경 써야 보일 것 같고, 결정적으로 그래서 쟤가 무슨 바이러스인지 모르잖음. 저거 저렇게 주면 연구자들도 NCBI 가서 저놈이 뭔 바이러스인지 찾아야 한다 이거거든요. inner는 바로 빠졌는데 트리 크기하고 이름 출력하는것때문에 ㄹㅇ 애먹었음.
이름 붙여놨더니 2차로 노안 간접체험 하게 생겼네… 근데 이거는 글꼴 크기 조정하면 해결은 됩니다. 아무튼 이게 NCBI에서 한타바이러스 게놈 긁어와서 S segment만 걸러서 Phylogenic tree 그린 결과임. 저기서 뭉쳐있는 놈들끼리는 친척인거고 거리가 좀 떨어져 있으면 사돈의 8촌정도 되는? 그런 애들이라고 생각하시면 됩니다. hierarchical clustering 하면 저게 90도 꺾인 그림이 나오는데 그게 덴드로그램임. 근데 좀 아쉬운건 이름 출력이 저게 최선이라 저게 그래서 한탄이여 스울이여 푸말라여는 안나옴. 쟤네 진짜 쪽수 많습니다.
여기서 MSA 해볼때 clustalW랑 muscle 안돼서 못했잖아요? 경로 입력해야되는데 리눅스 경로가 어디있는지 안나옴+which 몰라서. 근데 맥이나 리눅스에서는 which를 써서 설치 경로를 찾을 수 있습니다. 그러니까 해보자 이거임.
배경
뜬금없이 바이러스가 왜 나왔는가… 생물정보학 하면 보통은 유전자 시퀀싱 많이 하죠? 근데 뽑아서 시퀀싱하는건 내껄 할래도 일단 전문 장비가 있어야 하고(개비쌈), 회사에 달라고 할 수도 없고(달랜다고 주지도 않음), 환자 샘플에서 채취해서 분석하는거면 그분들한테도 동의를 구해야되는데 쟤가 어디서 굴러먹은 애인 줄 알고 그걸 덥석 줌?
아니 그럼 못해요? 아니 그건 또 아님. 우리가 몰라서 글치 데이터베이스가 아주 다양합니다. 케그라던가 켐블이라던가 PDB라던가 clinvar라던가 NCBI라던가... 걔네들이 아 니네 갖다쓰셈 하고 올려놔요. NCBI 얘네는 블래스트부터 그냥 스케일이 아 이래서 천조국 천조국 하는구나 어유...
그래서 왜 하필 한타바이러스냐… 일단 이놈이 아종(?)이 개많습니다. 진짜 월드와이드로 돌아댕기면서 새끼만 까제끼나 한탄(한탄강) 서울 푸말라 뉴욕 뭐 아주그냥 지역별로 갈려 얘네가… 그리고 이 바이러스를 발견한 사람이 한국분이세요. 이게 한국전쟁때 수수께끼의 괴질로 유명했던 놈인데 미국에서는 저 쏘오련놈들 어느새 세균전을? 했고 북쪽에서는 저 미제 간나새끼들이 세균전을 하고 있네? 했던 병입니다. 그걸 이호왕이라는 분이 '한탄강'유역에 사는 쥐한테서 발견한게 한타바이러스예요.
프로젝트 정보
- 인원: 1인
- Python 버전: 3.10
- 설치해야 하는 것: Biopython, muscle(여기서는 머슬 할건데 clustalw도 됩니다)
- 데이터 리소스: NCBI(Entrez로 갖고올 예정)
일단 머슬은 지금 안 깔아도 됨. 전편에서는 다운로드만 할거임. 아니 후편 분량은요? 그건 그때가서 뽑아봅시다.
# 모듈
from Bio import Entrez, SeqIO # 왼쪽: 일단 털어보자/오른쪽: 시퀀스 다루려면 필요합니다. 필수임.
from Bio import AlignIO # 서열 분석해줄 친구
import io # 누구세요?
아 그리고 혹시 본인이 맥이나 리눅스 쓰시는데 clustalW나 muscle 경로 모르시면 터미널 켜고 which 쓰십쇼. which muscle, which clustalw 치면 경로 알려줌.
# 바이러스 서열 다운로드
# 이게 근데 막 받으면 안되거든요? 한타바이러스 식구들은 둘쨰치고 저기가 데이터가 진짜 방대해요.
virus_query = "Hantavirus[Organism] and complete genome"
print('Searching sequences... ') # 솔직히 이거 없으면 되는건지 불안하잖아요...
handle = Entrez.esearch(db="nucleotide", term=virus_query, retmax=100)
record = Entrez.read(handle)
id_list = record['IdList']
print(f"총 {len(id_list)}개의 표준 서열을 찾았습니다.") # 100개 최대로!
쟤네들 데이터가 진짜 개쩔어서 덮어놓고 받다보면 큰일납니다. 그리고 데이터베이스중에 약간 미완성인? 그런것도 있음.
여러분 생물학 연구는 하루아침에 뚝딱 되는게 아닙니다. 바이러스같은 경우 숙주가 있어야 배양이 가능하고 대장균이 압도적으로 빨리 크는거지(하루면 다 자람) 보통 미생물들 그렇게 빨리 안 큽니다. 기껏 키웠는데 DNA 뽑았더니 수율이 개판일수도 있고 rna, 바이러스면 게놈 뽑는게 기적임. RNA는 진짜 유리몸도 이런 유리몸이 없어서 실험하다가 침튀면 RNase때문에 그대로 실험 시투더망이예요. 괜히 RNA 시험할 때 DEPC였나 아무튼 뭐 들어간 물 쓰는거 아님.
# 콤퓨타에 저-장
vir_sequence = []
for i, id in enumerate(id_list):
print(f"Downloading sequence {i+1}/{len(id_list)}: {id}")
handle = Entrez.efetch(db="nucleotide", id=id, rettype="fasta", retmode="text")
record = SeqIO.read(handle, "fasta")
# record에 id와 seq가 다 들어가야되더라... (안되면 오류남 봤음)
vir_sequence.append(record)
# 파일로 저장
SeqIO.write(vir_sequence, "hantavirus_sequence.fasta", "fasta")
print('Done!')
찾았으면 저장해야죠? 이 과정이 증말 오래 걸리기때문에… 이거 100개인데도 한 2~30초 걸렸습니다. 데이터 수집이라는 게 그렇게 빨리 안 끝나는… 인내의 시간을 거쳐야 하는거임. 쿼리 돌려놓고 Entrez 접속한 다음 저거 받고 똥 함 때리고 오십쇼.
아무튼 다 찾았으면 저거 돌려서 FASTA 파일로 저장하면 됨.
# 시퀀스 길이 체크
for rec in vir_sequence:
print(f"ID: {rec.id} | Length: {len(rec.seq)}")
셀레늄 배운김에 함 해봤음. 일단 클린바가 뭐냐면 유전적 변이와 인간의 표현형(phenotype)과의 관계에 대한 데이터를 수집하여 보관하는 데이터베이스이다. 이 코드를 매일 돌릴 필요는 없지만, 얘네가 데이터베이스다보니 주기적으로 업데이트를 함. 그니까 최신정보가 필요할때 쓰시면 되겠다.
from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import Select
# 웹드라이버 실행
driver = webdriver.Chrome() # 구글 크롬
driver.get('https://www.ncbi.nlm.nih.gov/clinvar/') # Clinvar 접속
print('Clivar Accessed!')
그 일단 웹드라이버가 뭐냐... 브라우저랑 파이썬 사이에서 가교 역할을 해주는 존재다. 우리가 코드를 실행하면 웹드라이버가 브라우저한테 이거 해달래 하고 요청하는 것이지... driver = webdriver.Chrome()은 크롬 켜겠다는 애기라서 오페라 사파리 파폭 엣지 뭐 다 된다. 웨일이요? 갸는 모르것다...
그… 시계열 데이터를 아십니까? 가로축이 시간인 데이터라고 보면 된다. 예를 들자면 나는 오늘 얼마나 걸었는가, 어제랑 비교해서는 얼마나 걸었는가, 얼마나 퍼잤는가, 오늘 삼전은 몇만전자인가(…) 뭐 그런거 말이다. 시계열의 대표적인 예시가 주식이다.
아니 오늘 판다스 통계분석을 하는데 diff()가 나온거임. 이게 뭐냐면 차분이거든요? 이 차분이 뭐냐면... 시계열 데이터는 슈뢰딩거도 무덤에서 기함할 정도로 평균과 분산이 아주 널을 뛰기때문에 이걸 정상화할 필요가 있는데, 그 정상화 절차다. 그리고 ARIMA에서 I를 맡고 있지.
그럼 AR이랑 MA는 뭔데요? AR은 자기상관이고 MA는 이동평균이다. 이동평균은 또 뭔데요? 12345 있으면 123 234 345 이런식으로 범위를 옮겨가면서 평균 내는 게 이동평균이다. ARIMA는 ARIMA(p, d, q) 이런 식으로 쓰는데 p가 AR, d가 차분(왜죠), q가 이동평균이다. 그래서 p가 0이면 IMA, q가 0이면 ARI임. 근데 뭐가 문제죠? 그건 과정 올리면서 설명해드림.
import numpy as np
import pandas as pd
import yfinance as yf
import matplotlib.pyplot as plt
from statsmodels.tsa.arima.model import ARIMA # 아리마
from statsmodels.graphics.tsaplots import plot_acf, plot_pacf # 우리 이거 볼거예요 예
yfinance는 주식 불러올라면 필요한 애고 매트플롯은 그래프 그리는 애고(…) 밑에 쟤들이 아리마 하고 acf, pacf 그릴 애들이다. 아니 그건 또 뭔데여? 그건 나중에 설명해드림. 어차피 곧 만나요.
# 삼성전자 주가 데이터... 인데...
# 제미나이야... 너 구글 소속 아니니...?
df = yf.download('005930.KS', start='2023-01-01', end='2024-01-01')
series = df['Close']
그... 구글 니네 삼성이랑 뭐 하니...? 주식을 삼전껄 추천해주네...? 아무튼... 삼성전자의 2023~2024년 주가를 가져왔다. ㅇㅋ? ㅇㅇㅋ. 저걸 근데 그냥 쓸 게 아니라 차분을 할거예요. 위에도 썼지만 시계열 데이터는 슈뢰딩거도 무덤에서 기함하고 하이젠베르크도 이딴 불확정성을 원한게 아니라면서 밥상 엎을 정도로 심각해서 정상화 절차를 거쳐야 한다.
# 위에도 썼지만 AR이냐 MA냐를 결정하기 위해서는 ACF, PACF를 봐야 합니다. 아니 그니까 봐야 뭘 알아요.
# 근데 시계열 데이터를 날로 이걸 그린다? 아 안돼 차분해야돼.
# 차분: 현재 시점-이전 시점
diff_df = series.diff().dropna()
diff_df
예 일단 차분 한번 할게요.
저걸 봐도 저게 오른건지 떨어진건지 모르겠지만 아무튼 차분 한 게 저거다.
fig, ax = plt.subplots(1, 2, figsize = (15,5)) # 사실 이게 뭔 기준인지 아직도 모르겠음둥
plot_acf(diff_df, ax = ax[0]) # 위에서 둘로 쨌으니까 한쪽에는 ACF가 들어가고
ax[0].set_title('ACF')
plot_pacf(diff_df, ax = ax[1]) # 얘는 PACF임다
ax[1].set_title('PACF')
plt.show()
# 이거... 맞나?
그럼 AR이냐 MA냐를 결정하기 위해 ACF와 PACF를 그려보자. ACF는 자기상관함수고 PACF는 부분자기상관함수인데... 이걸로 저걸 어떻게 정해요? 간단하다. ACF에서 슬금슬금 떨어지고 PACF에서 절단면(보면 앎 갑자기 선 방향이 막 틀어짐)이 보이면 AR, 반대로 ACF에서 절단면이 보이고 PACF에서 슬금슬금 떨어지면 MA, 둘 다 슬금슬금 떨어지면 ARMA 둘 다 해야된다. 그래서 뭐가 문제냐고?
이게 문제여 이게... 둘이 그래프가 거의 클론이여 클론... 아니 원래는 한쪽이 슬금슬금 떨어지고 한쪽에 팍 꺾이는 예시를 보여주면서 음 이건 AR이구나 이건 MA구나 하려고 했는데 얘는 여기서 뭘 더 할 필요가 없이 걍 저걸로 땡임... 차분 한 번 했더니 백색 잡음만 남아버려서 AR이고 MA고 못해요... 일단 제미나이 피셜 이 그래프는 개같이 깔끔한 그래프가 맞음.
# 나 많이 당황했쟈나...
# 근데 어쨌든 해봅시다. 투비컨티뉴.
# 아니 둘 중 하나는 완만하게 떨어져야 하는거 아니냐고... 삼전 이때 뭔 일이 있었던건데요...
model = ARIMA(diff_df, order = (0,1,0)) # p, d, q = 0, 1, 0
model_fit = model.fit()
model_fit.plot_diagnostics(figsize=(12, 8)) # 잔차 분석(뭔지 모르겠음...)
plt.show()
무빙평균이고 자기상관이고 못하니까 p, d, q=0, 1, 0으로 해보자. plot_diagnostics은 잔차분석 하는거라서 이따 그래프 또 나옴.
제미나이 피셜로 이건 진짜 개깔끔하게 된 게 맞다고 함. 쟤네가 뭔데요?
1. 왼쪽 위(Standard residual): 특정 시점에 비정상적으로 튀는 무리가 없고 일정하게 튀면 좋은거다.
2. 오른쪽 위(히스토그램): 저 작대기들이랑 선이 정규분포를 따를수록 좋은거다.
3. 왼쪽 아래(Q-Q plot): Q는 사분위수를 의미하는데 이건 또 나중에 설명해드리겠음. 일단 저 점들이 직선상에 일정하게 늘어져있으면(y=x에 가까우면) 좋은건데 저 그래프는 몇 개 빼고 다 일정하죠?
4. 오른쪽 아래(Correlogram): 야는 뭔지 모르겠음. 맨 왼쪽에 하나 튀는 놈은 있지만 대체로 괜찮단다.
이건 p, d, q=1, 1, 1로 돌려본 결과인데 일단 히스토그램이랑 QQ만 봐도 뭔가 아 이건 0, 1, 0쪽이 더 낫다 싶죠? 정상이랍니다. 주식이 원래 그래요...
Pandas를 쓰시는 분들이라면 한번쯤 보셨… 아냐 이건 한번 본 정도가 아니라 판다스 만질 일 있으면 엄청 써보는거임… 특히 저 앞에 두개요. 진짜 엄청 써봅니다. 근데 둘이 무슨 차이인지 모르시겠다고? 그럼 잘 오셨음.
시리즈, 그리고 데이터프레임
시리즈가 모이면 데이터프레임이 된다는 건 아실것이다. 그 대충 문발 생각하시면 된다. 구슬을 꿰어서 세로로 한 줄(시리즈)을 만들고, 그걸 가로로 엮어서 문발(데이터프레임)을 만든다. 그리고 저 네개를 데이터프레임에서 뭐 찾을 때 쓰는데 어떨 때 쓰느냐…
loc, iloc
이 두개는 데이터프레임에서 행단위로 찝을 때 사용한다. 그니까 저걸 쓰면 어떻게 나오냐... 그 비즈 문발 보시면 세로로 꿴 구슬을 가로로 엮어서 2차원 평면을 만들잖아요? 그 문발을 보면 구슬에 순서가 있지 않습니까? 그치 그 구슬을 가로로 한 줄 갖고온다 이거지. 근데 왜 두개씩이나 있냐고요?
loc은 주소(인덱스) 기반으로 가고 iloc은 순서 기반으로 간다. 쉽게 설명하자면 내가 친구 집을 찾아갈 때 얘 집이 무슨로 몇번이더라… 하면서 주소로 찾아가는건 loc, 얘네 집이 이 골목에서 몇번째였더라…로 찾아가는 건 iloc라고 보시면 된다. 이건 사실 데이터프레임의 인덱스가 숫자면 그렇게 크게 체감은 안 되는데, 인덱스가 숫자가 아니라 A, B, C 뭐 이런거면 차이가 확 드러난다. 사실 인덱스가 1부터 시작할때도 차이가 체감되긴 함.
일단 이거 돌리려면 넘파이가 설치되어 있어야 한다. 일단 개발은 3.10에서 하긴 했는데 뭐 버전타는건 없겠지… 있으면 큰일난다… 나 3.10에서만 돌려봄…
# OOP 서타일은 클래스에서 시작이여
class Bingo:
# 기본값은 5*5(기본 범위는 25)
def __init__(self, size = 5, n = 25):
self.size = size
self.bingo_max = n
self.bingo_range = range(1, self.bingo_max + 1)
self.board = None
self.number_list = list(self.bingo_range)
# 빙고판 생성
def make_bingo(self):
self.board = np.random.choice(self.bingo_range, size=(self.size, self.size), replace=False)
# 숫자 뽑기
def draw_number(self):
if len(self.number_list) > 0:
bingo_pop = random.choice(self.number_list)
self.number_list.remove(bingo_pop)
return bingo_pop
else:
print('No more draw!')
return None
# 빙고 체크 함수
def isbingo(self, n = 1):
count = 0
# 줄
count += np.sum(np.all(self.board == 0, axis=1))
count += np.sum(np.all(self.board == 0, axis=0))
count += np.all(np.diag(self.board) == 0) # 대각선(좌상-우하)
count += np.all(np.diag(np.fliplr(self.board)) == 0) # 대각선(우상-좌하)
# 빙고가 됐어?
return count >= n
# 마킹
def marking(self, jebi):
if jebi in self.board:
self.board[self.board == jebi] = 0
return True
return False
# 출력 관련임다. 깔끔하게 뽑을라고...
def print_board(self):
for row in self.board:
print(" ".join(f"{num:2}" for num in row))
print("+-----------------------+")
OOP 서타일의 완성은 모든걸 다 클래스에 때려박아서 각 역할별로 각 메소드가 책임지게 만드는 것이다. 물론 처음에는 클래스 없이 절차지향으로 했던거 저기다가 다 때려박는 정말 개같은 난이도가 날 기다리고 있었지만… 그래서 쟤들이 빙고를 할 때 필요한 것들을 다 할 거다.
그니까 우리가 마킹하다가 가로세로대각선 한줄 지워지면 빙고잖아요? 그걸 판별하는 메소드다. 근데 diag는 뭐냐고? 주대각선이요. 행렬의 좌상->우하로 가는 대각선이 주대각선이고 밑에건 거꾸로 뒤집는거다. 플립 들어갔을 때 알아봄.
# 마킹
def marking(self, jebi):
if jebi in self.board:
self.board[self.board == jebi] = 0
return True
return False
마킹하는 애다. 근데 리턴트류 리턴폴스는 왜 있냐고? 보드가 5*5인데 숫자가 1부터 50까지면 보드에 안 들어가는 숫자도 있잖아요? 그럴 때 폴스가 뜬다.
# 출력 관련임다. 깔끔하게 뽑을라고...
def print_board(self):
for row in self.board:
print(" ".join(f"{num:2}" for num in row))
print("+-----------------------+")
얘는 뭐 크게 볼 건 없고 출력 관련이다. 아니 이게 언패킹을 했더니 개같이 안이쁜거야... 그렇다고 []를 뗄 수는 없잖아요... 그런거임. 저것도 숫자 3~4자리 되면 num 뒤에 숫자 바꿔야 할 수도 있음. 아니면 범위를 1~99로 제한하던가...
# 빙고 보드 생성
while True:
bingo_num = int(input('Write maximum number: '))
size = 5 # 여기 바꾸시면 빙고 크기 바껴요! (기본 5*5)
try:
if bingo_num < size ** 2:
raise ValueError
else:
game = Bingo(size, bingo_num)
break
except ValueError:
print(f'Out ot range: You have to input number larger than {size ** 2}')
# 목표 설정
while True:
max_line = 2 * size + 2
bingo_line = int(input('How many lines for end game?: '))
try:
if bingo_line >= 1 and bingo_line <= max_line:
break
else:
raise ValueError
except ValueError:
print(f'Out ot range: You have to input number between 1 and {max_line}')
보드 생성하고 목표 설정에는 트롤링 방지 장치가 있어서 긴거고 나머지는 심플하다. 숫자 범위의 경우 5*5로 해놓고 범위가 25보다 작으면 넘파이가 이건 뭐 배열을 뭐 어쩌라는겨 하면서 오류를 토함. 그래서 그거 관련으로 준 거고... 그 빙고판의 크기에 따라서 빙고 줄 수 최댓값 있는거 아셨음? 나도 인제 알았음. 가로+세로+대각선 해서 사이즈 * 2 + 2가 최대다. 그리고 0줄은 있을 수 없으니까 1부터 최댓값까지 제한을 거는 것.
# 빙고판 생성
game.make_bingo()
# 몇트째임?
bingo_cnt = 1
# 이 숫자가 빙고판에 있으면 지우고, 없으면 패스.
# 일단 가로세로대각선 1빙고 될 때까지 해봅시다.
while True:
# 랜덤으로 숫자 하나를 뽑는다. (범위는 위에 빙고판 숫자랑 동일)
bingo_jebi = game.draw_number()
# 물론 그럴 일은 없겠지만 리스트 거덜나면 끝납니다.
if bingo_jebi is None:
print("No more draw! Game over.")
break
# 체크(위에 있음)
if game.marking(bingo_jebi):
print(f'{bingo_cnt}: {bingo_jebi} hit! 👏')
else:
print(f'{bingo_cnt}: {bingo_jebi} no hits... 😭')
game.print_board()
# 조건 ㅇㅋ->시마이
bingo_cnt += 1
if game.isbingo(bingo_line):
print(f'🎉Congratulations!')
break
나머지는 판 만들고 몇판째인지 세고 빙고게임 하는게 다임. 뽑기통 거덜나면 끝나는 로직도 넣어두긴 했는데 그 전에 빙고게임이 끝나겠지 지피티야…
일단 이거 어제 부트캠프에서 한거고 깃헙에는 코드가 올라가있음. 근데 왜 글은 오늘 올리느냐...
두 가지 이유가 있는데 일단 요즘 레전자 DLC 미느냐고 바쁘고, 미디움은 하루에 글 세개인가 제한이 있습니다… 목욜에 제한 넘겨서 하나 금욜에 올렸는데 이것도 금욜에 올렸다간 제때 못올라감…
힙 정렬을 하기 위해서는 힙 트리에 대해 먼저 알아야 하는데, 이거는 트리는 트리인데 일단 완전 이진 트리(자식이 최대 두 개인 트리)이다. 그리고 항상 루트에 최댓값(최대 힙) 혹은 최솟값(최소 힙)이 들어가있어서 최댓값 찾기는 개빨리끝남.
여기서는 어떻게 구현했냐면
1. 트리 뼈대를 만든 다음(리스트를 주면 리스트 길이에 따라서 완전 이진 트리가 생성됨)
2. 그 트리 안에 있는 리스트를 힙 트리로 만들건데(최대 힙), 이건 되게 간단하다. 부모 노드랑 자식 노드를 비교해서 더 큰 값이 계속해서 위로 올라가기만 하면 된다.
3. 그리고 가장 중요한 과정! 루트로 올라온 최댓값과 트리의 가장 오른쪽 아래에 있는 잎을 바꾼 다음 잎을 뗄 거다.
4. 2~3을 반복
2번하고 3번이 키포인트가 되어서 힙 정렬은 일단 개같이 빠른 속도를 자랑하지만 구현하는 것도 어렵고 코드도 보자마자 뇌 커널패닉 올 정도로 아스트랄하다. 그런데 왜 루트에 있는 걸 잎이랑 바꾸나요? 일단 뿌리 없는 나무는 근본 없는 나무… 루트는 트리의 근간이라 함부로 삭제할 수 없다. 쌉고수 분들은 잘 아시겠지만, 혹시나 개초보라면 대충 이렇게만 이해해두십셔. 그리고 루트랑 잎을 바꿔서 작은 값이 올라오면 또 다음 단계에서 최대 힙을 구성하면서 값들이 섞이게 돼서 끊임없이 올라오게 된다. 힙 정렬의 근간은 트리를 유지하면서 끊임없이 뒤섞어서 최댓값/최솟값을 끌어올려 힙을 만드는 것이다.
이진 트리 만들기
# 데이터를 이진 트리화하는 함수
def binary_tree(data):
# 부모 노드의 개수. 데이터 / 2다.
number_of_parent = len(data) // 2 # 소수점따원 필요없다네
# 완전 이진 트리이기때문에 무조건 자식은 두 개다.
# 딕셔너리에는 값의 '순서'를 담는다. ㅇㅋ? ㅇㅇㅋ
tree_node = {}
child_node_idx = 1 # 자식 노드는 1부터 시작 (0은 루트)
child_node_last = len(data) - 1 # 루트 빼면 전체 길이에서 하나 빠짐
for i in range(number_of_parent):
# 자 생성 드가자
tree_node[i] = []
# 자식은 최대가 두개(사유: 완전 이진 트리)
for _ in range(2):
tree_node[i].append(child_node_idx)
child_node_idx += 1
if child_node_idx > child_node_last:
break
return tree_node
아 혹시 보자마자 커널패닉이 오셨나요? 당신이 코딩 쌉고수가 아닌 이상 지극히 정상이다. 내가 위에서 힙 트리는 완전 이진 트리라고 했죠? 그래서 최대 자식이 두 개인거다. 그럼 왜 딕셔너리로 만든건가요?
딕셔너리의 키값이 부모 노드고, 밸류가 자식 노드(리스트)다. 그래서 키값을 호출하면 자식이 나오게 되는 구조인데, 일단 저기에 들어가는 건 리스트에 들어있는 실제 값이 아니라 리스트 길이에 따른 인덱스... 그니까 주소다. 그래서 길이가 15인 리스트를 넣으면 0부터 14까지 나오게 된다.
number_of_parent = len(data) // 2 # 소수점따원 필요없다네
그림을 잘 보면 유자식, 무자식 따로 표시가 되어있는 걸 볼 수 있는데, 이게 무슨 소리냐... 여러분들 솔직히 힙 정렬이 힙 트리 만들고 위아래 바꿔서 빼는걸 반복한다고 했을 때 무슨 생각 하셨어요? 그죠. 이걸 계속 반복하는데 이게 빠르다고? 라고 생각하셨을 분들도 계실 것이다. 근데 트리에서 저 노드들을 다 보는 게 아니라 자식이 있는 노드들만 본다. 자식이 있는 노드들을 확인해서 부모랑 비교하고 힙을 구축하는거지, 번거롭게 전체를 다 보지 않는다. 그리고 자식이 있는 부모 노드의 개수는 리스트 길이를 2로 나눈 정수값(소수점 버림)이다.
힙 정렬 하기
# 정렬 이즈 히얼
def heap_sort(data):
# 정렬 결과
result_list = []
# 우리 이거 뻉이쳐야돼요
while len(data) > 0:
# 순순히 트리를 넘긴다면 유혈사태는 일어나지 않을 것입니다.
tree = binary_tree(data)
# 키
keys = tree.keys()
# 이름내놔
key_list = list(keys)
key_list.sort(reverse=True)
# 본론 드가자...
for parent in key_list:
# 자식의 위치
child_position = tree[parent]
# 자식의 개수만큼 반복한다
for idx in child_position:
# 부모의 값이 자식의 값보다 작은가?
if data[parent] < data[idx]:
# 작으면 바꿔
data[parent], data[idx] = data[idx], data[parent]
# 제일 큰 값(루트)과 잎을 바꿉니다.
data[0], data[-1] = data[-1], data[0]
# 결과 리스트에 담는다.
max_list = data.pop()
result_list.append(max_list)
# 다 됐음?
result_list.reverse()
data.extend(result_list)
# 위 방식은 최대 힙입니다. (최소 힙으로 쓰려면 부등호 반대로 달아야됨)
여기서 2차 패닉 오신 분들은 일단 진정하시고 심호흡 한번 하십쇼. 이 코드가 트리 뼈대를 기반으로 트리를 만들고, 힙 정렬을 진행하는 코드다.
# 순순히 트리를 넘긴다면 유혈사태는 일어나지 않을 것입니다.
tree = binary_tree(data)
# 키
keys = tree.keys()
# 이름내놔
key_list = list(keys)
key_list.sort(reverse=True)
우리 그 위에서 짰던 트리 뼈대 만드는 함수 있죠? 그걸로 리스트 입력받아서 트리를 만드는거다. 그리고 키(부모 노드)를 입력받은 다음 뒤집는 건 트리를 루트부터가 아니라 밑에서부터 보기 위해서다. 위에서 설명했던 힙 만드는 과정이 밑에서부터 진행된다는 것.
# 본론 드가자...
for parent in key_list:
# 자식의 위치
child_position = tree[parent]
# 자식의 개수만큼 반복한다
for idx in child_position:
# 부모의 값이 자식의 값보다 작은가?
if data[parent] < data[idx]:
# 작으면 바꿔
data[parent], data[idx] = data[idx], data[parent]
# 제일 큰 값(루트)과 잎을 바꿉니다.
data[0], data[-1] = data[-1], data[0]
# 결과 리스트에 담는다.
max_list = data.pop()
result_list.append(max_list)
여기가 본론이다. 루트부터 시작해서 왼쪽->오른쪽 순서로 채워나간 다음, 밑에서부터 부모보다 큰 자식(둘 다 크면 둘중 더 큰 값을 올림)을 올리고 올리고 올려서 최대 힙을 만든다. 그리고 힙을 다 만든 다음 루트와 오른쪽 아래 잎을 바꿔주고, 그 잎을 뺀다. 그걸 반복문 돌리면 되는거다. 쉽죠?
# 다 됐음?
result_list.reverse()
data.extend(result_list)
그럼 이걸 왜 뒤집었는지에 대한 설명을 해주겠음… 쟤가 최대 힙이라 저대로 정렬하게 되면 내림차순 정렬이 된다. 왜죠? 큰 값이 첫빠따로 들어가잖아요. 그래서 오름차순으로 정렬하려면 최소 힙으로 해야 한다.
근데 왜 최대 힙으로 한건가요? 일단 우리 부트캠프는 뉴비들을 강사님이 멱살캐리 해가면서 데이터 분석이 가능한 인력으로 만드는 과정이다. 그래서 강사님이 OT때도 모르는 거 있으면 거리낌없이 물어봐라, 몇 번이고 설명해주겠다고 말씀하셨음... 아무튼 여기서 자료구조도 처음 보는 사람들한테 힙이 뭔지, 힙 정렬이 뭔지를 같이 설명해줘야 하는데 거기다가 최소힙, 최대힙까지 설명해야된다? 우리 이거 구현도 해야되는데? 뇌 커널패닉 1스택 추가됩니다. 저 최소힙 최대힙도 제미나이랑 쉬는시간에 티키타카 하다가 알게 된 거임...
if data[parent] < data[idx]:
리스트 안 뒤집고 오름차순으로 정렬하고 싶으시면 저 부등호 >로 하십시오. 그러면 부모가 자식보다 클 때 바뀌는 최소 힙이 완성된다. 저 부등호는 부모가 자식보다 작으면 바꾸라는 얘기.
트리를 탐색하는 방식이다. 방식인데 이제 하나는 수직으로 가고(DFS), 다른 하나는 수평으로 가는(BFS) 방식이다. 둘 다 공통적으로 없는 길을 만들어서 가지 않고, 모든 트리를 순회하는데 그냥 순서가 다소 다른 것 뿐이다.
참고로 오늘 올리는 건 특정 노드를 찾아가는 게 아니라 전체 순회다. 특정 노드만 찾는건 나중에 레전자 DLC 다 밀고 시간 좀 되면 해드림… 지금 DLC 미느냐고 정신없다…
공통: 트리 생성
# 트리도 연결 리스트로 만든다...
# 그래서 노드
class Node:
def __init__ (self, _value):
# 관리할 값
self.value = _value
# 부모
self.parent = None
# 자식 리스트
self.childlist = []
def add_child(self, child_node):
# 자식 노드 추가
self.childlist.append(child_node)
# 부모 연결 설정
child_node.parent = self
트리에는 부모와 자식이라는 개념이 존재한다. 마치 가계도같은거다. 그래서 노드에도 내 자식이 누구이고, 내 부모가 누구인지를 기록해야 하는 '데'… 이게 트리는요… 하늘이 두쪽나도 부모 노드는 하나임. 두개일수가 없음. 그래프는 부모자식 개념이 없는 대신 정점에 여럿이 연결될 수 있지만 트리는 아닙니다. 그래서 부모는 변수고 자식은 리스트인 것. 자식이 두개인 경우가 이진트리인거지, 자식이 없거나 하나거나 셋 이상일 수도 있다.
# 위에 저 트리를 DFS로 탐색해보자.
def DFS (_rootnode, _search_list):
# 전달받은 노드는 방문한 것으로 취급한다.
_search_list.append(_rootnode)
# 현재 루트 노드의 자식 노드들을 가지고 반복함
for subnode in _rootnode.childlist:
# 방문기록이 없다->함수를 다시 호출
if subnode not in _search_list:
DFS(subnode, _search_list)
# 탐색 결과
search_list = []
DFS(nodeA, search_list)
for subnode in search_list:
print(f'{subnode.value}')
일단 내가 노드를 하나 방문하면, 걔는 방문한 노드로 친다, 그라고 그 밑에 노드들을 가지고 방문하고, 기록하고를 반복하는 방식이다. 이게 그림이 있으면 이해하기가 편한데 아무튼… 재귀함수가 제일 깔끔함.
출력 형식 수정
# 위에 저 트리를 DFS로 탐색해보자.
def DFS (_rootnode, _search_list, _depth = 0):
indent = "ㆍ" * _depth
print(f'{indent} {_depth}단계: {_rootnode.value}')
# 전달받은 노드는 방문한 것으로 취급한다.
_search_list.append((_rootnode.value, _depth))
# 현재 루트 노드의 자식 노드들을 가지고 반복함
for subnode in _rootnode.childlist:
DFS(subnode, _search_list, _depth+1)
# 탐색 결과
search_list = []
DFS(nodeA, search_list)
우리가 그래도 이왕 출력하는거, 좀 보기 좋게 출력하면 좋잖아요... 저 위에꺼 출력하면 걍 값만 나와서 이게 몇단계인지 몰라...
0단계: A
ㆍ 1단계: B
ㆍㆍ 2단계: D
ㆍㆍㆍ 3단계: M
ㆍㆍㆍ 3단계: N
ㆍㆍ 2단계: E
ㆍㆍㆍ 3단계: H
ㆍㆍㆍ 3단계: I
ㆍㆍㆍㆍ 4단계: J
ㆍㆍㆍㆍ 4단계: K
ㆍ 1단계: C
ㆍㆍ 2단계: F
ㆍㆍ 2단계: G
깃헙에 올라가있는 건 이 버전이다.
BFS
기본 코드
# BFS
# DFS가 수직이라면 얘는 수평이다. 탐색할 때 인접한 노드 리스트를 다 담아둔다. (방문한, 방문할 두개)
def BFS(_rootnode, _search_list, _depth = 0):
# 방문'한' 노드
gone_list = [_rootnode]
# 방문'할' 노드
will_going_list = []
while True:
for gone in gone_list:
_search_list.append(gone)
# 인접한 노드들을 담는다
will_going_list.extend(gone.childlist)
# 가고 나면 갱신
gone_list.clear()
gone_list.extend(will_going_list)
_depth += 1
will_going_list.clear()
# 더 갈 거 없으면 종료
if len(gone_list) == 0:
break
# 탐색 결과
search_list = []
BFS(nodeA, search_list)
for subnode in search_list:
print(f'{subnode.value}')
얘는 뭐 재귀함수고 자시고 할 것도 없고 걍 돌면서 인접한 노드들 목록에 담고 순회하고 하면 된다. 근데 이 방식은 리스트 제때 초기화 안 하면 무한루프 터짐…
출력 형식 수정
# BFS
# DFS가 수직이라면 얘는 수평이다. 탐색할 때 인접한 노드 리스트를 다 담아둔다. (방문한, 방문할 두개)
def BFS(_rootnode, _search_list):
# 방문'한' 노드
gone_list = [_rootnode]
# 방문'할' 노드
will_going_list = []
# 단계(깊이)
depth = 0
while True:
print(f"\n[Level {depth}]")
for gone in gone_list:
_search_list.append(gone)
print(f"- {gone.value}")
# 인접한 노드들을 담는다
will_going_list.extend(gone.childlist)
# 가고 나면 갱신
gone_list.clear()
gone_list.extend(will_going_list)
will_going_list.clear()
depth += 1
# 더 갈 거 없으면 종료
if len(gone_list) == 0:
break
search_list = []
BFS(nodeA, search_list)
얘도 깊이 표시해주는 건 맞는데 DFS랑 출력 형식이 좀 다르다.
[Level 0]
- A
[Level 1]
- B
- C
[Level 2]
- D
- E
- F
- G
[Level 3]
- M
- N
- H
- I
[Level 4]
- J
- K
리스트 사이즈는 진도 뺄 때 안 넣었던건데 내가 걍 넣었다. 그거 외에는 머리꼬리… 그니께 지금 저 리스트는 머리랑 꼬리만 이어져있는 상태다.
생성
# 추가
# istail = True->꼬리/False->앞
def add_node (self, _value, _istail):
# <시스템> 노드가 생성되었습니다
new_node = Node(_value)
# istail이 True이면 뒤로, istail이 False이면 앞으로 간다.
# 뒤에서 추가: tail의 바로 앞 노드를 변수에 담은 다음 -> 새 노드의 다음 노드를 꼬리의 이전 노드로 설정하고-> 새 노드의 다음 노드를 꼬리로 설정하고 ->
# 꼬리의 이전 노드의 다음 노드를 새 노드로 설정하고 -> 꼬리의 이전 노드가 새 노드가 된다
if _istail == True:
# 꼬리의 바로 앞 노드
tail_prev = self.tail.prevnode
# 새 노드의 앞뒤를 묶어보자
new_node.prevnode = tail_prev # 새 노드의 이전
new_node.nextnode = self.tail # 새 노드의 뒤(꼬리)
# 꼬리의 이전 노드의 다음 노드를 새 노드로 설정+꼬리의 이전 노드가 새 노드가 된다
tail_prev.nextnode = new_node # 꼬리의 이전 노드의 다음
self.tail.prevnode = new_node # 꼬리 앞
# 리스트 전체 길이
self.listsize += 1
return
# 앞에서 추가: 위랑 비슷한데 시발점이 머리이기때문에 머리의 바로 뒤 노드를 담아야 한다.
else:
# 머리의 바로 뒤 노드
head_next = self.head.nextnode
# 앞뒤를 묶어요
new_node.prevnode = self.head # 새 노드의 앞(머리)
new_node.nextnode = head_next # 새 노드의 뒤
# 머리의 다음 노드가 새 노드가 된다.
head_next.prevnode = new_node # 머리의 다음 노드의 이전(...)
self.head.nextnode = new_node # 머리 뒤
# 리스트 전체 길이
self.listsize += 1
return
뇌정지가 오셨다면 정상입니다. 이거 이해하다가 커널패닉 오는 사람 많아요. 기본적으로 연결을 끊고 다시 잇는다는 건 연결 리스트와 같은데, 얘는 앞뒤로 이어야 한다. 근데 이걸 글로만 보면 다들 커널패닉이 온다 이거요... 이게 그리고 추가도 양방향이라 더함.
이걸로 보시면 이해가 좀 더 쉬울거임.
n번째 값 찾기
# 조회
# ishead = True->머리부터/False->꼬리부터
def get_node (self, _position, _ishead):
# 얘는 걍 조회라 리스트 사이즈가 바뀌지는 않는다.
# ishead = True->머리에서부터 n번째/ishead = False->꼬리에서부터 n번째
move_cnt = _position + 1 # 헤드 끼고 하면 한번 더 가야된다고 생각하시면 편합니다
# 머리부터
if _ishead == True:
pointernode = self.head # 시발점
for _ in range(move_cnt):
pointernode = pointernode.nextnode # 앞으로 갓
# 꼬리부터
else:
pointernode = self.tail # 시발점
for _ in range(move_cnt):
pointernode = pointernode.prevnode # 뒤로 빽
# 내가 값이여
return pointernode.value
이거는 되게 간단하다. 시발점이 머리 혹은 꼬리이고, 각각 이동하면 땡이다. 대신 시발점이 머리/꼬리라 이동횟수가 하나 더 들어간 것이다.
중간에 끼워넣기
# 끼워넣기(?)
# ishead = True->머리부터 시작해서 position - 1 & position/False->꼬리부터 시작해서 position & position + 1
# ishead, 0->맨앞
def insert_node (self, _position, _value, _ishead):
# <시스템> 노드가 생성되었습니다
new_node = Node(_value)
# 얘는 노드 하나만 찾으면 된다. 왜냐고? 내 위로, 내 밑으로 다 있으니까. 물론 시발점에 따라 이동 방향은 다르지만서도...
move_cnt = _position + 1
# 머리부터 출발
if _ishead == True:
pointernode = self.head # 시발점(욕 아님)
for _ in range(move_cnt):
pointernode = pointernode.nextnode # 도착하였소!!!
# 저기 위에 삽입한거 보이시죠? 그거 그대로 하면 됩니다. pointnode 다음에 넣을거임.
where_insert = pointernode.prevnode
# 앞-새거-포인트
where_insert.nextnode = new_node
pointernode.prevnode = new_node
# 새 노드도 연결
new_node.prevnode = where_insert
new_node.nextnode = pointernode
# 리스트 전체 길이
self.listsize += 1
return
# 꼬리부터 출발
else:
pointernode = self.tail # 시발점(욕 아니예욧)
for _ in range(move_cnt):
pointernode = pointernode.prevnode # 아 왔다고
# 얘는 pointnode 앞에 간다.
where_insert = pointernode.nextnode
# 포인트-새거-뒤
where_insert.prevnode = new_node
pointernode.nextnode = new_node
# 새 노드 연결
new_node.prevnode = pointernode
new_node.nextnode = where_insert
# 리스트 전체 길이
self.listsize += 1
return
사실 이건 생성인데 위치가 지정된 생성이다. 그래서 시발점에 따른 방향만 다르고 기본 골자는 비슷하다. 추가 순서는 머리부터 출발할 경우 포인터 앞에, 꼬리부터 출발할 경우 포인터 뒤에 추가된다. 이거는 추가되는 방향을 잘 보는 게 중요함.
삽입하는 위치는 케바케입니다.
수정
# 수정
# ishead = True->머리부터 시작해서 n번째/False->꼬리부터 시작해서 n번째
def set_node (self, _position, _value, _ishead):
# 가야 수정하쥬...
move_cnt = _position + 1
# 이건 걍 값만 바꾸는겁니다. 그니까 노드가 갖고 있는 값만요!!
# 머리부터
if _ishead == True:
pointernode = self.head
# 그럼 출발!
for _ in range(move_cnt):
pointernode = pointernode.nextnode
pointernode.value = _value
# 꼬리부터
else:
pointernode = self.tail
# 그럼 출발!
for _ in range(move_cnt):
pointernode = pointernode.prevnode
pointernode.value = _value
return
솔직히 위에 두 개 보다보니까 얘 보면 좀 쉬워보이지 않습니까...? 밑에 삭제도 그렇지만 얘는 시발점에 따라 가는 방향만 다르지 그냥 그 노드 도착하면 거기서 해결 볼 수 있는 것들임...
삭제
# 삭제
# ishead = True->머리부터 시작해서 n번째/False->꼬리부터 시작해서 n번째
def delete_node (self, _position, _ishead):
move_cnt = _position + 1
# 머리부터
if _ishead == True:
pointernode = self.head
# 렛츄고
for _ in range(move_cnt):
# n번째 노드에 도착할때까지 내려간다.
pointernode = pointernode.nextnode
# 꼬리부터
else:
pointernode = self.tail
# 렛츄고
for _ in range(move_cnt):
# n번째 노드에 도착할떄까지 올라간다.
pointernode = pointernode.prevnode
# 도착했으면 앞뒤를 확인한다
front = pointernode.prevnode
back = pointernode.nextnode
# 연결을 끊고
pointernode.prevnode = None
pointernode.nextnode = None
# 잇는다
front.nextnode = back
back.prevnode = front
self.listsize -= 1
return
얘는 사실 출발점만 다르고 포인터 앞이랑 뒤를 잇는 기본 골자는 같다. 단지 머리에서 출발하느냐, 꼬리에서 출발하느냐 차이다.
전체 조회
# (from head) 다 보여줘
def node_show(self):
# head가 가리키는 게 tail이면(중간에 암것도 없으면)
# 지하철인데 역이 없어 역이
if self.head.nextnode == self.tail:
print('리스트가 비었습니다. ')
return
# 아 이제 역 좀 생겼다
pointernode = self.head
while True:
# 다음으로 렛츄고
pointernode = pointernode.nextnode
print(pointernode.value)
# 없으면 시마이
if pointernode.nextnode == self.tail:
break
return
def __init__ (self):
# 포인터 두 개(front, rear)
self.frontpointer = None
self.rearpointer = None
# 큐 크기
self.queuesize = 0
보니까 얘는 포인터가 두 개 있네? 왜 그렇죠? 큐는 들어오는 건 뒤로 들어오는데 나가는 건 앞으로 나가서 그렇다. 어디 오픈런같은 거 할 때 줄 어디로 서요? 줄 뒤로 가죠. 그럼 어디로 나옵니까? 줄 앞으로요. 프론트 포인터는 나갈 애가 누구인지, 리어 포인터는 들어갈 애가 누군지를 가리킨다.
# 인큐
def enqueue(self, _value):
# 인큐: 줄을 섬
new_node = Node(_value) # 커피 주문하는 손님
# 프론트 포인터가 None->마수걸이(첫 손님)
if self.frontpointer is None:
# 일단 하나까지는 같은 곳을 가리킴
self.frontpointer = new_node
self.rearpointer = new_node
else:
# 인큐일때는 리어가 이동합니다
self.rearpointer.nextorder = new_node
self.rearpointer = new_node
# 사이즈 추가
self.queuesize += 1
return
# 디큐
def dequeue(self):
# 디큐: 커피 나와서 받고 갈 길 감
# 이거는 값 표시용입니다.
dequeue_pointer = self.frontpointer
# 대기열이 없으면 디큐 못해요
if self.queuesize == 0:
print('큐가 비었습니다!')
return
# 큐가 비지 않았다면 디큐를 하면 됨
else:
# 디큐를 할 때는 프론드 포인터가 한칸 이동합니다
self.frontpointer = self.frontpointer.nextorder
self.queuesize -= 1
# 큐가 비면 두 포인터가 다시 None을 가리키게 해 줘야 한다
if self.frontpointer is None:
self.rearpointer = None
return dequeue_pointer.value
위에서 큐는 포인터가 두 개라고 했는데, 두 포인터가 각각 움직이는 시점이 다르다. 이 큐를 커피 대기줄이라고 해 보면, 인큐는 커피 주문이 새로 들어온 것이다. 주문이 한개일때까지는 두 포인터가 다른 곳을 가리키지만, 두개 이상이 되면 리어 포인터가 새로 들어오는 주문쪽으로 이동하게 된다. 이 상태에서 누군가가 커피를 받으면 디큐가 되죠? 그러면 프론트 포인터가 다음으로 나갈 주문을 가리킨다. 그러니까 새로 누군가 줄을 서면 리어가, 누군가 주문한 걸 받으면 프론트가 움직인다.
# 큐 좀 봅시다
def queue_show(self):
# 큐 비었으면 비었다고 하고
if self.queuesize == 0:
print('큐가 비었습니다! ')
return
# 아니면 쫙 보여줘
else:
# 큐 안 건드리고 내용만 볼겁니다.
temp_pointer = self.frontpointer
# 다음이 비어있나요?
while temp_pointer is not None:
print(temp_pointer.value)
# 오키 넥스트
temp_pointer = temp_pointer.nextorder
return temp_pointer
부트캠프 들으면서 얘를 구현해 볼 기회가 또 생겼음. 전에 했던것보다 훨배 복잡한거라 들고 왔습니다. 아마 다음에 올리는건 트리랑 그래프정도?
# 노드
class Node:
# 뾰로롱
def __init__ (self, _value):
self.value = _value
self.nextnode = None
# 다음 노드의 주소값을 설정
def setnext(self,_nextnode):
self.nextnode = _nextnode
얘는 노드 만드는 애다. 연결 리스트는 노드 하나 안에 노드가 담을 정보와 다음 노드 주소(다음 노드 여기 있음)가 들어있다.
class Linkedlist:
# 머리
def __init__ (self):
self.headnode = Node(0)
self.datacount = 0 # 연결 리스트의 길이
# 데이터 넣기
def add_node (self, _value):
# 새로운 노드 생성
new_node = Node(_value)
pointernode = self.headnode
# 마지막 노드가 어디 있나
while True:
# 찾았으면 뒤에 추가해라
if pointernode.nextnode == None:
break
else:
pointernode = pointernode.nextnode
pointernode.nextnode = new_node
# 카운터 추가
self.datacount += 1
# 내놔
def where_node (self, _position):
target_index = _position - 1
# 잘못 입력했다면
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
# 여기가 본론임...
else:
# 헤드에서 시작해서 우리가 찾는 포지션 값까지 가야 한다.
pointernode = self.headnode
# 전체 이동 횟수를 계산하고
move_cnt = target_index + 1
# 그만큼 반복 아...
for i in range(move_cnt):
# 가야돼 아...
pointernode = pointernode.nextnode
# 드디어 나옴
return pointernode.value
# 여기다 넣어줘
def insert_node (self, _position, _value):
# 수정할 포지션
target_index = _position - 1 # 3 입력하면 3번째 수정하려면 필요함
# prev: 하나 덜 감/curr: 정직하게 ㄱㄱ
# 2번때에 노드 끼워넣는거면 1, 2까지 갑니다.
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
# 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨?
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
else:
# 끼워넣을 노드
new_node = Node(_value)
# 노드를 끼워넣을 포지션과 그 앞 노드에 대한 정보가 필요함
# 그래서 두개지요
prev_pointer = self.headnode
curr_pointer = self.headnode.nextnode
move_cnt = target_index
for i in range(move_cnt):
prev_pointer = prev_pointer.nextnode
curr_pointer = curr_pointer.nextnode
# 노드 끼우는 순서: prev-노드-curr
prev_pointer.nextnode = new_node
new_node.nextnode = curr_pointer
# 아 맞다 카운터
self.datacount += 1
return
# 바꿔줘
def change_node (self, _position, _value):
# 3을 입력하면 정직하게 2번째 인덱스를 바꾸기 위해서는 변환 절차가 필요하다.
target_index = _position - 1
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
# 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨?
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
else:
# 원리는 간단하다. 찾아라, 그리고 바꿔라.
move_cnt = target_index + 1
pointernode = self.headnode
for i in range(move_cnt):
pointernode = pointernode.nextnode
# 도착했으면 수정을 해야됩니다.
pointernode.value = _value
# 빼줘
def delete_node (self, _position):
# 3을 입력하면 정직하게 2번째 인덱스를 지우기 위해서는 변환 절차가 필요하다.
target_index = _position - 1
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
# 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨?
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
else:
# 그 포인터 앞에 있는 노드의 연결을 다음다음노드로 하면 된다. 연결만 끊으면 끝.
move_cnt = target_index
pointernode = self.headnode
for i in range(move_cnt):
pointernode = pointernode.nextnode
pointernode.nextnode = pointernode.nextnode.nextnode
# 아 맞다 카운터
self.datacount -= 1
return
# 잘 된겨?
def node_show (self):
# 헤드노드의 다음 노드가 없으면
if self.headnode.nextnode == None:
print('이 리스트는 텅 비었습니다. ')
return
pointernode = self.headnode
while True:
# 다음으로 렛츄고
pointernode = pointernode.nextnode
print(pointernode.value)
# 없으면 시마이
if pointernode.nextnode == None:
break
return
본론은 여기 있다. 이게 다 머여!! 하나씩 알아봅시다... 이게 이래뵈도 OOP 서타일인데, 그거는 또 나중에 기회가 되면 얘기해주겠음.
머리 머리 머리
# 머리
def __init__ (self):
self.headnode = Node(0)
self.datacount = 0 # 연결 리스트의 길이
연결 리스트는 머리와 꼬리가 있다. 머리는 말 그대로 연결 리스트의 시발점이고, 앞 노드가 없다. 반대로 꼬리는 다음 노드의 주소를 갖고 있지 않고, 연결 리스트 맨 뒤에 있다.
노드 추가
# 데이터 넣기
def add_node (self, _value):
# 새로운 노드 생성
new_node = Node(_value)
pointernode = self.headnode
# 마지막 노드가 어디 있나
while True:
# 찾았으면 뒤에 추가해라
if pointernode.nextnode == None:
break
else:
pointernode = pointernode.nextnode
pointernode.nextnode = new_node
# 카운터 추가
self.datacount += 1
리스트를 만들고 거기에 노드를 추가하려면 쟤가 필요하다. 기본적으로 맨 앞... 그니까 헤드를 만들 때를 빼면 연결 리스트에 새 노드를 추가하는 과정은 1) 새 노드를 만들고 2) 새 노드와의 연결점을 맨 뒤 노드에 추가한다 이다. 얘는 그래도 좀 심플한 편이여...
특정 번호로 노드 찾기
# 내놔
def where_node (self, _position):
target_index = _position - 1
# 잘못 입력했다면
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
# 여기가 본론임...
else:
# 헤드에서 시작해서 우리가 찾는 포지션 값까지 가야 한다.
pointernode = self.headnode
# 전체 이동 횟수를 계산하고
move_cnt = target_index + 1
# 그만큼 반복 아...
for i in range(move_cnt):
# 가야돼 아...
pointernode = pointernode.nextnode
# 드디어 나옴
return pointernode.value
리스트로 치자면 인덱싱이다. 이 코드에는 약간의 변형을 했는데, 원래는 연결 리스트의 3번째 노드에 들어있는 값을 보고 싶으면 2를 입력해야 하는데(콤퓨타는 0부터 셈) 이게 너무 직관적이지 않은겨... 헷갈려요 사람... 그래서 3 입력하면 3번째 노드의 값이 나오게끔 변형했다.
그럼 특정 번호로 노드를 찾는 과정에 대해 알아보자… 뭐 사실 알아보고 자시고 할 것도 없이 찾을 순번 될 때까지 반복문 도는 게 다긴 한데… 왜 이렇게까지 해야 하나요? 연결 리스트는 원래 그렇습니다. 배열은 일렬로 줄줄이 소세지라서 걍 첫 번째 값 찾고 하나 둘 셋 하면 되지만 쟤는 얘는 여기있고 얘 따라가면 여기있고 걔 따라가면 또 여기있고…가 꼬리까지 반복이다. 연결 리스트는 삭제, 수정, 추가가 상대적으로 용이한 대신 탐색이 좀 오래 걸리는데, 특히나 찾을 노드가 뒤에 있을수록 더 오래 걸린다. 3번 노드면 0->1->2->3만 가면 되지만 7번 노드면 0->1->2->3->4->5->6->7이거든.
사이에 끼워넣기
# 여기다 넣어줘
def insert_node (self, _position, _value):
# 수정할 포지션
target_index = _position - 1 # 3 입력하면 3번째 수정하려면 필요함
# prev: 하나 덜 감/curr: 정직하게 ㄱㄱ
# 2번때에 노드 끼워넣는거면 1, 2까지 갑니다.
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
# 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨?
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
else:
# 끼워넣을 노드
new_node = Node(_value)
# 노드를 끼워넣을 포지션과 그 앞 노드에 대한 정보가 필요함
# 그래서 두개지요
prev_pointer = self.headnode
curr_pointer = self.headnode.nextnode
move_cnt = target_index
for i in range(move_cnt):
prev_pointer = prev_pointer.nextnode
curr_pointer = curr_pointer.nextnode
# 노드 끼우는 순서: prev-노드-curr
prev_pointer.nextnode = new_node
new_node.nextnode = curr_pointer
# 아 맞다 카운터
self.datacount += 1
return
사이에 끼워넣는다는 건 1) 얘랑 2) 쟤(얘 앞에 있음) 사이에 노드를 새로 끼워넣는다는 얘기인데, 이건 어떻게 하느냐... 원리 자체는 간단하다. 앞의 노드 포인터를 추가할 애를 가리키게 하고, 추가할 애의 포인터가 뒤 노드를 가리키게 하면 된다. 그러니까 A와 B 사이에 C를 넣을거면 A의 포인터는 C를, C의 포인터는 B를 가리키게 하면 되는 것이다. 근데 뭐가 문제냐고? 저 노드들 출발선을 조절해야 할 거 아뉴... 반복문을 두 노드가 같이 돌게 되면 같은 횟수를 순회해야된다 이거지.
여기서 prev_pointer보다 curr_pointer가 하나 앞으로 가야 한다. 근데 둘이 출발선상이 같으면 종점이 같아지잖아요? 그러니까 하나 앞으로 가야 하는 노드는 출발선을 하나 앞으로 땡기면 된다는거다. 이거 두개 앞으로 땡기면 넥스트 넥스트 달아야되나... 백준 그 롱롱롱롱롱롱롱롱인가 그거냐
노드가 담은 값 바꾸기
# 바꿔줘
def change_node (self, _position, _value):
# 3을 입력하면 정직하게 2번째 인덱스를 바꾸기 위해서는 변환 절차가 필요하다.
target_index = _position - 1
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
# 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨?
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
else:
# 원리는 간단하다. 찾아라, 그리고 바꿔라.
move_cnt = target_index + 1
pointernode = self.headnode
for i in range(move_cnt):
pointernode = pointernode.nextnode
# 도착했으면 수정을 해야됩니다.
pointernode.value = _value
뺑뺑이 도는 건 똑같은데 걍 도착해서 값만 바꾸면 된다.
노드 삭제
# 빼줘
def delete_node (self, _position):
# 3을 입력하면 정직하게 2번째 인덱스를 지우기 위해서는 변환 절차가 필요하다.
target_index = _position - 1
if _position < 1:
print('순서값은 1보다 같거나 큰 정수입니다. ')
return
elif _position > self.datacount:
# 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨?
print(f'범위는 1부터 {self.datacount}까지입니다. ')
return
else:
# 그 포인터 앞에 있는 노드의 연결을 다음다음노드로 하면 된다. 연결만 끊으면 끝.
move_cnt = target_index
pointernode = self.headnode
for i in range(move_cnt):
pointernode = pointernode.nextnode
pointernode.nextnode = pointernode.nextnode.nextnode
# 아 맞다 카운터
self.datacount -= 1
return
연결 리스트에서 노드를 삭제하는 것도 원리 자체는 간단하다. 포인터가 다음다음 노드를 가리키게 하면 된다. 그러니까 A-B-C에서 B를 지우고 싶으면 A의 포인터가 C를 가리키게 하면 된다. 쉽죠? 솔직히 인서트 하고 나면 쟤는 선녀야...
전체 조회
# 잘 된겨?
def node_show (self):
# 헤드노드의 다음 노드가 없으면
if self.headnode.nextnode == None:
print('이 리스트는 텅 비었습니다. ')
return
pointernode = self.headnode
while True:
# 다음으로 렛츄고
pointernode = pointernode.nextnode
print(pointernode.value)
# 없으면 시마이
if pointernode.nextnode == None:
break
return
이건 뭐 별 거 없고, 연결 리스트를 머리부터 꼬리까지 쭉 돌면서 노드가 담고 있는 값을 출력하는 코드다. 연결 리스트의 꼬리는 다음으로 이어지는 게 없으니까 포인터 없어? 끝! 이 되는 것. 쉽죠?
3. 그 밑으로는 양 사이드에 1을 쓰고, 순차적으로 윗줄 양 옆의 수를 더한다. 그래서 3번째 줄은 1+1=2다.
4. 이하 반복.
토대 잡기
import sys
N = int(sys.stdin.readline())
# 첫번째 줄: 1
# 두번쨰 줄: 1, 1
# 세번째 줄: 1, 1+1, 1
# 네번째 줄: 1, 1+1+1. 1+1+1, 1
triangle = []
for i in range(N):
print(i)
일단 여기는 뭐 볼 거 없으니까 빠르게 다음으로 넘어가자.
삼각형 만들기
for i in range(N):
# range는 0부터 시작하기때문에 i도 0부터 시작한다.
# 그리고 각 행은 i+1개의 열을 갖는다. (꼭대기: i=0, 열 수=1)
rows = [1] * (i + 1)
print(rows)
여기서부터 잘 따라오십쇼.
일단 왜 i+1이냐... 답은 간단하다. python의 range는 시발점을 지정하지 않으면 0부터 시작이거든... 인덱싱도 다 0부터 시작이다. 그래서 1을 안 더하면 어떻게 되냐고? 맨 위층에 꼭지점이 안 생김. 그렇게 되면 N이 5일때 4까지만 나온다.
[1]
[1, 1]
[1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1, 1]
1만 들어있다고? 지금은 삼각형 형태만 만든거니까 1만 들어있는 게 정상이다.
내용물 채우기
다 왔으니까 좀만 더 참으십쇼. 이제 삼각형 뼈대를 만들었으니까 안에 내용물만 채우면 된다.
for i in range(N):
# range는 0부터 시작하기때문에 i도 0부터 시작한다.
# 그리고 각 행은 i+1개의 열을 갖는다. (꼭대기: i=0, 열 수=1)
rows = [1] * (i + 1)
for j in range(1,i):
# 그럼 이제 저 1만 있는 삼각형들의 안쪽을 채워볼까요?
# 가장 바깥을 제외한 안쪽은 위 행에서 인접한 좌우의 요소들을 더해서 값을 구한다.
rows[j] = triangle[i-1][j-1] + triangle[i-1][j]
triangle.append(rows)
print(*triangle)
주석 빼면 다섯줄밖에 안됨. 출력 빼면 네줄인데 이걸로 삼각형 내용물을 채울 수 있다. 위에서 우리가 뼈대를 만들었잖아요? 그럼 만든 뼈대를 채워야 하지 않겠음? 뼈대를 채우기 위해서는 내 위층에서 나랑 인접한 값(내 위에 양 옆에 둘)이 뭔지를 알아야 할 것 아닙니까. 그죠?
i가 1... 그니까 한줄일때는 쟤가 안 돌아간다. j가 1 이상 1 미만이 가능하겠수? 무슨 유니콘의 뿔도 아니고. 그래서 i가 2일때부터 j가 작동한다고 보시는 게 낫습니다. 그러면 j가 1일때 첫번째 열(인덱싱은 0부터라 맨 꼭대기는 rows[0]임)의 첫번째와 두번째를 더해야되는데 하나밖에 없으니까 1만 두 개 나온다. 그럼 그 밑에는요? 두번째열에 1 두개니까 그거 더하면 2죠. 양 옆은 더할 거 없으니까 1인거고.
import sys
N = int(sys.stdin.readline())
# 첫번째 줄: 1
# 두번쨰 줄: 1, 1
# 세번째 줄: 1, 1+1, 1
# 네번째 줄: 1, 1+1+1. 1+1+1, 1
triangle = []
for i in range(N):
# range는 0부터 시작하기때문에 i도 0부터 시작한다.
# 그리고 각 행은 i+1개의 열을 갖는다. (꼭대기: i=0, 열 수=1)
rows = [1] * (i + 1)
for j in range(1,i):
# 그럼 이제 저 1만 있는 삼각형들의 안쪽을 채워볼까요?
# 가장 바깥을 제외한 안쪽은 위 행에서 인접한 좌우의 요소들을 더해서 값을 구한다.
rows[j] = triangle[i-1][j-1] + triangle[i-1][j]
triangle.append(rows)
# 이거 이차원 배열이라 이렇게 안 하면 일렬로 나옴...
print(*triangle, sep="\n")
그래서 이건데... 출력에 왜 언패킹이 되어 있나요? 저게 이차원 배열입니다. 그래서 언패킹+구분자 없으면 대괄호 두개가 쌩으로 나오고요. 언패킹 해도 구분자 설정 안 하면 일렬로 나옵니다.
여러분들 한번씩은 다 그런 경험이 있을 것이다. 다른 사람이랑 장을 보건, 혼자서 장을 보건 집에 오면서 먹을 간식을 하나 사게 되는데, 계산을 마치고 간식을 먹으려고 봤더니 에엥? 간식이 장바구니 맨 밑에 들어가서 안보여요! 장바구니가 일종의 스택 역할을 해서 그런거다.
예? 그게 무슨 말이죠? 스택은 먼저 들어간 게 나중에 나온다. 그 간식을 맨 처음으로 장바구니에 넣고 다른 물건들을 넣었다면, 먼저 들어간 간식이 다른 물건에 묻히게 된다. 그렇다고 이동중에 장바구니를 들어낼 수는 없고… 씁. 이럴때는 간식을 따로 빼두자.
스택을 만들어보자-상자 만들기
스택은 장바구니, 혹은 상자, 혹은 부페 접시(그 부페가면 접시 쌓여있는)다. 그리고 여기서는 상자를 만들고, 상자 안에 물건을 적재하고, 꺼내고 할 것이다. 그러려면 상자가 있어야겠죠?
이게 상자다. 혹은 장바구니가 되기도 하고, 부페 접시가 되기도 하는데 아무튼 쌓을 수 있는거면 된다.
상자에 물건을 넣고 빼기
# 빈 공간에 접시를 쌓아보자.
def push(self, data):
self.items.append(data)
부페에 가면 테이블에 접시를 두는 공간이 있다. 그 공간 중 하나에 접시들을 차곡차곡 쌓는 코드다.
# 손님이 접시를 하나씩 가져간다.
def pop(self):
pop_object = None
# 접시 스택이 없다면 없다고 해
if self.isEmpty():
print("스택이 비었습니다.")
# 아니면 접시 하나 줘
else:
pop_object = self.items.pop()
return pop_object
여기는 왜 코드가 길어요? 우리가 부페에서 접시를 왜 쓰는지를 생각해보자. 부페는 접시 스택이 여러 줄인데, 손님들이 접시를 가져가다보면 중간에 비는 줄이 나오게 될 것이다. 이 경우에는 비었다는 게 눈에 보이니까 아, 비었구나. 하고 다른 줄에서 접시를 가져가겠지만, 이게 뚜껑이 닫혀있는 상자라면? 아니면 프링글스 통이라면? 누군가가 그거 빈 상자야, 혹은 그거 다 먹은거야라고 얘기를 해 줘야겠죠? 그거다.
보자… 안에 뭐가 들었나…?
def peek(self):
top_object = None
# 접시 스택이 없다면 없다고 해
if self.isEmpty():
print("스택이 비었습니다.")
# 아니면 뭐가 있는지 보여줘
else:
top_object = self.items[-1]
return top_object
이건 또 뭔가... 손님은 부페 접시를 당연히 가져가서 음식 담는 용도로 쓰지만, 내가 부페 직원이라면 접시 스택을 확인하는 목적이 접시가 부족한가를 보고 부족하면 리필하기 위해서일 것이다. 여기서 접시가 부족한가? 를 보는 코드가 이거다. 역시나 접시가 없으면 확인하고 채워야 하기 때문에 그 역할을 하는 코드가 있는 것 뿐이다.
isEmpty(): 어어 비었다
def isEmpty(self):
# 기본 플래그: 안비었어
is_empty = False
# 스택의 길이가 0이라면 플래그가 바뀐다
if len(self.items) == 0:
is_empty = True
return is_empty
이건 일종의 플래그인데, 디폴트값은 안 비었다이다. 그리고 스택의 길이가 0이면 비었다로 바뀐다.
이렇게 하면 스택 안에 든 게 안 나오고 <__main__.stack object at 0x1008f0980>라고 뭐가 튀어나온다. 아니 이게 머여?
def show(self):
if self.isEmpty():
print("스택이 비었습니다.")
else:
print(self.items)
는 클래스 안에 스택 전체를 볼 수 있는 것도 추가함… 저게 반복문으로 될 것 같죠? 응 아니야.
큐
큐는 스택과 달리 먼저 온 사람이 먼저 나가는 구조다. 스택이 부페 접시, 프링글스였다면 큐는 대기열(게임이나 이런데 있는), 출근시간대 메가커피 앞에 있는 줄(미리 안 시키면 똥줄타요…), 수강신청 대기열이다. 근데 구현하려고 찾아보니 다 리스트 아니면 모듈이라 지피티한테 버스터콜함… ㅋㅋ
대기장소(?) 만들기
def __init__(self):
self.items = []
큐가 줄을 서는거지 우리 보통 줄 서는 장소는 정해져 있습니다. 메가커피에서 커피 기다리는 사람들은 커피가 나오는 곳 앞에 줄을 서 있고, 수강신청이나 콘서트 예매같은 거 하는 사람은 사이트에서 기다리잖음. 그런겁니다.
출근길에 메가커피에서 커피를 주문하는 건 인큐다. 왜죠? 커피를 받기 위한 대기열에 줄을 선 거니까요. 그리고 내 커피가 나와서 커피를 받아가는 건 디큐다. 왜죠? 커피를 받고 대기열에서 나와서 내 갈 길 가는거니까요. 그리고 위에 있는 코드는 메가커피에 커피를 주문하고 대기열에 줄을 선 거다.
# 큐에서 빼는것(커피 받았다 회사가자)=디큐
def dequeue(self):
# 큐가 비었나요? (대기열이 없나요?)
if self.isEmpty():
print("큐가 비었습니다!")
return None
# 대기열이 있다면 맨 앞 손님의 주문을 해결하자
else:
return self.items.pop(0)
이건 디큐다. 스택처럼 디큐 코드에도 뭔가 있는데... 메가커피가 항상 붐비는 게 아니라 상대적으로 한산한 시간대가 있다. 뭐 예를 들자면 오후 한 2~3시쯤... 그때는 대기열이 없기때문에 주문도 안 들어오고, 커피를 내 갈 필요도 없다. 하지만 대기열이 있다면 맨 앞의 손님이 주문한 커피를 해결해서 큐에서 내보내야 한다.
대기열이 얼마나 있나?
# 보자... 지금 주문이 얼마나 밀렸지?
def peek(self):
# 손님이 있나?
if self.isEmpty():
print("큐가 비었습니다!")
return None
# 아, 있네.
return self.items[0]
이건 사실 대기열이라기보다는 먼저 온 주문이 뭔지를 파악하는 것에 가깝다. 봐봐요. 5번 고객이 라떼를 시켰는데 6번 고객이 아아를 시켰어, 그러면 라떼 먼저 처리해야 할 거 아님. 고객의 시간과 인내심은 유한하잖아요. 그래서 손흥민 골 넣는 날은 메가커피 갈 때 각오해야됩니다…
주문 있냐?
def isEmpty(self):
# 기본 플래그: 안비었어
is_empty = False
# 스택의 길이가 0이라면 플래그가 바뀐다
if len(self.items) == 0:
is_empty = True
return is_empty
스택에 썼던 그 코드 맞는데, 큐에서는 약간 의미가 달라서 접시탑 비었냐? 가 아니라 대기열 비었냐?가 된다.
주문 얼마나 있음?
# 대기열 얼마나 있음?
def size(self):
return len(self.items)
스택에 넣어도 될듯. 이 코드는 말 그대로 큐의 크기를 반환한다.
큐 전체 보여줘
# 큐 전체를 볼 수 있다.
def show(self):
if self.isEmpty():
print("큐가 비었습니다!")
else:
print(self.items)
