파이팅웨이

greedy 알고리즘 일곱 번째 문제 7.Huffman Code -텍스트를 압축할때, 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 것이다. -이 때 문자를 표현하기 위해 트리를 이용한다. -방법 1. min-priority queue를 사용하는 방법 1.각 문자 당 노드를 만들고, 그 문자의 빈도수를 노드에 저장 2.n개의 노드의 빈도수에 대해 우선순위 큐 Q를 만든다. while(Q에 있는 노드 수 >=2){ 빈도수가 가장 작은 2개의 노드 (A와 B)를 Q에서 제거. 새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다. N의 빈도수 = A의 빈도수 +B의 빈도수 노드N을 Q에 삽입한다.} return Q -Time Complexi..

3.서비스 전략 3.1.서비스 전략의 의의 주어진 환경에서 기업의 목표를 달성할 수 있도록 각종 프로그램들이 서로 일관성 있게 수행되도록 하는 행위 -의사결정 일관성 전략의 구성요소 1.차별적 능력 2.서비스 목표 3.서비스 정책 전략의 중요성 1.역량 집결 : 무엇을 기대할 수 있나? 2.합리적 통제 3.동기유발 4.효율성 제고 3.2.기업전략 기업비전 1.비전설정 2.외부환경분석, 내부환경분석(SWOT) 3.실행전략 수립 3.3.경쟁우위전략 원가우위전략 : 대량생산, 규모의 경제, 시장점유율, 공격적 가격정책, 최신장비, 초기손실감수, 효율성 극대화, 불필요한 활동 제거, 고객접촉지점 최소화, 재량권 낮음, 동일한 업무 반복수행, 자동화, 간접접촉, 셀프서비스, 고객접촉지점 입지, 지원지점 입지, 외..

-방법 1)배열의 원소 하나를 피봇(pivot)삼고 기준 2)피봇보다 작은 숫자들은 왼쪽, 피봇보다 큰 숫자들은 오른쪽에 위치하도록 분할 3)분할된 부분문제에 대해서도 위와 동일한 과정을 재귀적으로 수행하여 정렬 +이 때, 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않는다. -Pseudo Code QuickSort(A, left, right) 입력: 배열 A[left]~A[right] 출력: 정렬된 배열 A[left]~A[right] 1. if (left < right) {//배열 A의 가장 왼쪽 원소의 인덱스가 가장 오른쪽 원소의 인덱스보다 작으면, 정렬 수행. 그렇지 않으면 1개의 원소를 정렬하는 경우임. 2. 피봇을 A[left]~A[right] 중에서 선택하고, 피봇을 A[left]와 자리를 ..

회로 구현의 효율성을 위해 부울함수의 간략화가 필요한데, 부울 대수의 규칙과 법칙만을 이용해선 완전한 최소화가 용이하지 않다. 따라서 카노프 맵을 이용하여 간략화 하는 방법을 알아야 한다. * 카노프 맵이란? -입력변수들에 대한 조합 수 만큼의 셀들로 구성된 2차원 배열 - 인접해 있는 1들을(0들을) 2^n개 단위의 그룹으로 묶고, 정해진 규칙에 따라 변수를 제거 - 3 - 변수, 4-변수 및 5-변수 부울 함수들에 대하여 적용가능 - 그 이상의 변수 함수들에 대해선 방법은 있으나 프로그래밍으로 대부분 해결 (1) 3- 변수 sop형 부울 함수에 대한 카노프맵 3-변수 카노프 맵이란 2^3개(8개)의 셀들로 이루어진 2차원 배열이다.(변수가 만들 수있는 최소항의 수와 같다) 각 셀에는 대응되는 2진수들..

XOR 연산 하나라도 다른 값이 생기면 1 Exclusive-OR 같으면 0 다르면 1 -결합 법칙 증명 방법 : 입력 변수의 1의 개수가 홀수 함수이면, 출력은 무조건 1 -분배 법칙 증명 방법 : 역방향의 함수가 되도록 유도해 본다. XNOR 연산 등가 연산 같으면 1 다르면 0 -입력 변수의 1의 개수가 짝수일 때 F=1 =>XNOR 함수는 짝수 함수(even function)임을 뜻한다.

NAND 게이트: 기본 게이트 혹은 범용 게이트 라고도 부름 부울 함수를 SOP 형으로 변환 후, NAND 함수로 변형하면 부울 함수를 NAND 게이트만으로 구현할 수 있다. NAND 게이트 구현의 이점 (1)기본 게이트인 NAND 게이트들을 이용하므로, 동작 시간이 더 빨라진다. (2)7400칩에는 네 개의 NAND 게이트들이 포함되어 있으므로, AND-OR 회로 구현에 필요한 칩의 수를 줄일 수 있다. NOR 게이트 :NAND 게이트와 쌍대 관계 부울 함수를 POS형으로 변환한 후, NOR 함수로 변형 혹은 두 개의 인버터를 연속으로 추가해주면 부울 함수를 NOR게이트만으로 구현할 수 있다. 직접 그려보기

표준형 함수 : 부울 곱으로 이루어진 항들의 합, 혹은 부울 합으로 이루어진 항들의 곱으로 표현된 함수 ex) 일반형 F(A,B,C)=A(B+C)+BC ->형태가 규칙적이지 않다. 표준형 F(A,B,C)=AB+AC+BC ->곱으로 이루어진 항들의 합으로 구성되어있다. ->이는 처리 시간을 단축시켜주고, 회로 구성을 단순화시킨다. 4.5.1.SOP 표현(Sum Of Products representation) 부울 곱으로 이루어진 두개 이상의 항들이 부울 덧셈에 의해 합해진 형태의 부울 함수. 쉽게 곱셈들의 덧셈 -항들 중의 하나 이상이 1이면, 출력은 무조건 1이다. -AND-OR 회로에 의해 구현된다. -분배 법칙을 이용하면 표준형으로 표현되지 않은 부울 함수를 SOP형으로 변형시킬 수 있다. 정규형 ..

설계 절차 1. 설계할 회로의 기능을 나타내는 진리표를 작성한다. 2.진리표로부터 부울 함수를 유도한다. 3.부울 함수를 간략화 한다. 4.논리 게이트들을 이용하여 회로를 구성한다. 4.4.1최소항과 최대항 진리표로부터 부울 함수를 유도할 땐 최소항(minterm) 또는 최대항(maxterm) 방법을 이용한다. (1)최소항 구하는 방법 ((1))입력값이 1인 변수는 정상형으로 표현한다. ((2))입력값이 0인 변수는 보수형으로 표현한다. ((3))변수들을 곱의 형태로 표현한다. ->표준 곱이라고도 부른다. ->각 항은 입력변수들간의 AND 연산 결과가 '1'이 되도록 표현한 결과에 해당한다. 각 항의 AND 연산결과가 1이 되도록 만드는 것이 목표이므로, 항은 항상 1개이다. (2)최대항 구하는 방법 (..

부울 함수의 주요 용도 디지털 시스템(논리회로)의 동작 특성 분석 디지털 시스템(논리회로)의 설계 논리회로의 설계 과정에서 부울 함수를 간략화 시킬 때 법칙들과 규칙들을 사용할 수 있다.-> 회로 구현에 필요한 부품의 수 감소, 크기 최소화 및 처리 속도 향상 효과 법칙들 교환 법칙 결합 법칙 분배 법칙 +팩터링(공통 변수로 묶는 것) 규칙들 A*0=0 A*1=A A*A=A A*A'=0 A+0=A A+1=1 A+A=A A+A'=1 A''=A A+AB=A ※외우기 A+AB'=A+B ※외우기 +쌍대성의 원리 드모르간 정리

2.1 이진수 표현 비트 2진 숫자의 약어 디지털 시스템에서 수 혹은 문자와 같은 정보를 표현하는 기본 단위 변환 연습 10진수->2진수 : 반복 2분법 2진수->10진수 소수점 이하의 10진수 2진수로 변환->오차발생 소수점 포함 2진수를 10진수로 변환 정수와 소수가 합해진 10진수의 2진수 변환. 단어 : 디지털시스템에서 데이터의 입력, 처리, 저장 및 출력을 수행하는 기본 단위. 2.2 8진수 및 16진수 표현 변환 연습 10진수->8진수 : 반복 8분법 2진수 8진수 : 세 비트씩 분할 2진수 16진수 : 네 비트씩 분할 2.3 2진 산술연산 연산 연습 2진 덧셈 : 합과 올림수 2진 뺄셈 : 차이와 빌림수 2진 곱셈 2진 나눗셈 2.4 음수 표현 MSB를 부호 비트로 사용하라 부호화 크기 표현..