몽상실현개발주의

[알고리즘 기초] 09_SW 문제해결 응용_2 / Python 1. 완전 검색 & 그리디 1.1 반복과 재귀 반복(Iteration)과 재귀(Recursion) 반복과 재귀는 유사한 작업을 수행할 수 있다. 반복은 수행하는 작업이 완료 될때까지 계속 반복 루프(for, while 구조) 재귀는 주어는 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 하나의 방법 하나의 큰 문제를 해결할 수 잇는 (해결하기 쉬운) 더 작은 문제로 쪼개고 그 결과들을 결합한다. 재귀 함수로 구현 반복 구조 초기화 반복되는 명령문을 실행하기 전에 조건 검사에 사용할 변수의 초기값 설정 조건검사 반복할 명령문 실행 업데이트 무한루프가 되지 않게 조건이 거짓이 되게 한다 재귀적 알고리즘 재귀적 정의는 두 부분으로..

[알고리즘 기초] 08_SW 문제해결 응용_1 / Python 1. SW 문제 해결 문제 해결 역량 프로그램을 하기 위한 많은 제약조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력 프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력 추상적인 기술 훈련이 필요하다 문제 해결 과정 문제를 읽고 이해한다. 문제를 익숙한 용어로 재정의 한다. 어떻게 해결할지 계획을 세운다. 계획을 검증한다. 프로그램으로 구현한다. 어떻게 풀었는지 돌아보고, 개선할 방법을 찾는다. 문제 해결 전략 직관과 체계적인 접근 2. 복잡도 분석 알고리즘 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터용어로 쓰이며, 컴퓨터..

[알고리즘 기초] 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. 스택의 구현 - 스택을 프로그램에서 구현하기 위해 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저..

[알고리즘 기초] 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]..