자료구조수업에서 시에르핀스키 삼각형에 대한 과제가 있어서 한번 코딩을 해보았습니다. 시에르핀스키 삼각형(Sierpinski triangle)은 프랙탈 도형입니다. 시에르핀스키 삼각형은 다음과 같은 방법을 통해 얻을 수 있다. 정삼각형 하나에서 시작한다. 정삼각형의 세 변의 중점을 이으면 원래의 정삼각형 안에 작은 정삼각형이 만들어진다. 이 작은 정삼각형을 제거한다. 남은 정삼각형들에 대해서도 2.를 실행한다. 3.을 무한히 반복한다. 이것을 반복하면 다음과 같은 도형이 얻어진다.(무한반복) 아래는 Sierpinski Triangles recursively arrow에대한 코드입니다. Sierpinski Triangles을 recursively하게 tuple을 사용해서 그려보겠습니다. 1 2 3 4 5 6..

하노이탑에 대한 Python 코드입니다. 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다. peg1에 있는 디스크를 peg3에 모두 옮기려면 어떻게 해야할까요?? 1. peg3에 6번 디스크가 가기위해서는 peg2에 1~5번 디스크가 있어야합니다. 2. 마찬가지로 peg2에 5번 디스크가 있기 위해서는 peg3에 1~4번 ..

단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조 동적 메모리 할당을 받아 노드(node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킴 연결리스트에서는 삽입/삭제 시 항목들의 이동이 필요 없음 연결리스트에서는 자료를 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색 (Sequential Search)을 해야함 단순연결리스트에서 head는 맨 처음 노드라고 생각하면 됩니다. head를 통해서 노드로 순차적으로 탐색 그럼 코드를 통해 확인해볼게요 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

List 자료구조에 대한 내용입니다. 자료구조로서의 리스트는 자료들의 덩어리입니다. 그리고 자료들 사이에 순서가 존재합니다 이러한 순서에 접근하기 위해서 인덱싱을 사용합니다. 리스트연산 1.삽입 append()를 사용해서 리스트에 값을 추가할 수 있습니다. 2.삭제 pop()을 사용해서 삭제가 가능합니다. 시간복잡도 삽입, 삭제 시에는 O(n)의 시간복잡도를 가집니다. 그렇다면 어떻게 시간복잡도를 줄여서 성능을 올릴 수 있을까요? c언어에서는 충분한 배열의 크기를 선언해서 사용합니다. 반면 파이썬은 삽입,삭제하면서 리스트의 메모리공간이 변합니다. 그렇다면 어떻게 메모리를 변화시킬까요? 1. 삽입할때마다 메모리를 일정한 크기씩 확장하는 방법 메모리가 부족할때마다 2씩 메모리를 확장. k = n/c T(n)..

알고리즘의 성능을 나타낼때 정확성, 복잡도, 효율성이 대상이 됩니다. 알고리즘의 복잡도란 알고리즘의 성능을 나타내는 지표입니다. 알고리즘의 수행시간 -> 시간 복잡도 (time complexity) 알고리즘의 사용공간 ->공간 복잡도 (space complexity) 주로 시간복잡도로 알고리즘의 성능을 평가합니다. 시간 복잡도 측정 방법 1.Big-Oh O(n)은 수행시간 함수 입니다. f(n) = 2n^2 + 3n + 5이면, 양의 상수 c 값을 최고 차항의 계수인 2보다 큰 4를 택하고 g(n) = n^2으로 정하면, 3보다 큰 모든n에 대해 2n^2 + 3n + 5 < 4n^2이 성립, 즉, f(n) = O(n^2) f(n)의 수행시간은 O(n^2)라는 것입니다. 흔히 수행시간에서 계수는 생략가능합..

분수에 관한 기본연산과 비교연산에 대한 코드입니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354def gcd(m, n): #최대공약수를 구하는 함수입니다. while n: m, n = n, m % n return m class Fraction: #Fraction class를 만들어줍니다. def __init__(self, num, denom): #constructor입니다 self._num = num #num은 분자값 self._denom = denom #denom은 분모값 입니다. def __repr__(self): #string으로 출력하기위한 함수 return str..

오늘은 파이썬의 기초에 대해 공부하겠습니다. 파이썬은 high-level, objected-oriented 프로그래밍 언어입니다. 1.배우기 쉽다. 2. 무료이고 오픈소스 입니다. 3. Portable, extensible, embeddable한 특징이 있습니다. 4. 많은 표준 라이브러리를 제공합니다. 5. Interpreted 언어입니다. 6. 객체지향언어입니다. ex1) 7. 보시다시피 변수의 타입을 선언할 필요가 없습니다. 8. c언어처럼 세미클론(;)을 뒤에 삽입하지 않아도 됩니다. 9. print문을 통해 쉽게 문장을 출력가능합니다. ex 2) 10. for문 사용 ex 3) range(1,11) 1~10까지의 수입니다. for i range(1,11): 에서 i에 1~10까지 매칭됩니다. 그..