프로그래밍[Univ] 343

[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 3. 합병정렬(Mergesort)

. N개의 숫자들을 정렬하는 방법 ⓐ 알고리즘(명백한 방법) - 최대값을 찾는다. - 남아 있는 숫자들을 회귀적으로 정렬한다. ⓑ 분석 - 요구되는 비교 횟수 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = ⊝(n^2) > 명백히 이 방법은 "균형취하기"발견법(Heuristic)을 이용하지 않는다. ⓓ 새로운 알고리즘 전략 : 합병정렬 - 배열을 반(Half)로 나눈다. - 두개의 부분들을 각각 정렬한다. - 정렬한 두 개의 부분들을 병합한다. ex) 27 10 12 20 25 13 15 22를 정렬하라. ⓔ 새로운 알고리즘 구현 //배열 a[i...j]를 정렬한다. void Mergesort(int i, int j){ int mid; if ( i > j ) { mid = flo..

[프로그래밍 언어론] 명령형 언어의 특징 2 - 변수(value)

명령형 언어의 특징이라는 주제를 달고 나온 부분은 자신이 프로그램언어를 개발시 고려해야할 상항에 대해서 나와 있는 것입니다. ----------------------------------------------------------------------------------------------------- * 변수란? - 메모리 공간에 대한 추상화 - 6개의 특징이 포함되어 있어야 한다. > name, address, value, type, lifetime, and scope - 선언된 변수는 symbol Table에 변수를 저장한다. ex) int a,b,c; //symbol Table에 저장 1. Name(이름) : "명명법은 명령형 언어의 특징 1"에서 이미 소개 되어 있기 때문에 건너띈다. 2. ..

[JavaScript] 자바스크립트

1. JavaScript란 - 인터프리터 방식의 Script언어 - HTML에 기능을 추가하기 위해서 사용 > HTML은 정적인 요소를 나타낸다면, JavaScript는 동적인 요소를 나타낸다. - 가격이 무료이며, 대부분의 브라우져에서 지원해준다 - ECMA에 의해 표준화가 되었다. 2. JavaScript적용하기 - HTML 내부에 삽입 : 여기서 주석이 들어가는 이유는 Javascript를 지원하지 않는 브라우져를 위해서 사용된다. - 외부 JavaScript 파일 사용 ex) 외부에 선언후 태그에 속성갑쳐럼 스크립트의 함수를 불러다 쓴다. 3. Java와의 비교 - 결론부터 말하면, 비슷하긴하지만 전혀 다른 언어이다. - 공통점 ⓐ 대/소문자 구분 ⓑ 문장은 ';' 에 의해 구분 ⓒ 기본적인 제어..

[프로그래밍 언어론] 명령형 언어의 특징 3 - Binding

명령형 언어의 특징이라는 주제를 달고 나온 부분은 자신이 프로그램언어를 개발시 고려해야할 상항에 대해서 나와 있는 것입니다. ----------------------------------------------------------------------------------------------------- * 바인딩이란? 변수나 예약어등 프로그래밍언어를 구성하고 있는 여러 것에 속성을 부여하는 것을 "바인딩한다"라고 한다. ex) int x; // 변수 x에 integer타입을 바인딩했다. x = 3;// 변수 x에 3이라는 값을 바인딩했다. * 바인딩이 일어나는 시간 1. 설계시 : 설계자에 의해서 기호(+, - 등)와 기호가 하는 일이 바인딩 된다.(ex> +는 더하는 역할을 한다) 2. 구현시 : ..

[HTML/CSS] 웹 개발

1. 웹 표준/웹 접근성 - W3C의 권장 표준 준수 - 논리적이고 의미에 맞는 HTML/CSS사용 - 내용과 디자인의 분리 - 브라우저간의 호환성 유지 - 웹 접근성 : 웹 접근간 장애제거(장애우, 노약자, 외국인의 접근편리 유도) - 웹 표준에 맞는가를 확인 하는 방법(Validation) > 통합검사기 : http://validator.w3.org/unicorn/ > HTML/XHTML : http://validator.w3.org/ > CSS : http://jigsaw.w3.org/css-validator/ > 브라우져의 Add-on ⓐ chrome : pendule ⓑ firefox : html Validator 2. 웹 개발 과정 - 요구 분석/조사 > 목표 및 요구 사항 분석 > 관련 사이..

[프로그래밍 언어론] 명령형 언어의 특징 1 - 명명법(identifier)

명령형 언어의 특징이라는 주제를 달고 나온 부분은 자신이 프로그램언어를 개발시 고려해야할 상항에 대해서 나와 있는 것입니다. ----------------------------------------------------------------------------------------------------- * 명명법(identifier) : 명명법을 표현하기 위해서는 다음 4가지를 고려 해야한다. 1. 길이 예전에는 컴퓨터의 메모리가 적었기에 이름의 길이를 제한하고 있었다. 예를들어 FORTRAN은 최대 6개로 이뤄져있고, 프로그램언어를 영어처럼 표현하기 위한 목적으로 만들어진 COBOL에서도 최대를 30으로 제한하고 있다. 현재에는 메모리가 풍부하여, 이름의 길이에 제한하지 않는 언어가 많이 있다. 변..

[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 2. 이진검색

1. 이진 검색(Binary Search) - 문제 : 크기가 n인 정렬된 배열 S에 키(key) x가 있는지를 탐색 ⓐ 명확한 방법 - 알고리즘 ① 키 x를 찾을 때까지 배열의 첫번째 요소부터 시작하여 x를 배열의 각 요소와 순서대로 비교한다. - 복잡도 분석 > 최악의 경우 n번을 비교해야 한다. - 관찰 > 이 방법은 "배열이 정렬되어 있다는 사실"을 이용하지 않고, "균형취하기"라는 발견법을 이용하지 않았다. ⓑ 효율적인 방법 - 알고리즘 ① 키 x를 배열의 중간요소와 비교한다. 같으면 찾았으니 끝낸다. 캍지 않으면, 배열을 중간요소를 기준으로 반을 나눈다. ② 키 x가 중간요소보다 작으면 왼쪽에 위치한 배열반쪽을 선택한다. 키 x가 중간요소보다 크다면 오른쪽에 위치한 배열의 반쪽을 선택한다. ③..

[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 1.일반론

1. 설계전략 ⓐ 분할(Divide) - 문제를 풀기 쉽도록 여러개의 작은 하위 문제들(Sub Problems)로 나눈다. ⓑ 정복(Conquer) - 더 작은 하위 문제들을 회귀적으로 푼다. ⓒ 통합(Merge) - 본 문제에 대한 답을 구하기 위해 하위 문제들의 답을 합친다. 2. 문제 : 배열의 최대 값과 최소 값 찾기 - 일반 해결법 ⓐ 배열의 값을 일일이 비교하며 최대값을 구한다. ⓑ 최대값을 제외한 모든 값을 비교하며 최소값을 구한다. > 효율 - 배열의 크기 : n - 비교 횟수 : n - 1 - 총 비교 횟수 : n-1(최대값 비교횟수) + n-2(최소값 비교횟수) = 2n - 3 - 분할 정복을 이용한 해결법 ⓐ 배열을 반으로 나눈다. ⓑ 양쪽 절반들의 최대값과 최소값을 구한다. ⓒ 배열..

[프로그래밍 언어론] 어휘 및 문법 분석 단계

1. 어휘 분석 단계(컴파일러 구성 중 제일 윗 단계) - 어휘를 문법적 의미가 있는 단위로 나눈다(lexeme과 token으로 나눠서 저장) ex) result = 10 * count + 1 2. 구문 분석(Parser를 이용한 Parsing 과정) - 파스 트리를 만들면서 구문을 분석하는 것으로 2가지 방법이 있다. > Top - down : start -> string // 대표 LL > Bottom-up : String -> start // 대표 LR - 토큰이 문법 순서에 맞게 들어오면 승인, 그렇지 않으면 오류를 발생해준다. - 대부분의 컴파일러는 Bottom-up방식을 따른다. ex) -> ac -> a|b 라는 문법을 가진 것에 aabc라는 사용자 입력이 있었다. 이것이 참인지를 보여라. ..

[알고리즘] 차수

1. 차수(Order) - 어떤 1차 시간(linear-time) 알고리즘이 어떤 2차 시간(quadratic-time) 알고리즘 보다 더 효율적이다. - 일반적으로 고차항이 시간 복잡도를 지배한다. ex) 주1 : 0.01n^2 >= 100n ( n >= 10,000) 주2 : n = 1,000,000 일때 0.01n^2과 0.01n^2+100n+10,000의 값은 거의 같다고 볼 수 있다. > 0.01n^2+100n+10,000에서 n^2의 항이 식을 지배함. 2. 큰(Big) O 표기법 - 정의 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 n>=N인 모든 정수 n에 대해서 g(n) 0)와 음이 아닌 정수 N이 존재하는 g(n)함수들의 집합이다. - g(n) ∈ O(f(n))이라면 우리는 g..