파이팅웨이

Dynamic Programming(동적 알고리즘)이란? 최적화 문제를 해결하는 알고리즘 1.입력 크기가 작은 '부분 문제'들을 모두 해결 2.그 해들을 이용하여 보다 '큰 크기의 부분 문제'들을 해결 3.최종적으로 원래 주어진 입력의 문제를 해결. Divide&Conquer(분할 정복 알고리즘) 방식과 구조적으로 유사하지만, 순서는 반대이다. 거기에 더해, 동적 계획 알고리즘은 B와 C의 해를 구하는 데 E와 F의 해 모두를 이용한다. 분할 정복 알고리즘의 경우, D,E,F,G는 각각 더 이상 분할할 수 없는 부분 문제들이다. D와 E의 해를 취합하여 B의 해를 구하고, F와 G의 해를 취합하여 C의 해를 구하고, B와 C의 해를 취합하여 A를 구한다... 동적 계획 알고리즘의 경우, 먼저 최소 단위의..

제 1장 빠르게 변화하는 비즈니스 환경에서의 리스크에 대한 대응과 수익창출 비즈니스와 부의 창출 부의 창출에서 기업가의 중요성 기업과 환경 미국 기업의 변화과정 [부의 창출에 기업가가 미치는 중요성] -생산의 5가지 요소 1.토지 2.노동 3.자본 4.기업가정신 5.지식 특히 자본이 압도적으로 중요하다. 제 2장 경제학 이해하기 경제시스템이 기업에 영향을 미치는 방법 자유시장 자본주의 이해 사회주의 이해 공산주의 이해 혼합경제로의 추세 [경제학 이해하기] -아담 스미스와 부의 창출 경제에 가장 중요한 요소는 자유이다. 토지 및 부동산을 소유할 수 있는 자유와, 기업 이익을 소유할 수 있는 권리는 필수적인 것이다. 노력에 대한 댓가가 확실히 보장될 때 사람들은 열심히 일할 것이다. -아담 스미스의 국부론 ..

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..

-방법 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 ※외우기 +쌍대성의 원리 드모르간 정리