조환희의 학습 블로그

Untitled2 증가 기준(Order of Growth)¶ 여러줍니 두 알고리즘을 분석하고 그들의 실행시간을 입력의 크기에 대한 함수로 표현했다고 치자. 알고리즘 A는 $100n+1$번의 단계를 밟아 크기 n인 문제를 풀 수 있고, 알고리즘 B는 $n^2 + n + 1$ 번의 단계를 밟는다. 다음 표는 여러 가지 크기의 문제들에 대해, A와 B의 알고리즘의 실행시간을 보여준다. 입력의 크기 A 알고리즘의 실행시간 B 알고리즘의 실행시간 10 1001 111 100 10001 10101 1000 100001 1001001 10000 1000001 $> 10^1$$^0$ n=10일 때, 알고리즘 A는 별로 좋아 보이지 않는다. 알고리즘 B보다 무려 10배나 긴 시간이 든다. 하지만 n=100인 경우 두 알..

Untitled1 알고리즘 분석¶ 알고리즘 분석은 알고리즘의 성능을 연구하는 컴퓨터 과학의 한 분야로, 특히 실행시간과 필요공간에 대해 연구한다. 더 많은 정보를 보려면 http://en.wikipedia.org/wiki/Analysis_of_algorithms 를 참고하자. 알고리즘 분석의 실질적인 목표는 디자인을 결정하기 위해서 여러 가지 다른 알고리즘들의 성능을 예측하는 것이다. 2008년 미국의 대선 캠페인 기간에 구글을 방문했을 때 버락 오바마 후보는 즉흥적인 분석을 해보라는 요청을 받았다. 에릭 슈미트 최고경영자는 그에게 농담 삼아 '100만 개의 32비트 정수들을 정렬하는 가장 효율적인 방법은 무엇이냐'고 물었다. 분명히 오바마는 누구에게 귀띔을 받았을 것이다. 재빠르게 '버블 정렬 알고리즘..

문제 1아래에서 리스트의 인덱스 기능을 이용하여 5 를 출력하라. l = [[1,2], [3,4], [5,6]] 문제 2[0,1,4,9,16,25] 의 리스트를 for 와 range() 함수를 이용하여 구하라. 정답 Untitled14 In [1]: l = [[1,2], [3,4], [5,6]] l[2][0] Out[1]: 5 In [2]: s=[] for i in range(6): s.append(i**2) print(s) [0, 1, 4, 9, 16, 25]

랜덤 그래프, 연결 그래프, 폴 에어디쉬 랜덤 그래프¶ 랜덤 그래프는 문자 그대로의 뜻을 가지고 있다. 무작위로 생성된 연결선들이 있는 그래프인 것이다. 그래프를 생성할 수 있는 무작위 프로세스는 당연히 여러 가지 종류가 있으며, 그래서 랜덤 그래프의 종류도 여러 가지다. 그 중에서 흥미로운 것이 G(n,p)로 나타내는 에어디쉬-레니 모델이다. 해석하자면 두 개의 노드 사이에서 연결선이 존재할 확률이 p일 때, n개의 노드로 된 그래프를 생성하는 모델이다. 참고 : http://en.wikipedia.org/wiki/Erdos-Renyi_model 연결 그래프¶ 모든 노드에서 다른 모든 노드로 경로가 존재할 때 그 그래프는 연결되었다고 말한다. 참고 : http://en.wikipedia.org/wiki..

그래프 표현하기 그래프 표현하기¶ 그래프를 그릴 때는 일반적으로 노드를 동그라미나 사각형으로, 연결선을 선으로 그린다. 위 그래프에서 연결선들의 가중치는 미국 동북부 도시들 간의 대략적인 이동시간을 나타낸다. 이 경우, 노드의 배치는 도시들의 대략적인 지리적 위치를 반영하고 있지만, 일반적으로 그래프의 레이아웃은 임의로 배치된다. 그래프 알고리즘을 구현하기 위해서, 여러분은 그래프를 데이터 구조의 형식으로 나타내는 법을 알아야 한다. 그러나 가장 좋은 데이터 구조를 선택하기 위해서는 그래프가 어떤 작업들을 지원해야 하는지를 먼저 알아야 한다. 이 같은 닭이 먼저냐 달걀이 먼저냐 하는 문제에서, 여러 가지 그래프 알고리즘에 쓰기 좋은 그래프 구조를 먼저 보여주고자 한다. 이후에 이 구조로 다시 돌아와 장단..

그래프란 무엇인가?¶ 많은 사람들이 '그래프'라고 하면 데이터 세트의 표현, 즉 막대 차트나 심전도 같은 것을 연상한다. 이 장에서 다루는 그래프는 그런 것이 아니다. 이 장의 그래프는 이산의, 서로 연결된 원소들이 포함된 시스템을 모델링하기 위한 추상화라고 생각해야 한다. 여기서 원소들은 노드로 표현되고 상호 연결은 연결선으로 표현된다. 예를 들자면 도시 각각을 하나의 노드로, 도시들을 연결하는 도로를 연결선으로 표현해서 도로 지도를 그릴 수 있다. 또는 소셜 네트워크의 경우, 각 사람을 노드로 표현하고 사람들이 서로 '친구'인 경우 그들 사이에 연결선을 그리고, 그렇지 않은 경우 연결선으로 잇지 않는 식으로 표현이 가능하다. 어떤 그래프에서는 연결선들의 길이가 서로 다른데, 이것은 '가중치'나 '비용..

문제 1아래의 코드에서 문자열 s 를 ':' 으로 구분하여 리스트로 저장하라. s = ' abc:de:fghi:jkl\n' 문제 2아래의 코드에서 [5,6] 을 추가하는 두가지 방법을 적용하거나 설명하라. 정답 Untitled13 In [2]: s = ' abc:de:fghi:jkl\n' s.strip().split(':') Out[2]: ['abc', 'de', 'fghi', 'jkl'] In [3]: l = [[1,2], [3,4]] l+[[5,6]] Out[3]: [[1, 2], [3, 4], [5, 6]] In [4]: l = [[1,2], [3,4]] l.append([5,6]) l Out[4]: [[1, 2], [3, 4], [5, 6]]

Plot¶ R 언어에서 표현한 시각화 함수 Plot을 파이썬 언어로 고쳐보자. R 시각화 함수 Plot 출처 https://unfinished-god.com/2019/03/01/r-plot%EC%97%90-%EB%8C%80%ED%95%9C-%EC%9D%B4%EB%AA%A8%EC%A0%80%EB%AA%A8/ Step0. Plot을 구성하기 위한 Data 만들기¶ In [2]: import numpy as np from sklearn.datasets import load_iris iris = load_iris() In [3]: dir(iris) Out[3]: ['DESCR', 'data', 'feature_names', 'filename', '..