몽상실현개발주의

[알고리즘 기초] 07_Tree / Python Tree 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 트리의 정의 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다 노드 중 최상위 노드를 root 라 한다. 나머지 노드들은 n(>=0) 개의 분리 집합 T1, ..., TN 으로 분리될 수 있다. 이들 T1, ..., TN 은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리 (subtree)라 한다. 트리의 용어 노드(node) - 트리의 원소 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) - 트..

[알고리즘 기초] 06_Queue / Python Queue Queue 의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조 (FIFO : First In First Out) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제 된다. 큐의 기본 연산 삽입 : enQueue() ( Queue의 Rear 동작 ) 삭제 : deQueue() ( Queue의 Front 동작) 생성 : createQueue() 공백 확인 : isEmpty() 포화 확인 : isFull() 삭제 없이 원소 반환 : Qpeek() 1. 선형 큐 1차원 배열을 이용한 큐 큐의 크기 = 배열의 크기 front : 저장..

[알고리즘 기초] 05_Stack 2 / Python 1. 계산기 문자열로 된 계산식이 주어질 때, 스택이 이용하여 이 계산식의 값을 계산할 수 있다. 문자열 수식 계산의 일반적 방법 step1. 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용) step2. 후위 표기법의 수식을 스택을 이용하여 계산한다. 1.1 중위표기식의 후위표기식 변환 방법. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다. 괄호를 제거한다. 1. ( ( A * B ) - ( C / D )) 2. ( ( A B ) * ( C D ) / ) - 3. AB * CD / - 1.2 중위표기식의 후위표기식 변환 방..

[알고리즘 기초] 04_Stack 1 / Python 1. Stack(스택) 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 이다. 스택에 저장된 자료는 선형 구조를 갖는다. 선형구조 : 자료 간의 관계가 1대 1의 관계를 갖는다. 비선형구조 : 자료 간의 관계가 1대 N의 관계를 갖는다. (ex. 트리 구조) 트리구조: 트리구조는 가지치기형으로 생긴 구조이다. 부모자식 관계로 형성. 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다. 마지막에 삽입한 자료를 가장 먼저 꺼낸다. LIFO(후입선출) 이라고 부른다. ex) 1, 2, 3 순으로 삽입 -> 3, 2, 1 순으로 꺼낼 수 있음 2. 스택의 구현 - 스택을 프로그램에서 구현하기 위해 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저..

[자료구조] 그래프 Graph 그래프 Graph 정점 (vertex / node) , 간선 (edge / link) 로 이루어진 자료구조 정점과 간선은 집합이기 때문에 중복된 값을 가지지 않는다. 그래프는 꼭 연결되어 있을 필요도 없고, 간선이 반드시 서로 다른 두 정점을 연결해야 할 필요도 없다. 비선형 자료구조이다. 즉, 선형 자료구조와 다르게 하나의 원소 다음에 여러개의 원소가 올 수 있다. (1:M , 0 외부에서 오는 간선 수 진출 차수(out-degree) : 해당 정점을 시작으로 하는 간선의 수 (=외차수) => 외부로 나가는 간선 수 루프(loop) : 간선 하나에 동일 노드가 연결(부속)되어 있는 경우 경로(path) : 간선을 따라 갈 수 있는 길. 정점의 나열로 표시 ex) , , ...

[알고리즘 기초] 03_문자열(string) / Python 1. 문자의 표현 - 컴퓨터에서의 문자의 표현 1) 코드체계 각 문자에 대해서 대응되는 숫자를 정해 놓고 이것을 메모리에 저장하는 방법을 사용 영어의 경우 대소문자 합쳐서 52자 이므로 6비트(64 가지)면 모두 표현 할 수 있다. 이를 코드체계라고 한다. 000000 -> 'a' 000001 -> 'b' 네트워크가 발전하면서 서로간의 정보를 주고 받을 때 정보를 다르게 해석한다는 문제가 발생 지역별 코드 체계가 다르기 때문 2) ASCII Code 표준안을 목적으로 1967년, 미국에서 ASCII(American Standard Code for Information Interchange)라는 문자 인코딩 표준이 제정됨. ASCII는 7bit ..

[알고리즘 기초] 02_배열 2 (Array 2) / Python 1. 배열 : 2차 배열 1.1 2차원 배열의 선언 1차원 List를 묶어놓은 List 2차원 이상의 다차원 List는 차원에 따라 index를 선언 2차원 List의 선언: 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함 Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함 arr = [[0, 1, 2, 3], [4, 5, 6, 7]] 1.2 2차원 배열의 접근 배열 순회 n X m 배열의 (n * m) 개의 모든 원소를 빠짐없이 조사하는 방법 행 우선 순회 # i 행의 좌표 # j 열의 좌표 for i in range(len(Array)): for j int range(len(Arrary[i])): Array[i]..

[알고리즘 기초] 01_배열 1 (Array 1) / Python 1. 배열 프로그램 내에서 여러개의 변수가 필요할때 사용. 하나의 선언으로 둘 이상의 변수를 선언 할 수 있다. - 완전탐색 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-force 혹은 generate-and-test 기법이라고도 불리 운다. 모든 경우의 수를 테스트 한 후, 최종 해법을 도출한다. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다. 수행속도가 느리지만 해답을 찾지 못할 확률이 적다. - 순열 (Permutation) 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것 nPr nPr = n * (n-1) * (n-2) * ... * (n-r+1) nPn = n * (n-1..