일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- NumPy
- 코틀린 시작하기
- 재귀함수
- 빅세타
- trivial solution
- nontrivial solution
- matrix fo a linear transformation
- matrix-vector product
- Big-O 예제
- 이진 탐색
- 코틀린 Hello World!
- 일차변환
- Big-Oh 예제
- itertools
- 빅오 표기법
- homogeneous linear system
- nonhomogeneous linear system
- 알고리즘 분석의 실례
- linear dependence
- solutions of matrix equation
- Big Theta
- Big-Oh notation
- python
- 빅오메가
- one-to-one
- Big Omega
- 배열 섞기
- 랜덤 순서 배열
- recursive algorithms
- matrix trnasformations
- Today
- Total
목록분류 전체보기 (152)
코딩 연습
파이썬의 내장함수 all 은 다음과 같다. def all(iterable): for element in iterable: if not element: return False return True 함수 all 은 매개변수로 iterable (리스트, 튜플, 딕셔너리 등등) 를 갖는다. 함수 all 은 iterable 내의 모든 요소가 참이거나 혹은 iterable 이 비어 있다면 True 를 반환하고, 그 외의 경우에는 False 를 반환하는 함수이다. 즉, iterable 내의 요소 중 단 하나라도 거짓인 경우에는 False 를 반환한다. 파이썬에서는 0을 False 로 1은 True 로 인식한다. 다음의 예제를 보면 쉽게 이해할 수 있다. >>> all([]) True >>> all([1, 2, 3, ..
functools 모듈의 reduce 함수는 다음과 같다. def reduce(function, iterable, initializer=None): it = iter(iterable) if initializer is None: value = next(it) else: value = initializer for element in it: value = function(value, element) return value reduce 함수는 매개 변수로 function, iterable[, initializer] 를 갖는다. function 과 iterable 은 반드시 전달되어야 하고, initializer 는 선택적이라고 보면 된다. 위 코드를 보면 알겠지만 reduce 함수는 다음과 같이 iterable..
enumerate 함수는 다음과 같다. def enumerate(sequence, start=0): n = start for elem in sequence: yield n, elem n += 1 enumerate 함수는 두 개의 매개변수 sequence, start 를 갖는다. 쉽게 말해서 enumerate 함수는 sequence 의 각각의 요소에 index 를 붙인 튜플을 생성하는 반복자를 리턴하는 함수라고 생각하면 된다. 내가 써 놓고도 무슨 말인지 하나도 모르겠다. 다음의 예제를 보면 한방에 이해가 간다는 것을 믿어 의심치 않는다. >>> seasons = ['Spring', 'Summer', 'Fall', 'Winter'] >>> list(enumerate(seasons)) [(0, 'Spring..
파이썬의 itertools 모듈에는 다음과 같은 takewhile 함수가 있다. def takewhile(predicate, iterable): for x in iterable: if predicate(x): yield x else: break 이 함수는 두 개의 매개변수 predicate 와 iterable 을 갖는다. predicate 는 True 나 False 를 리턴하는 함수라고 보면 되고, iterable 은 리스트, 튜플, 문자열과 같이 각각의 요소에 접근할 수 있는 자료형이라고 보면 된다. takewhile 함수는 iterable 의 각각의 요소에 순서대로 접근하여 prediacte 이 참이 될 때까지의 요소만으로 이루어진 반복자를 리턴하는 함수다. 다음의 예제를 보면 쉽게 이해할 수 있다...
파이썬의 itertools 모듈에는 다음과 같은 count 라는 함수가 있다. def count(start=0, step=1): # count(10) --> 10 11 12 13 14 ... # count(2.5, 0.5) -> 2.5 3.0 3.5 ... n = start while True: yield n n += step 위에서 보는 바와 같이 함수 count 는 두 개의 매개 변수 start 와 step 을 갖고, 이들의 기본값(default value)는 각각 0과 1로 설정되어 있다. 함수의 설명에서 알 수 있듯이 count 함수는 start 로부터 시작하여 step 만큼 떨어진 수들을 무한히 생성하는 무한 반복자를 리턴한다. 다음의 예제를 보면 쉽게 이해할 수 있다. >>> for i in ..
\(1, 2, 3, 4, 5\) 를 나열하는 순열의 수는 \(5!=120\) 가지로 금방 계산할 수 있지만, 실제로 \(120\) 를 나열하는 것은 사람이 하기 힘든 일이다. 컴퓨터로 하면 금방 될거라고 생각했는데, 생각만큼 쉽지는 않았다. 이런 저런 방법들을 생각해 보다가 결국 함수를 재귀적으로 사용하는 방법으로 결정을 했는데, 나열해야 하는 숫자가 많아질수록 시간이 좀 많이 걸리는 것 같다. 그래도 지금 수준에서 찾아낼 수있는 최선의 방법인거 같아 기록을 남긴다.새로운 방법을 배우고야 말았다. 그래서 두 가지 방법을 모두 소개하기로 한다. 1. 재귀함수를 이용하는 방법 기본적인 아이디어는 간단한다. 1 한 개를 나열하는 방법은 당연히 (1) 한 가지다. 1, 2 두 개를 나열하는 방법은 맨 앞자리가 ..
체스에서 여왕(queen) 은 가로, 세로, 대각선으로 움직이며 상대를 공격할 수 있다. N-queens 문제는 $N \times N$ 크기의 체스판에 $N$ 개의 여왕을 서로 서로 공격하지 못하도록 배치하는 법을 찾아내는 문제이다. 예를 들어, $N=4$ 일 때는 다음과 같이 $4$ 개의 여왕을 배치하면 된다. 즉, 어떤 두 개의 여왕도 같은 행, 같은 열, 같은 대각선 상에 놓이지 않도록 $N$ 개의 여왕을 배치하는 문제이다. 이 문제를 풀기 위해서는 위와 같은 배치를 표현하는 방법을 정의해야 한다. 이를 위해서 크기가 $N$ 인 배열을 만들고, 배열의 $i$ 번째 요소가 $i$ 번째 행에 놓이는 여왕의 열 위치를 나타내도록 표현하면 된다. 위의 해법을 이런 배열로 표현하면 (2, 0, 3, 1) 이..
달팽이 배열은 $n \times n$ 배열에 $1$부터 $n^2$ 까지의 자연수를 달팽이 집 모양으로 채우는 문제이다.다음 그림은 $4 \times 4$ 배열에서의 숫자를 채워 나가는 방향과 결과로 얻어지는 배열을 보여준다. 사용자로부터 배열의 크기를 결정하는 $n$ 을 입력받아 달팽이 배열을 만든 후 출력하는 프로그램을 작성하는 것이 이 문제의 목적이다. 계속 $4 \times 4$ 배열을 예로 들자면, 행과 열의 index 는 다음과 같이 주어질 것이고, 숫자들이 채워질 때는 규칙성이 있게 채워진다는 것을 알아야 한다. (0, 0) 에서 출발하여 오른쪽으로 숫자들을 4 개 채워간다. 오른쪽으로 채운다는 것은 열의 index 가 하나씩 증가하는 것을 의미한다. (0, 3) 에서 방향을 바꾸어 아래쪽으로..
베트남의 수도 하노이에 있는 불교 사원에 전해지는 이야기 중 다음과 같은 것이 있다고 한다. 다이아몬드로 이루어진 3개의 기둥 중 하나에 64개의 황금 원반이 끼워져 있다. 황금 원반은 크기가 모두 다르며, 아래쪽에서 위쪽으로 갈수록 크기가 작아져서 전체적으로는 원뿔형의 탑을 이루고 있다. 이 64개의 원반을 한 번에 하나씩 움직여 모두 다른 쪽 기둥으로 옮기려고 한다. 단, 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수는 없다. 이런식으로 원반들이 처음 있던 기둥에서 다른 기둥으로 모두 옮겨지면 세상이 끝난다는 전설이 있다. 하노이의 탑 문제는 유명하기 때문에 여기까지 검색해서 오신 분들이라면 다른 설명이 필요 없을 것이라고 생각된다. 이 문제는 재귀함수를 이용하여 간단하게 해결할 수 있다. (물..
유클리드 알고리즘 이 글을 이해하기 위해서는 유클리드 알고리즘을 먼저 이해해야 합니다. 다음 동영상을 참고하시기 바랍니다. 확장 유클리드 알고리즘 $x, y$ 에 대한 부정방정식 $ax+by=c$ 는 $c$ 의 값이 ${\rm gcd}(a, b)$ 의 배수일 때만 정수해를 갖는다고 알려져 있다. 즉, $ax+by=c$ 가 정수해를 갖는 $c$의 최솟값이 ${\rm gcd}(a, b)$ 가 되는 것이다. 따라서 확장 유클리드 알고리즘은 말 그대로 유클리드 알고리즘을 확장하여 $a, b$ 의 최대공약수 뿐만 아니라, $ax+by={\rm gcd}(a, b)$를 만족하는 정수해 $x, y$ 도 구하는 알고리즘이라고 생각하면 된다. $240$ 과 $46$ 의 최대공약수를 $c={\rm gcd}(240, 46)$..