전체 글
연구에서 어떤 인구 집단을 지칭할 때, “코호트(cohort)”라는 용어가 자주 등장한다. 이번 글에서는 이 개념을 간단히 정리해보고자 한다. 1. 코호트란 무엇일까?코호트는 단순히 “사람들의 집단”이라기보다는, 연구 설계에서 특별한 의미를 가지는 집단을 의미한다. “group”이라고 하기에는 의미가 너무 넓고,“population”이라고 하기에는 지나치게 일반적이기 때문에,이 둘을 구분하기 위해 “cohort”라는 용어가 사용된다. 예를 들어, 다음과 같은 집단이 코호트에 해당한다.같은 해에 태어난 사람들특정 연령대에 속한 집단동일한 환경이나 조건에 노출된 사람들이처럼 코호트는 명확한 기준과 동일한 시점(또는 시기)을 바탕으로 정의된다. 2. 왜 “집단(group)”이 아니라 “코호트”라는 말을 사용할..
단계별 조건부 분석은 어떤 복잡한 인과관계가 얽혀있는 경우, 그것들을 한번에 다 보는 게 아니라 하나씩 추가하면서 각 변수의 실제 영향력을 추적하는 방법이다. 1.왜 필요할까?예를 들어, "아이스크림을 많이 파는 날에 익사 사고가 많다"는 데이터가 있다고 하자. 아이스크림이 익사를 유발하는 것일까? 그건 절대 아닐 것이다. 두 현상 모두 더운 날씨라는 제 3의 변수 때문에 동시에 일어나는 것이다. 이런 변수를 "교란 변수(confounder)"라고 부른다. 단계별 조건부 분석은 바로 이 교란변수들을 단계적으로 통제하면서, "진짜 원인"과 "그냥 같이 움직이는 것"을 구분해낸다. 2. 커피와 집중력 (효과가 살아남는 경우)그렇다면, 커피와 집중력같이 상관있어 보이는 것은 어떨까? 단계별 조건부 분석을 통해..
한마디로, Genotype 데이터(SNP) + Expression 데이터(mRNA 발현량)로 특정 유전자 변이가 유전자 발현에 영향을 미치는지를 통계적으로 찾아내는 분석이다. 단순히 DNA 서열의 변이를 찾는 것이 아니라, 그 변이가 유전자 발현이라는 표현형(phenotype)에 어떤 영향을 주는지를 분석한다. eQTL 분석 과정 (Workflow)일반적인 과정은 다음과 같다. ① 데이터 준비- Genotype 데이터: SNP array 또는 WGS로 각 개체의 유전형 정보를 얻는다.- Expression 데이터: RNA-seq을 통해 각 유전자의 발현량(mRNA 수준)을 측정한다.- 보통 수백 명 이상의 샘플이 필요하다. (통계적 검정력 확보를 위해) ② 전처리- Genotype: QC(품질 관리) ..
한 생물의 전체 유전체(genome)의 DNA 염기 서열을 모두 읽어내는 기술 특정 유전자만 보는 것이 아니라. 모든 DNA(coding + non-coding 영역)을 분석한다. WGS 과정 (Workflow)일반적인 과정은 다음과 같다. ① DNA 추출- 세포에서 genimic DNA를 추출한다. (혈액, 조직, 박테이라 배양 등에서) ② DNA fragmentation- DNA를 짧은 조각(fragment)로 분해한다. (보통 150-500bp (lllumina 기준)) ③ Sequencing- 각 DNA fragment의 염기서열을 읽는다. (이를 위한 읽는 기계들이 존재한다.) ④ Read alignment- 얻어진 sequence read를 reference genome에 정렬한다. - 여기..
그래프는 두 개의 점을 선으로 연결한다. Alice와 Bob이 친구면 두 사람을 선 하나로 잇는다. 간단하고 직관적이다. 문제는 현실이 항상 이렇지 않다는 것이다. 회의실 예약을 생각해보자. Alice, Bob, Charlie가 월요일 오전 회의에 참석한다면, 이 관계를 어떻게 표현할까? 그래프로는 각자 회의와 따로 연결된다. 하지만 실제로는 세 사람이 동시에 있어야 회의가 성립한다. Alice 혼자서는 회의가 아니다.이게 그래프의 근본적 한계다. 항상 둘씩만 연결하기 때문에 "함께"를 표현할 수 없다. 1. 그래프로 표현할 수 없는 것들이 문제는 여러 곳에서 나타난다. 요리 레시피를 보자. 카레를 만들려면 감자, 당근, 양파, 고기가 모두 필요하다. 감자만으로는 안 된다. 넷이 함께 있어야 카레가 된다..
분자생물학적 현상은 유기적으로 연결된 구조를 가진다. 이를 분석해본 결과 그래프 구조로 표현할 수 있음을 발견했다. 본 노트는 분자생물학적 기작을 그래프로 표현하는 방법과 그 특징을 정리한다. 1. 그래프 표현의 출발점분자생물학적 시스템을 수학적으로 표현하기 위해 그래프 G = (V, E)를 사용한다. 여기서 V는 노드(node)로 분자들을 나타내고, E는 엣지(edge)로 분자 간 상호작용을 나타낸다. 1.1. 노드를 무엇으로 볼 것인가가장 직관적인 방법은 분자 개체를 노드로 보는 것이다. 유전자, 단백질, RNA, 대사물질이 각각 하나의 노드가 된다. 예를 들어 lac operon 시스템에서는 lacI 유전자, LacI 단백질, lac 오페론, lactose가 모두 개별 노드로 표현된다. 분석 목적에..
수능 미적분 30번 문제를 풀 때를 생각해보자. 여러 조건들을 하나씩 확인하면서, "이건 아닌 것 같은데?"라는 직감으로 가지치기를 한다. 우리는 자연스럽게 가능성을 좁혀가며 답을 찾는다. 이런 과정을 체계적으로 표현할 수 있을까? 조건들을 트리 형태로 정리하면 문제 해결 과정을 시각적으로 이해할 수 있고, 컴퓨터로도 풀 수 있다. 이를 상태 공간 트리(State Space Tree)라고 한다. 이번 글에서는 상태 공간 트리의 개념과 이를 활용하는 알고리즘을 이야기해보려 한다. 1. 상태 공간 트리란?상태 공간 트리는 문제를 해결하는 과정에서 거쳐갈 수 있는 모든 상태를 노드로 나타낸 트리 구조다. 각 노드는 문제 해결의 한 단계를 의미하며, 간선은 한 상태에서 다른 상태로의 전이를 나타낸다. 왜 굳이 ..
1. Gene Therapy(유전자 치료)란 무엇인가?Gene Therapy(유전자 치료)는 질병을 일으키는 비정상적인 gene(유전자)을 교정하거나, 정상적인 gene(유전자)을 세포 내로 도입하여 질병을 치료하는 방법이다. 이 치료법의 핵심 아이디어는 virus(바이러스)가 본래 가진 특성, 즉 자신의 genetic material(유전물질)을 host cell(숙주 세포)에 효율적으로 전달하는 능력을 치료 목적으로 활용하는 것이다. 예를 들어, 20세 이상에서 필연적으로 발병하는 암 gene을 가진 환자가 있다고 가정해보자. Gene Therapy를 통해 이 비정상 gene을 제거하고 정상 gene으로 대체함으로써 암 발병을 예방하거나 지연시킬 수 있다. 2. Gene Therapy는 어떻게 이루어..
2012년, 존스 홉킨스 대학 연구진은 인간 암의 약 3분의 2가 환경이나 유전이 아닌, 단순한 DNA 복제 오류에서 비롯된다는 논문을 발표했다. 37조 개 세포가 매일 30억 글자짜리 DNA를 베껴 쓰고 있으니 오타가 나는 건 놀랍지 않다. 놀라운 건 그 오타 하나가 20년 뒤 암이 된다는 사실이다. 이 글에서는 돌연변이(Mutation)라는 렌즈를 통해 암이 발생하는 전체 과정을 추적한다. 1. 체세포 돌연변이 vs 생식세포 돌연변이DNA 복제 오류, 즉 돌연변이는 어디에서 발생하느냐에 따라 성격이 완전히 달라진다. 체세포 돌연변이(Somatic Mutation)는 우리 몸의 일반 세포에서 후천적으로 생긴다. 다음 세대로 유전되지 않지만, 해당 세포 안에 축적되면서 암의 직접적인 원인이 된다. 생식세..
더 빠른 방법은 없을까? 데이터를 탐색하고, 삭제하고, 저장하는 작업을 가장 빠르게 처리하려면 어떻게 해야 할까? 알고리즘 수업에서 배운 이진 검색 트리는 이런 작업들을 평균 O(log n) 시간에 처리할 수 있는 훌륭한 자료구조다. 하지만 이보다 더 빠른 방법이 있다. 바로 해시 테이블(Hash Table)이다. 해시 테이블은 평균적으로 O(1), 즉 상수 시간에 탐색, 삽입, 삭제를 수행할 수 있다. 이번 글에서는 해시 테이블이 어떻게 이런 놀라운 성능을 내는지, 그리고 실제로 사용할 때 주의해야 할 점은 무엇인지 이야기해보려고 한다. 0. 검색 트리먼저 검색 트리의 시간 복잡도를 살펴보자.이진 검색 트리(BST): 평균 Θ(log n), 최악 Θ(n)균형 잡힌 이진 검색 트리(AVL, Red-Bla..
문서에서 특정 문자를 찾아보자. 우리는 당연하게 Ctrl+F를 누른다. 그런데 컴퓨터는 어떻게 그렇게 빠르게 찾아낼 수 있을까? 5글자 정도야 처음부터 하나씩 비교해도 금방 찾을 수 있다. 하지만 DNA 서열처럼 수십억 글자 속에서 특정 패턴을 찾아야 한다면? 단순하게 하나씩 비교하는 방식으로는 턱없이 느리다. 오늘은 이 문제를 똑똑하게 해결하는 문자열 매칭 알고리즘에 대해 알아보자. 1. 원시적 매칭 원시적 매칭은 가장 직관적인 방법이다. 텍스트의 처음부터 끝까지 한 칸씩 이동하면서 패턴과 일치하는지 확인하는 것이다. 구체적으로 말하면, 텍스트 A[1...m], A[2...m+1], ..., A[n-m+1...n]이 패턴 P[1...m]과 일치하는지 순서대로 비교한다. 예를 들어 텍스트 "with ev..
혼성화(Hybridization)는 DNA나 RNA의 상보적인 염기 서열이 수소 결합을 통해 이중나선을 형성하는 현상이다. 이 단순한 원리가 현대 분자생물학에서 가장 강력한 도구 중 하나가 된 이유는, 특정 DNA나 RNA를 정확하게 찾아내고 분석할 수 있기 때문이다. 혼성화 기법은 크게 세 가지 응용 분야로 나뉜다. 서브트랙티브 혼성화는 건강한 유전자와 돌연변이 유전자를 비교하여 질병 관련 변이를 찾아낸다. mRNA 혼성화는 세포에서 실제로 발현되는 유전자만을 선택적으로 분리한다. FISH는 세포 내에서 특정 DNA의 위치를 직접 눈으로 확인할 수 있게 해준다. 1. 서브트랙티브 혼성화 - 변이 유전자 찾아내기서브트랙티브 혼성화는 두 샘플 간의 유전자 발현 차이를 비교하는 방법이다. 예를 들어 건강한 ..
1. 바이오테크놀로지란 무엇인가?바이오테크놀로지는 생물학적 시스템, 살아있는 유기체 또는 그 파생물을 이용하여 특정 목적을 위한 제품이나 공정을 만들거나 수정하는 모든 기술적 응용을 의미한다. 이는 생물의 대사능력, 유전정보, 단백질 등을 인간의 필요에 맞게 활용하는 기술 분야다. 바이오테크놀로지가 다루는 범위는 매우 넓다. 미생물의 발효를 이용한 식품 생산부터 시작해서, 동물의 췌장 세포에서 인슐린을 추출하는 것, 식물의 유전자를 조작해서 새로운 품종을 만드는 것, 그리고 박테리아에 인간의 유전자를 삽입해서 의약품을 생산하는 것까지 모두 포함된다. 2. 바이오테크놀로지의 발전바이오테크놀로지는 경험적 활용에서 출발하여 현대의 유전자 수준의 조작으로 발전해왔다. 초기에는 미생물의 자연적인 대사능력을 관찰하..
친구 관계를 생각해보자. 철수는 영희와 친구고, 영희는 민수와 친구다. 그렇다면 철수와 민수는 같은 친구 그룹일까? 당연히 그렇다. 이제 친구가 100만 명이라면? 철수와 민수가 같은 그룹인지 확인하려면 모든 친구 관계를 일일이 뒤져야 할까? Union-Find라는 자료구조는 이 문제를 빠르게 해결한다. 그룹을 합치고(Union) 찾는(Find) 작업을 효율적으로 처리한다. 이번에는 Union-Find가 어떻게 동작하는지 알아보자. 1. 집합 처리Union-Find가 다루는 것은 집합이다.집합이란 순서와 중복이 없는 원소들을 갖는 자료구조다. 특히 Union-Find가 다루는 집합은 특별하다. 여러 개의 집합이 존재하고, 이들은 서로 겹치지 않는다. 이를 '상호 배타적 집합'이라고 한다. 이런 집합들을 ..
수업시간에 피보나치 수열의 50번째 항을 구하는 프로그램을 짜기로 했다. 어떤 사람은 1시간이 지나도 답이 나오지 않았지만, 다른 사람은 1초 만에 문제를 해결했다. 대체 무슨 차이가 있었던 걸까? 1. 재귀적 해법첫 번째 사람이 사용한 방법은 재귀였다. 피보나치 수는 다음과 같은 점화식으로 정의된다.f(n) = f(n-1) + f(n-2) 이를 그대로 코드로 옮기면 다음과 같은 의사코드가 나온다.점화식을 그대로 구현했으니 직관적이고 간결하다. 하지만 실제로 f(7)을 계산하는 과정을 펼쳐보면 문제가 드러난다.같은 값을 여러 번 계산하고 있다. f(3)은 5번, f(2)는 8번 계산된다. n이 50이 되면? 이 중복은 수백만 번으로 늘어나고, 1시간이 지나도 답이 나오지 않는 상황이 벌어진다. 재귀는 중..
이전에 읽으면 좋은 글 그리디 알고리즘(Greedy Algorithm)과 그 적용급한 약속이 있어 건물 로비에 도착했다. 두 대의 엘리베이터가 있는데, 하나는 5층에, 다른 하나는 12층에 있다. 당신은 어느 버튼을 누를까? 당연히 5층에 있는 엘리베이터다. 지금 당장 가장 가insight0591.tistory.com그리디 알고리즘을 공부하다 보면 늘 궁금한 게 있다. 어떤 문제는 그리디로 최적해를 찾을 수 있고, 어떤 문제는 안 된다. 대체 그 차이가 뭘까? 이 질문의 답이 바로 매트로이드(Matroid)다. 이번 글에서는 매트로이드가 무엇인지, 왜 그리디 알고리즘과 관련이 있는지를 알아보려고 한다. 1. 그리디는 왜 실패할까?먼저 그리디가 실패하는 경우를 살펴보자. 대표적인 예시가 배낭 문제(Knap..
급한 약속이 있어 건물 로비에 도착했다. 두 대의 엘리베이터가 있는데, 하나는 5층에, 다른 하나는 12층에 있다. 당신은 어느 버튼을 누를까? 당연히 5층에 있는 엘리베이터다. 지금 당장 가장 가까운 선택이 결과적으로 가장 빠른 해결책이 된다. 이처럼 "매 순간 최선의 선택"을 하는 방식은 우리 일상에서 자주 사용하는 의사결정 방법이다. 그리고 이것이 바로 그리디 알고리즘(Greedy Algorithm)의 핵심 아이디어다. 이번 글에서는 직관적이면서도 강력한 이 알고리즘에 대해 알아보자. 1. 그리디 알고리즘의 구조그리디 알고리즘은 각 단계에서 가장 이득이 되는 선택을 반복하여 최적해를 구하는 방법이다. 이 알고리즘의 가장 큰 특징은 한 번 선택한 것을 번복하지 않는다는 점이다. 즉, 미래를 내다보지 ..
인스타그램에서 사람들의 팔로우 관계를 들여다보면 흥미로운 패턴이 발견된다. 어떤 사람들은 서로를 팔로우하며 아주 긴밀하게 연결된 그룹을 형성한다. A가 B를 팔로우하고, B가 C를 팔로우하며, C가 다시 A를 팔로우하는 식이다. 그래프 이론에서는 이런 구조를 강연결 요소(Strongly Connected Component, SCC)라고 부른다. 강연결 요소란 방향 그래프에서 어떤 정점 집합 내의 모든 정점 쌍이 서로 도달 가능한 최대 부분 그래프를 의미한다. 쉽게 말해, A에서 B로 갈 수 있고 B에서 A로도 갈 수 있다면, A와 B는 같은 강연결 요소에 속한다. 즉, 사이클을 통해 서로 연결된 정점들의 집합이 강연결 요소다. 이번 글에서는 방향 그래프에서 이러한 강연결 요소들을 효율적으로 찾아내는 알고..
네비게이션의 최단 경로는 어떻게 찾을까? 단순히 가장 짧아 보이는 길을 선택하는 방식으로는 정확한 경로를 찾기 어렵다. 도시에는 수많은 교차로와 도로가 얽혀있고, 모든 경로를 일일이 따져보는 것은 현실적으로 불가능하기 때문이다. 이 문제를 우아하게 해결한 사람이 바로 에츠허르 다익스트라(Edsger Dijkstra)다. 하지만 최단 경로 문제는 하나의 알고리즘으로 해결되지 않는다. 그래프의 특성에 따라 다른 접근이 필요하다. 이번 글에서는 다익스트라 알고리즘을 시작으로, 다양한 상황에 맞는 최단 경로 알고리즘들을 살펴보겠다. 1. 그래프의 표현: 가중치 인접 행렬(weight adjacent matrix)최단 경로 문제를 다루기 전에, 먼저 그래프를 어떻게 표현할지 정해야 한다. 우리가 다루는 것은 가중..
라면을 끓이는 상황을 떠올려보자. 냄비에 물을 붓고 불을 켠다. 그런데 물이 끓는 동안 가만히 기다려야 할까? 아니다. 그 사이에 봉지를 뜯고, 계란을 풀고, 그릇을 준비할 수 있다. 하지만 아무 순서로나 해도 되는 건 아니다. 물이 끓기 전에 면을 넣으면 제대로 익지 않고, 봉지를 뜯기도 전에 면을 꺼낼 수는 없다. 어떤 작업은 반드시 다른 작업이 끝난 뒤에야 시작할 수 있다는 것이다. 이런 의존 관계를 그래프로 나타내면 각 작업 간의 선후 관계가 명확해진다. 그렇다면 이 작업들을 어떤 순서로 해야 가장 빨리 라면을 끓일 수 있을까? 이번 글에서는 이런 문제를 해결하는 위상 정렬에 대해 알아보겠다. 1. 위상 정렬이란?→ 위상 정렬은 방향 그래프에서 각 정점들의 선후 관계를 지키면서 모든 정점을 일렬로..
문제 유형그리디 알고리즘 문제 풀이 과정 도출 과정1. 문제 구조 파악- 세준이는 +, -, 괄호를 가지고 식를 만들었다. 이후에 괄호를 없앴다.- 우리가 해야 하는 것은 식에서 괄호를 적절하게 쳐서 가장 최소의 값을 구하는 것이다. 2. 문제 풀이 전략 도출 과정1) 문제 재정의- 예로 들어 55-50+40이 있을 때, 55-(50+40)이 되어야 값이 최소가 된다. 즉, 55-50-40- 또, 10-20-30-40의 경우는 (10-20)-30-40이 되어야 값이 최소가 된다. 즉, 10-20-30-40- 하지만 50+20+20+30의 경우에는 어떤 것을 넣어도 상관이 없다.- 반면, 50+40-30-20의 경우에는 (50+40)-30-20 = 40이다.- 이 결과에 따라, 모든 연산자가 최대한 값을 ..
상상해보자. 여러 도시를 전선으로 연결해야 하는데, 전선 비용을 최소화해야 한다. 머리로는 "가장 짧은 것들만 골라서 연결하면 되지 않을까?" 싶지만, 막상 해보면 어디서부터 시작해야 할지, 이게 정말 최선인지 확신이 서지 않는다. 도시가 10개만 넘어가도 손으로 푸는 건 사실상 불가능하다. 다행히도 이런 최소 신장 트리 문제를 해결하는 깔끔한 알고리즘이 있다. 바로 프림과 크루스칼이다. 이번 글에서는 이 둘 알고리즘에 대해서 이야기해보도록 하겠다. 1. 최소 신장 트리(Minimum Spanning Tree, MST)본격적으로 알고리즘을 보기 전에, 우리가 풀려는 문제부터 정리하자. 목표는 모든 도시를 연결하되, 전선 비용을 최소화하는 것이다. → 위 그림을 보면, 원래 복..
문제 유형정렬 문제 풀이 도출 과정1. 문제 구조 파악- 수직선 위에 N개의 좌표 X1,X2,...,XN이 있다.- Xi의 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. ()- X1, X2,...,XN의 압축결과인 X1, X2,...,X'N를 출력하는 것이 문제 2. 문제 풀이 전략 도출1) 좌표 압축에 대한 공부- 먼저 좌표 압축에 대해서 알지 못했다. 그러므로 공부를 한 뒤 알고보니, 숫자의 작은 순서대로 0~로 구하는 것이다.- 하지만 같은 값인 경우 같은 숫자를 할당받는다. 2) 정렬 후 숫자 매핑 시 조건 사용- 가장 먼저 정렬을 한 뒤에 숫자를 매핑하면 되겠다는 생각을 했다.- 하지만 동일한 수의 내용을 매핑을 어떻게 하는냐가 문제다. 이..
복잡한 지하철 노선에서 가장 빠른 환승 경로를 찾아본 경험이 있을 것이다. 우리는 노선표를 보면서 가장 적절한 지점을 찾게 된다. 우리가 대체 어떻게 이를 찾았을까? 겉보기에는 단순한 시각적 탐색처럼 느껴지지만, 사실 이 과정에는 일정한 규칙이 숨어 있다. 사실 우리는 알게모르게 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)을 하여 찾았을 것이다. 이번 글에서는 이 두 방법에 대해서 이야기해보려고 한다.1. 넓이 우선 탐색(Breadth-First Search)어떤 지점에서 출발해 주변을 먼저 살펴보고 싶은 상황이 있다. 가까운 선택지를 모두 확인한 뒤, 그다음 단계로 넘어가는 방식이다. 지하철에서 “일단 바로 연결된 역들을 먼저 보고, 그다음에 그다음 역들을 보자”라는 사고와 비슷하다 너비 우선 ..
문제 유형그래프 탐색 기법(넓이 기반 탐색 기법) 문제 풀이 도출 과정1. 문제 구조 파악- 지도가 주어지면 모든 지점에 대해서 목표 지점까지의 거리를 구하라- 움직이는 것은 가로, 세로밖에 안된다.- 0은 갈 수 없는 곳 1은 갈 수 있는 곳 2는 목표지점이다.- 해야하는 건 2라는 숫자를 목표로 A까지 가는 데 걸리는 움직인 칸의 거리를 A자리에 두면 된다. 2. 문제 풀이 전략 도출 과정1) 넓이 기반 그래프 탐색 기법- 2라고 적힌 곳을 먼저 찾고 여기서 부터 넓이 기반 탐색을 시도한다.- 칸을 옮기면서 count를 +1하고 그 다음 count는 이전에 있었던 자리의 count에 +1을 한다.- 0을 만나면 그쪽은 가지 못하게 만든다. 코딩from collections import dequeN, ..
읽으면 좋은 글 그래프(Graph)와 그래프 용어페이스북 친구 관계나 항공 노선처럼 우리 주변에는 수많은 연결망이 존재한다. 그렇다면 이 방대한 연결 관계를 효율적으로 표현하려면 어떻게 해야 할까? 바로 그래프라는 자료구조가 그 해insight0591.tistory.com 자료구조에서 정점 잡합과 간선들의 집합들로 이루어진 수학적 구조다. 그렇다면 이 구조를 어떻게 표현할까? 이번 글에서는 그래프를 표현하는 방법을 이야기해보도록 하겠다. 1. 인접 행렬(Adjacency Matrix)을 이용한 방법그래프를 표현하는 방법은 가장 먼저 2차원 배열로 표현하는 방법이 있다.이 내용을 인접 행렬이라고 하는데 위처럼 연결이 안된 경우 0, 연결 된 경우 1로 표현하는 방법을 사용하면 된다.만약에 가중치가 있다면 ..
페이스북 친구 관계나 항공 노선처럼 우리 주변에는 수많은 연결망이 존재한다. 그렇다면 이 방대한 연결 관계를 효율적으로 표현하려면 어떻게 해야 할까? 바로 그래프라는 자료구조가 그 해답이다. 여기서 말하는 그래프는 미적분에서 보는 좌표 그래프와는 다르다. 이번 글에서는 그래프 자료구조가 무엇인지 자세히 살펴보겠다. 1. 그래프 그래프는 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것을 말한다. 위의 내용과 동일하다. 이러한 구조는 다:다(M:N) 관계를 보여준다. 이를 수식으로는 $$G = (V, E)$$로 표현되는데 여기서 V는 정점(노드)의 집합, E는 간선(링크)의 집합이다. 이러한 그래프는 여러 종류가 있다. 가중치에 따라서 가중치가 없는 그래프, 가중치 그래프, 방향이 있..
문제유형최대 힙 / 구현 문제 풀이 과정1. 문제 인식- 최대 힙을 만드는 문제- 최대 힙의 삽입(생성), 출력(가장 큰거 출력)을 구현 하는 문제(탐색은 구현하지 않음)- 출력 시 만약에 값이 없으면 0 출력 2. 문제 풀이 도출 과정1) 구현 구조 생각하기(최대 힙)- 최대 힙을 구현하는 문제다. 힙을 구현하는 데 사용되는 heapq라이브러리가 있다. 하지만 이는 최소 힙만 구현을 할 수 있다. 그러므로, 실제로 최대 힙을 구현해보도록 하겠다.- 필요한 것은 push, pop이다.- 이를 위해 push에서는 값을 맨 아래 노드에 넣고 위로 올리면서 값들을 조정하는 _heapify_up이 필요하며,- 이를 위해 pop에서는 꺼낼 값(여기서는 가장 큰 값만)을 맨 아래와 교환한 후 꺼낼 값을 없앤 뒤에,..
