조용히 끄적끄적

백준 사이트 URL : https://www.acmicpc.net/problem/1707 문제 분석입력 : 테스트크기 T, 정점의 개수 V, 간선의 개수 E, E개의 연결정보출력 : 그래프가 이분 그래프를 이루는지에 대한 여부제한 : 시간제한 2초, 메모리제한 128MB 아이디어 : 이분그래프가 맞는지 확인해주면된다. : http://sanghoon9939.tistory.com/33 에서 확인 가능하다. : 간단하게 visit 처리를 색으로 해준후 이미 visit된 정점을 확인할때 자신과 같은 색이면, NO처리를 해준다. 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354..

▣Bipartite Graph Distinction(이분 그래프 판별) : 이분그래프의 여부를 판별하는 알고리즘-> 이분 그래프 정의: 그래프의 모든 정점을 2그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 한다. : 다음 알고리즘은 위 그래프가 2분그래프인지를 확인하는 알고리즘이다. : 그림에서 볼 수 있는 것과 같이 하나의 간선에 연결된 정점은 다른 색을 가지고 있는 것을 볼 수가 있다. : 즉, BFS 혹은 DFS를 이용하여 탐색을 하며 이미 visit된 정점을 확인할 당시 자기와 같은 색을 갖고 있다면, 이분 그래프가 아님을 확인 할 수가 있다.-DFS기준-: 이런식으로 DFS의 탐색순서를 따라가며, visit 처리를 색으로 구분하게 된다. : 이미 v..

백준 사이트 URL : https://www.acmicpc.net/problem/2696 문제 분석입력 : 테스트크기 T, 수열의 크기 M, 그리고 M길이의 수열의 값출력 : 수열에서 중앙값의 개수를 구한다(단, 중앙값은 홀수개를 기준으로 생성된다), 생성되는 중앙값들을 출력한다.제한 : 시간제한 1초, 메모리제한 128MB 아이디어 : 단순히 배열을 통행 입력받고 매 홀수 번째 마다 정렬 후 가운데 인덱스를 출력하는 방법도 있다. 하지만, 그 경우 시간초과의 위험이 있다. : 2개의 Heap인 Max_Heap과 Min_Heap을 통해 중앙값과 데이터의 입력을 효육적으로 만들 수 있다. 즉, 새로운 값을 넣고 난 후의 두 Heap의 사이즈가 다를 시 Max_Heap의 top()값이 중앙값이 된다. 소스코..

▣ Software & Soft Engineering ▶software 정의 : instruction - 프로그램 실행 시 요구된 function, performance 그리고 feature를 제공하는 명령어. : data structures - 프로그램이 data를 적절하게 조작할 수 있게 하는 자료구조 : documentation - 프로그램의 operation과 use를 설명하는 documentation. ▶software 특징 : developed 되거나 engineered 된것으로 고전적관점에서의 제조된 것이 아니다. : 하드웨어와 다르게 'wear out'없다. 즉, 마모와 같은 손실이 없다. [하드웨어] [소프트웨어] : 산업들이 component-based 방향으로 움직이는 반면, 소프트웨..

백준 사이트 URL : https://www.acmicpc.net/problem/2491 문제분석입력 : 길이 n과 최대 길이와 n개의 정수출력 : 연속된 증가 혹은 감소 수열의 가장 긴 길이를 출력한다. 아이디어1. 감소와 증가 수열의 기록을 저장할 변수를 통해 한번의 탐색으로 해결한다.2. 같은 경우는 두 변수를 증가 시킨다. 그 외는 경우에 따라 증가의 길이, 감소의 길이를 각각 증가 시킨다.3. 길이를 비교하여 최대 길이를 소스 코드123456789101112131415161718192021222324252627282930313233#include int main() { int n, res = 1, pre = 0, num; scanf("%d", &n); int len_1 = 1, len_2 = 1..

▣ 보수 : 디지털 컴퓨터에서 뺄셈 연산과 논리 계산에 상용: r진법에는 두가지 동류의 보수가 존재. 1) r의 보수 / 2) (r-1)의 보수 ▶r-1의 보수 : (r^n-1)-N으로 정의된다. ▶r의 보수 : r^n-N(N=0일때는 0)으로 정의된다. ▶부호 없는 숫자의 뺄셈

▣ 레지스터 : n비트 레지스터는 n비트의 이진정보를 저장하기 위한 n개의 플립플롭과 데이타 처리를 위한 조합 회로로 구성되어 있다. - 가장 단순한 형테는 플립플롭만으로 구성되어 있다. ▶시프트 레지스터 : 저장되어 있는 이진 정보를 단반향 혹은 양방향으로 이동시키는 레지스터 1) SIPO 레지스터 : 2) SISO 레지스터 3) PISO 레지스터 4) PIPO 레지스터 참고) http://blog.naver.com/PostView.nhn?blogId=lagrange0115&logNo=220729360287

▣ 집적회로 : 디지털 게이트를 구성하는 전자부품들을 포함하는 실리콘 반도체. - 소규모 집적(SSI) : 10개 이하의 독립적 게이트가 하나의 칩 / 게이트의 입출력이 곧바로 외부 핀으로 연결 - 중규모 집적(MSI) : 10~200개 까지의 게이트를 집적 / 디코더나 가산기, 레지스터와 같은 기본적 디지털 장치를 구현 - 대규모 집적(LSI) : 200~1000개까지의 게이트를 집적 / 프로세서나 메모리 칩과 같은 디지털 시스템 형성 - 초대규모 집적(VLSI) : 수천개의 게이트를 하나의 칩으로 집적 / 대형 메모리나 복잡한 마이크로 컴퓨터 칩을 형성 [디지털 논리군] : 기술에 따라 분류 - TTL : 가장 많이 사용 - ECL : 고속도가 요구되는 시스템에 사용 - MOS : 부품의 밀도가 높은..

▣ 순차회로 : 순차 회로로 구현되는 저장요소를 필요로 한다. : 불연속적인 특정시각에 저장요소에 영향을 주는 동기형과 클럭이없이 동작하는 비동기형으로 나눠있다. [순차회로의 종류] ▶ SR플립플롭 : S와 R의 입력에 따른 상태 변화는 위의 표와 같다. : S와 R에 1이 입력되면 0과 1도 아닌 중간값을 같은 상태가 지속되는 문제가 발생한다. : 위의 값을 통해 SR플립플롭의 특성방정식을 세워보면 Qn+1 = SR'+R'Qn이 되는것을 알 수있다. : 동기식으로 클럭을 주게 되면 회로도는 다음과 같다. : 클락과 S,R신호를 AND게이트로 연결해 준다. ▶ D플립플롭 : S와 R입력을 인버터로 연결하고 D라는 기호를 붙이것으로 D입력이 클럭 변이 동안 출력에 전달 된다. : 특성방정식 Qn+1 = D..

▣ 조합회로 : 입력과 출력을 가진 논리 게이트의 집합으로 출력의 값은 입력의 0과 1들의 조합함수이다. 반대로, 순차회로는 게이트 뿐만 아니라 플립플로과 같은 기억회로를 포함한다.즉, 순차회로는 상태에대한 정보를 기억할 수 있다. [조합회로의 설계 절차] 1. 문제가 제시 2. 입력과 출력 변수에 문자기호 할당. 3. 입력과 출력사이를 정의하는 진리표 유도 4. 각 출력에 대한 값을 간소화 시킨 부울대수를 얻는다. 5. 간소화된 부울대수를 통해 논리회로를 그린다. 1) 반가산기 : 비트 두개를 서로 산술적으로 가산하는조합회로. 2) 전가산기 : 비트 두개와빝의 자리로부터 올라오는 carry값을 고려하여 3개의 비트를 가산하는 조합회로. : 2개의 반 가산기로 구성된다.