파이팅웨이

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를 부호 비트로 사용하라 부호화 크기 표현..

1.1아날로그 신호 아날로그 신호 : 연속적으로 변하는 값들의 집합 시간축, 크기 ->무수한 실수값이다 ex)온도 변화, 속도, 음성 신호 디지털 신호 : 연속적인 신호를 일정 시간 간격으로 샘플링한 값들 혹은 특정 시간 동안에 관측된 값들의 집합 시간축, 크기 ->불연속적인 값이다. ex)샘플링 된 자동차 속도, 시간대별 고객 수, 매 시간마다 측정된 체온, 샘플링 값이란 이산적 값 혹은 디지털 데이터. 보통 샘플링된 각 값을 10진수, 8진수, 혹은 2진수로 표현한다. 1.2아날로그 시스템과 디지털 시스템 아날로그 시스템 : 아날로그 신호를 받아서 처리하는 부품들로 구성된 장치. 아날로그 신호 입력, 아날로그 신호 출력 ex) 일반전화 시스템, 카세트 테이프 레코더, 앰프 등 디지털 시스템 : 디지털..

제 1장 서비스와 경제 1.1일상생활과 서비스 서비스 의미 부정적에서 긍정적~ 서비스 산업 비중 높아지는 중 수퍼볼->스포츠 산업 파급효과. 15조원 돈잔치 서비스 사회, 서비스 경제에 따라 새로운 인식 필요 : 서비스의 정의 과정과 상호작용, 그 속의 편익도 중요 1.2.경제의 진화 경제의 구성 추출, 제조, 서비스 서비스가 우리 삶에 끼친 영향 ->전기산업사회(산업혁명 전), 후기산업사회(산업혁명 후) 비교 전기산업사회: 자급자족, 육체 사용, 생산성 낮음, 농경사회, 자연과의 게임 산업사회: 적은 비용으로 많은 제품의 생산. 개인화. 개인은 기계의 부품. 비인간적 효율적 생산, 단순화, 표준화, 분업화, 전문화, 기계화. 대량생산, 대량판매 ->계층적 조직 탄생(최고경영자-부서-최고관리자) 노조 탄..

greedy 알고리즘의 여섯 번째 문제 6. 작업 스케줄링(Job Scheduling) -작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제. -machine의 수가 무제한이지만 최소로 쓰게 풀어라. -Input : 작업의 수 n개, 각 작업의 시작 시간과 종료시간(길이) -각자 시작 시간과 마치는 시간이 다른 강의자들을 어떻게 강의실에 배치시킬 것인가? ex) Task=(t1=[7,8],t2=[3,7],t3=[1,5],t4=[5,9],t5=[0,2],t7=[1,6]) 단, [s,f]에서 s는 작업의 시작 시간, f는 작업의 종료 시간 -방법 1.시작 시간의 오름차순으로 정렬한다. L={[0,2],[1,6],[1,5],[3,7],[5,9],[6,8],[7,8]} 2.가장..

Greedy 알고리즘의 네 번째 문제 4.부분 배낭 문제 -n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있다. 배낭을 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 물건을 넣어라. -배낭 문제의 종류 (1) 0-1 배낭 문제. 물건을 통째로 넣어야 한다. 이는 greedy알고리즘으로는 풀 수 없다. (2) 부분 배낭 문제. 물건을 부분적으로 잘라서 담는 것을 허용한다. greedy 알고리즘으로 해결 가능하다. -방법 단위 무게 당 가장 비싼 물건을 배낭에 넣고, 그 다음으로 값 나가는 물건을 넣음. 그러다 값나가는 물건을 통째로 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 부분적으로 나눠 배낭에 넣음 -Pseudo Code Input : n개의 물건, 각 물..

Greedy 알고리즘의 세 번째 문제 3.최단 경로 찾기 문제 -주어진 가중치 그래프에서 '어느 한 출발점'에서 '또 다른 도착점'까지의 최단 경로를 찾는 문제 -weight값이 양수일 때! -대표적인 알고리즘 다익스트라(Dijkstra)최단 경로 알고리즘 주어진 출발점에서 시작하여 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 앞선 최소 신장 트리와 비교했을때, 무조건 weight가 적은 노드를 찾는 MST와는 달리 특정 경로를 향해 거쳐갈 수 있는 경로 중에서 가장 weight가 적은 것을 선택해야 한다. 여기서 Greedy 개념에 Dynamic programing 성격을 가진다. 서울에서 대구로 가는 최소 경로를 찾을 때, 출발점 기준 ..

Greedy 알고리즘 문제 중 하나인 최소 신장 트리 구하는 문제의 두 번째 풀이 -Prim algorithm 랜덤으로 노드를 하나 고르고 고른 노드와 연결되는 edge 중 weight가 적은 것을 고르고, 이어진 노드에서 이 과정을 이어가기를 반복한다 -주의 점을 하나 선택할때마다 근처 점들의 weight를 가져오는 것은 비효율적이다. 그래서 배열D에 각 노드에서 다른 한 노드까지 걸리는 wieght의 최소값을 저장해놓는다. D의 값들 중 최솟값을 T로 업데이트한다. T를 갱신할때마다 D를 업데이트한다. 이 과정이 추가됨에 따라 Greedy Search+Dynamic program 방법이 섞인 알고리즘이 된다. -Prim MST의 Pseudo Code 입력 : 가중치 그래프 G=(V,E), |V|=n,..

정의 그리디 알고리즘은 최적화 문제를 해결하는 알고리즘 최적화(optimization) 문제 : 가능한 해들 중(선택 순간)에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불린다. 이름만큼 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 '욕심내어' 최소값 또는 최대값을 가진 데이터를 선택하는 것.(부분적인 최적해(Partial Solution)) 당장 눈 앞의 선택을 하기 때문에 '근시안적'선택이라고도 말한다. 이들을 모아 문제의 최적해(Final Solution)를 구한다. \ 특징 -그리디 알고리즘은 한 번 선택하면 이를 절대로 번복하지 않는다. 뒤에 나쁜 결과가 나와도 선택한 데이터를 버리고 다른 것을 취하지 않는다..

-선택 문제란? n개의 숫자들 중에서 K번째로 작은 숫자를 찾는 문제이다. 최소 숫자를 k번 찾거나, 숫자들을 정렬한 후 k번째 숫자를 찾는 방법도 있지만, 각각 최악의 경우 O(kn)과 O(nlogn)의 수행 시간이 걸린다. 그래서 다른 방법으로, 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 2/1로 나눈 두 부분 중에서 한 부분만을 검색하는 방법이 있다. 퀵 정렬처럼 피봇을 무작위로 선택하고 한 부분을 정렬시킨다. 퀵 정렬과 다른 점은, 원하는 수가 속하는 '원하는 그룹'이 아니라면 정렬시킬 필요가 없다는 것이다. Small group은 피봇보다 작은 숫자의 그룹이고, Large group은 피봇보다 큰 숫자의 그룹 이 때 각 그룹의 크기를 알면, k번째 작은 숫자가 어..

분할 정복 알고리즘이란? -주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘. ->문제를 나누어서 풀면 더 효율적인 경우 사용 -대부분의 분할 정복 알고리즘은 분할만 해서는 해를 구할 수 없다. -따라서 분할된 부분 문제들을 정복해야한다. ->부분해를 찾는다. ->일반적으로 부분 문제들의 해를 취합하여 보다 큰 부분 문제의 해를 구한다. -종류 1.합병 정렬(merge sort) 합병 정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘. 1)n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할(Divide) 2)각각의 부분문제를 해결(Conquer) 3)재귀적으로 합병 정렬(Merging) 2.퀵 정렬(quick sort) 위와 반대로 정복 후 분..