Hyun's Wonderwall

따끈따끈한 소식! 어제 6월 27일 장충체육관에서 열린 Innovators Hive Seoul 2024 행사에 오거나이저로 참여하였다. 장충체육관은 밴드 콘서트를 보러 온 적이 있었는데 이곳에 일하러 오다니 감회가 무척 새로웠다. 현수막이 가장 먼저 반겼고 계단, 유리창 벽, 깃발까지 구글의 색깔로 알록달록 꾸며져 있었다. 기념으로 받은 티셔츠~!! Innovators Hive의 앞에 Google Cloud Summit 행사가 진행되어서, 대기하면서 이 행사도 조금 볼 수 있었다. 이렇게나 많은 분들이 모이는 행사에 와 있는 것이 신기해서 마음이 들떴다. 나는 GDSC 이화여대 소속으로 같은 동아리 멤버들과, 그리고 행사를 주관하신 GDG Seoul 분들과 Google Cloud Skills Boost ..

방 정리를 하다가 여태 모은 명찰 목걸이들을 모아 사진을 찍었다. - 제일 왼쪽부터 소개 - // 2022 1 - 2022 MaKING Jam(게임잼) TF // 2023 2 - 2023 NDM 게임전시회 참가 3 - 제1회 UNIJAM(게임잼) 기획자로 참가 4 - UNICON 2023 TF 5 - GDSC Ewha Server 멤버 6 - 2023 MaKING Jam TF 7 - GDSC Ewha Home Coming Day (행사 참여) 8 - 42서울 10기 카뎃 오리엔테이션 // 2024 9 - 눈꽃톤(서비스 개발 해커톤) 참가 10 - 제2회 UNIJAM TF 11 - 2024 NDM 게임전시회 참가 12 - 42서울 본과정 출입 카드 13 - GDSC Ewha 멤버 카드 어제 GDSC Ewh..

Minimum Spanning Tree- 무방향 연결 가중치 그래프. n개의 모든 정점 n-1개의 간선으로 연결.- MST는 유일하지 x 전체 트리의 가중치합.. GENERIC-MST -> A는 매 반복에서 선택된 안전간선들의 집합.A에 대해 safe edge (u,v)를 찾아서 A에 합한다. 그것을 A 가 최소신장트리 되기 전까지 반복GENERIC-MST(G,w) A 크루스칼(Kruskal) 알고리즘- forest를 이룸.- 가중치값 최소 간선 선택함. (cycle 생기지 않게)프림(Prim) 알고리즘- single tree가 계속 확장됨. (시작정점o)- 트리에 있지 않은 정점을 트리에 연결시키는 가중치값 최소 간선 선택함. Kruskal 알고리즘의 실행- 간선이 잇는 정점 이미 같은 집합 안에 있..

그래프 G = (V,E)- 정점 V, 간선 E.- 무방향, 방향 그래프- 차수: 인접 간선의 개수 (방향: in-degree, out-degree / 무방향: degree)- weighted graph 가중치 그래프- connected graph 연결 그래프. strongly connected 강연결 그래프.- 희소 sparse, 밀집 dense - 스택, 큐 그래프로 표현 가능 인접행렬 Adj[i][j]. Θ(V^2) 공간 필요인접리스트 Adj[v] = {1, 2}. Θ(V+E) 공간 필요. 시간복잡도 O(n)- 인접리스트 무방향이면 값 2번 있어야. 가중치그래프는 노드 (key,value) 로 구성.- |adj[v]| = out-degree 갯수 (각 정점의 외차수의 개수만큼 인접노드.)- 삭제랑 탐..

Huffman Codes 허프만 압축 (허프만 코드)- Binary character code. 각 문자는 고유 이진 문자열로 표현됨.* Fixed-length code: 고정길이 방식 (6개 문자 나타내는데 3bit 필요.)* Variable-length code: 가변길이 방식 (등장 빈도수 고려해 codeword 부여 가능. 자주등장-짧은 codeword. 굿) Prefix Codes: 어떤 codeword도 다른 codeword의 접두사가 아님- 인코딩과 디코딩에 용이. 각 문자를 나타내는 코드워드를 차례대로 concat하고 쪼개면 됨.  (인코딩) "abc" -> 0.101.100 = 0101100 | (디코딩) 001011101 = 0.0.101.1101 -> "aabe"- 문자는 이진트리의 ..

Greedy Algorithms 그리디 알고리즘: 각 단계에서 최적의 수를 찾아 전역 최적해를 구함.- ex) 수업 시간표 짜기: (1) 젤 빨리 끝나는 과목 먼저 신청 (2) 첫번째 과목 끝난후 시작해서 젤 빨리 끝나는 과목 신청- 그리디 알고리즘은 지역 최적해로 전역 최적해를 구하는 방식. DP로 얻은 최적해보다 덜 최적일 수 있음. Activity Selection Problem 행동 선택 문제- 입력: n개의 행동이 담긴 집합 S = {1,2,..n}. 시작 시간 si, 종료 시간 fi라 할때 행동 i는 [si,fi)를 차지함.- 목표: 호환가능한. 안겹치는 행동들로 최대 개수의 행동을 하기. (시간을 얼마나 쓰는진 고려대상x)S = { [1,4), [5,7), [2,8), [3,11), [8,1..

12.1동적 프로그래밍(DP): 격자(배열) 만들어 사용- 분할정복 DAC와의 비교: 문제를 부분 문제로 나누어 해결하는 것이 비슷.- DAC는 하위 문제들이 서로 독립적, DP는 서로 연관.- 하위 문제들이 겹침 -> DAC는 중복 계산하지만 DP는 table에 저장하는것으로 단 1번만 계산. DP 알고리즘 수립1. 최적해의 구조 특징을 찾는다.2. 최적해의 값을 재귀적으로 정의한다.3. 최적해의 값을 상향식(bottom-up)으로 정의한다.4. 계산된 정보들로부터 최적해를 구성한다. DP 알고리즘의 구성요소1. Optimal sub-structures 최적의 하위구조2. Overlapping sub-problems 겹치는 부분문제3. Memoization and reuse 메모이제이션과 재사용 Opt..

Red-black tree- 트리의 균형을 보장 -> 최악의 경우에도 O(lgn) 시간에 수행.- color 속성: red 또는 black. // BST에서 상속되는 속성 key, left, right, p- 리프노드(빈 트리)들은 흑색인 경계노드 T.nil. 널포인터 역할임 // T.nil.color=black.- 루트노드의 부모노드도 T.nil - key가 있으면(nil아니면) 다 내부노드, 모든 내부 노드는 자식 2개 가짐. (nil 리프는 보여지지 않을 뿐)- 맨밑 경계노드 T.nil 만이 리프노드=외부노드. 항상 흑색. RBT는 (BST에서의) NULL 대신 T.nil 가리켜 사용 레드블랙트리의 특성1. 모든 노드는 red거나 black이다.2. 루트 노드는 black이다.3. 모든 리프 노드(..

Binary Search Tree (BST, 이진검색트리)- 동적 집합 연산을 지원하는 자료구조. (search, minimum, predecessor, successor, insert, delete)- 수행시간이 트리의 높이에 비례: O(h)- 한 노드의 왼쪽, 오른쪽 자식노드도 각 서브트리의 루트가됨 -> 재귀적으로 이진탐색트리- 노드들이 연결된 자료구조. - root(T)가 T의 루트노드를 가리킨다. // p[root[T]]=NIL- null도, 노드가 1개여도 BST이다. - 각 노드가 포함하는 필드들: key, left(왼쪽 자식 노드의 포인터), right(오른쪽 자식 노드의 포인터), p(부모 노드의 포인터), satellite data(부속 데이터)- 루트 노드는 부모노드가 NIL인 유일한..