실제 그래프(real graph)와 랜덤 그래프(random graph)

1. 실제 그래프(real graph) 실제 그래프(real graph)는 실제 존재하는 complex system으로부터 데이터를 얻어 표현한 그래프 MSN은 옛날에 microsoft에서 서비스하던건데 지금은 안한다고 한다 실제 그래프는 어떻게 이해해야할까? 잘 이해하기위한 비교대상이 필요하다. 그것이 바로 random graph 2. 랜덤 그래프(random graph) In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random pro..

• format_list_bulleted Graph
• · 2022. 2. 3.
• textsms

union find 알고리즘

서로소 집합 알고리즘(disjoint set) 그래프 내에서 여러개의 node가 존재할 때 2개의 node를 선택해서 이 node가 서로 같은 node에 속하는지 판별하는 알고리즘 예를 들어 다음과 같이 8개의 node가 존재한다면 이런 경우는 부모 node가 자기 자신인 경우이다 이제 1과 2가 연결되었다고 생각해보자 이런 경우 2의 부모 node는 1이 된다 이렇게 합쳐나가는 과정을 union알고리즘이라고 부른다 이번엔 2와 3도 연결되었다고 가정해본다면 그러면 3의 부모 node는 2가 되는데 3과 1이 연결되었다는 것은 어떻게 아는가? 3의 부모 node는 2이고 2의 부모 node는 1이라서 부모 node만 보고서는 판단할 수가 없다 그렇지만 재귀함수를 사용하면 3의 부모 node가 2를 가리키..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 2. 2.
• textsms

파이썬(python)의 defaultdict, ordereddict, namedtuple

1. defaultdict 사전에서 value의 기본값을 지정하여 새로 key를 생성할 때 value를 지정하지 않으면 기본값이 자동으로 들어간다 from collections import defaultdict로 사용할 수 있음 단어 빈도수 계산에 유용함 defaultdict를 쓰지 않으면 d[word]하는 순간 에러가 나는데 try~except~로 처리해야하는 번거로움이 있다 하지만 defaultdict로 기본값을 미리 지정해주면 d[word]해도 에러가 안난다 2. Ordereddict 데이터 입력한 순서대로 출력해주는 dictionary 요즘엔 기본 dictionary도 입력한 순서대로 출력해주므로 큰 의미없다 3. namedtuple 튜플 형태로 데이터 구조체(자료 구조, 이름 등)를 저장하는 자..

• format_list_bulleted Python
• · 2022. 2. 1.
• textsms

코딩테스트에서 유용한 list의 split과 join

str.split([기준값])은 [기준값]을 기준으로 str을 분리하여 리스트로 만들고 list(str)은 str 1글자씩 원소로 갖는 리스트로 만들어 반환 string = 'daehyuck' string.split() ['daehyuck'] string2 = 'daehyuck yun' string2.split() ['daehyuck','yun'] list(string) ['d','a','e','h','y','u','c','k'] ‘(기준값)’.join(list)는 리스트를 받아서 기준값으로 리스트 원소를 이어 문자열을 반환함 입력된 글자를 역순으로 출력하는 프로그램 word = input('input a word:') word_list = list(word) reverse_list = [] for i ..

• format_list_bulleted Python
• · 2022. 2. 1.
• textsms

힙큐(heapq) 활용하기 기본

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수=가장 맵지 않은 음식의 스코빌 지수+(두 번째로 맵지 않은 음식의 스코빌..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 2. 1.
• textsms

convolution 연산 이해하기 기본편

1. Fully connected 연산 기존의 MLP는 가중치 행렬에서 각 행마다 다른 가중치 행들이 각각 Hidden vector에 연결되는 구조다. 이게 단점은 parameter가 많아서 계산량이 많아진다. 2. Convolution 연산 고정된 가중치 행렬 kernel을 입력벡터상에 움직여가면서 모든 hidden vector에 연결시키는 전략은 어떨까? parameter 수가 엄청나게 줄어들어 계산이 쉬워진다. 심지어 행렬곱이니까 여전히 선형변환이다. 3. Convolution 함수 공식은 다음과 같다. 참고로 convolution은 변수변환을 시켜서 교환법칙이 성립한다는 것을 보일 수 있다. 커널을 이용해 신호를 국소적으로 증폭 또는 감소시켜 정보를 변환하거나 추출하는 방식으로 signal pro..

• format_list_bulleted 딥러닝 기초
• · 2022. 2. 1.
• textsms