이너의 Computer Library

생각나는 대로 올리겠슴니다

출처 : 서울특별시교육청 출간 고등교과 <알고리즘>, 위키백과

동적 계획법(DP : Dynamic Programming)

문제를 해결하기 위해 문제를 해결이 가능한 더 작은 문제로 분할함. 그런 다음 작은 문제를 먼저 해결하고 그 결과를 활용하여 전체 문제를 해결하는 방법.

> 메모이제이션(Memoization)

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.

ex) fiboncci 수열을 구하는 함수 fib(n)이 있을 때, 여러 번 함수를 수행할 경우 같은 인자값에 대해 반복함. 실행시간 단축을 위해 따로 저장공간을 두어 fib(n)을 계산할때마다 그 저장공간에 저장하고 필요할때 마다 참조.

활용 : 검색, 소스 코드 생성, 암호화 또는 데이터 압축 영상 변환과 같은 반복 계산 ..

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

> Top down(하향식) vs Bottom up(상향식)

문제를 여러 작은 부분으로 분할하는 형식의 Top down(=분할 정복)

제일 작은 부분부터 해결해 나가면서 큰 부분을 해결하는 형식의 Bottom up(=동적 프로그래밍)

욕심쟁이 알고리즘(그리디 알고리즘 : Greedy Algorithm)

현재의 상태에서 가장 좋다고 판단되는 것부터 선택하여 나가는 방법. 때로는 그리디 알고리즘이 가장 효율적이고 간단할 때가 있기 때문에 알고리즘이 항상 최적인 해답을 주는지 확인이 필요함.

역추적 기법(Back Tracking)

가능한 모든 방법을 빠짐없이 탐색하여 문제를 해결하는 방법. 이 기법은 데이터의 양이 조금만 늘어나도 실행시간이 엄청나게 늘어나기 때문에 불필요한 탐색을 하지 않기 위해 가지치기 전략을 구사하여 실행시간을 줄여야 함.

분할 정복(Divide and Conquer)

주어진 문제를 원래 문제와 같은 형태의 작은 문제들로 나누어 문제를 해결하는 기법. 나누어진 문제가 해결이 어렵다면 해결할 수 있을 만큼 더 작은 문제들로 나누어 해결하는 방식

그래프 탐색 방법

> DFS(Depth First Search, 깊이 우선 탐색)

> BFS(Breadth First Search, 너비 우선 탐색)

#include <stdio.h>

int main() {
	int a[1001] = {0,}; //에라토스테네스의 체를 이용한 소수 찾기 알고리즘
	int i,j,count=0;    //acmicpc 1987번 문제풀이  
	int N;
	
	for(i=2;i<1001;i++)
		a[i]=1;
		
	for(i=2;i<1001;i++) {
		if(!a[i]) continue;
		
		for(j=i*2;j<1001;j+=i) {
			a[j]=0;
		}
	}
	
	scanf("%d",&N);
	
	for(i=0;i<N;i++) {
		scanf("%d",&j);
		if(a[j]) count++;
	}
	
	printf("%d",count);
}

에라토스테네스의 체? : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 개념

이미 정렬된 자료에 대한 검색 알고리즘. 파일을 이분화하면서 검색 대상이 되는 키 값과 중간 위치의 값을 비교하면서 검색하는 방법.

앞에서부터 하나하나 검색하는 순차 검색보다 보다 효율성이 높다.

한번 비교할때마다 검색의 범위가 반으로 줄어드므로 수행 복잡도는 최소 O(log^n)

2. 과정

① 정렬된 데이터에서 첫 번재 위치를 left, 마지막 위치를 right로 설정

② middle 값을 구한다. (middle = (left + right) / 2)

③ middle 값이 찾고자 하는 데이터이면 검색을 종료.

   찾고자 하는 데이터가 아닐떄,

   1) 찾고자 하는 값 > middle 값일때

   left = middle+1로 재설정 후 2~3번의 과정 반복

   2) 찾고자 하는 값 < middle 값일때

   right = middle-1로 재설정 후 2~3번의 과정 반복

④ left>right이 되면 검색 종료(찾고자 하는 데이터 값이 없음)

3. Code

#include <stdio.h>

int binary_search(int a[], int n, int key) {
	int left, right, middle;
	left = 0;
	right = n-1;
	
	while(!(left>right)) {
		middle = (left+right)/2;
		if(key>a[middle])
			left = middle+1;
		else if(key<a[middle])
			right = middle-1;
		else
			return middle;
	}
	
	return -1;
}

int main() {
	int i, key, find, count;
	int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
	
	count = sizeof(array)/sizeof(int);
	printf("array[] 데이터 : ");
	for(i=0;i<count;i++) {
		printf("%d\t", array[i]);
	}
	printf("\n");
	
	printf("찾고자 하는 데이터를 입력해주세요 : ");
	scanf("%d", &key);
	
	find = binary_search(array, count, key);
	if(find > -1)
		printf("array[%d] = %d", find, array[find]);
	else
		printf("값이 존재하지 않습니다.\n");
}

1. 정렬(Sort)이란?

컴퓨터 기억 공간 내에 순서 없이 배열된 자료들 중에서 특정 항목을 키로 하여 키 값에 따라 오름차순 또는 내림차순으로 자료를 재배열하는 것

2. 수행되는 장소에 따른 정렬의 구분

1) 내부정렬 - 정렬되는 자료가 적어서 자료 전체의 정렬이 주기억 장치에서 이루어지는 정렬 방식

삽입법 : 레코드의 키를 비교하여 삽입하는 방식 ex) 삽입 정렬(insertion sort), 쉘 정렬(shell sort)

교환법 : 레코드의 키를 비교하여 교환하는 방식 ex) 선택 정렬(selection sort), 퀵 정렬(quick sort), 버블 정렬(bubble sort)

선택법 : 레코드의 키들 중에서 가장 큰 값이나 작은 값을 선택하는 방식 ex) 힙 정렬(heap sort)

병합법 : 레코드의 키를 병합하는 방식 ex) 병합 정렬(merge sort)

분배법 : 레코드의 키를 구성하는 각 자릿수를 특정 버킷에 분배하여 정렬하는 방식 ex) 기수 정렬(radix sort)

2) 외부정렬 - 정렬되어야 할 자료가 매우 많아 자료를 보조 기억 장치에 기억시켜 놓은 상태에서 주기억 장치에서 처리할 수 있는 양만큼을 가져와 정렬하고 보조 기억 장치에 저장하는 과정을 반복하면서 자료 전체의 정렬이 보조 기억 장치에서 이루어지는 정렬 방식

ex) 병합 정렬(merge sort)

3. 정렬에 따른 수행 속도 비교

삽입 정렬, 선택 정렬, 버블 정렬 : O(n^2)                                                                              

- 대량의 데이터를 정렬하는 방법으로는 이용 x

쉘 정렬 : 증분에 따라 성능이 조금씩 달라지만 일반적으로 O(n(logn)^2) ~ O(n^2)의 성능을 가짐      

- 속도면에서 빠르고 안정적임. 부분적으로 정렬되어 있을 때 더 효율적.

힙 정렬 : O(nlogn)

- 힙을 생성하는데 O(n)의 수행 과정을 거치고 n번 삭제하는데 O(nlogn)의 수행 과정을 거침. 수나 형태에 무관하게 거의 고른 성능을 보여줌.

퀵 정렬 : O(nlogn)

- 보통 pivot값은 배열의 끝의 값을 이용하지만 한 번의 탐색을 통해 average 값을 pivot 값으로 설정하면 효율을 높일 수 있다. 매우 빠르고 성능이 좋지만 구간이 넓을 경우에 한하고 구간이 어느 정도 좁혀지면 그다지 빠르지 않음. 분할된 데이터 수가 적다면 삽입 or 선택 정렬이 오히려 더 빠를 수 있음.

n개의 레코드 개수가 있을때 레코드 위치를 결정하기 위해 n번의 비교를 하고 서브 파일에 대해 n/2번 비교를 하고 계속해서 n/4, n/8 ... 번 비교를 하게 됨.

병합 정렬 :

2-way 병합 정렬 알고리즘 : O(m+n)

- 이미 정렬된 두 개의 파일을 정렬하여 한 개의 다른 파일로 만드는 것. 두개의 while문은 두 배열중 어느 한쪽이 끝나면 다른 한쪽에 있는 자료를 새로운 배열에 비교 없이 넣는 연산을 수행하므로 첫 번째 파일 개수를 m, 두 번째 파일 개수를 n이라 하면 두 개의 정렬된 파일을 병합하는데 이를 더한 수행 시간이 소요됨.

n-way 병합 정렬 알고리즘 : O(nlogn)

- n개의 데이터를 분할하는데 O(n), 분할을 한 번 할때마다 부분 배열의 길이가 절반으로 줄기 때문에 log₂n회 분할됨.

기수 정렬 : O(n)

- 각 버킷을 배열을 이용하기 보다는 연결리스트를 이용하여 처리하면 기억 장소를 절약할 수 있음.

  정렬될 자료의 개수가 n일때 비교 횟수는 각각의 레코드에 대해 n번씩 수행됨 -> O(n), 자리수가 b일때 O(bn)의 수행 시간이 걸리지만 b를 상수 취급.

4. 빅오표기법으로 본 수행 시간 비교(레코드의 수, 키값 무시. 병합정렬 제외)

기수 정렬(O(n)) > 퀵 정렬(O(nlogn)) > 힙 정렬(O(nlogn)) > 쉘 정렬(O(n(logn)^2) ~ O(n^2)) >= 삽입 정렬, 선택 정렬, 버블 정렬(O(n^2))

#include <stdio.h>

int main() {
	printf("왜 다른분들은 잘되는데 나는 안되지?");
	return 0; 
	
}

Ace 사용중인데 왜 대체 색깔이 안나오는걸까요오오 ㅠㅠ

프로그래밍을 공부하다 보면 맞닥뜨리는 헷갈리는 말중에 동기식과 비동기식이 있습니다. 저도 프로젝트 진행중에 동기와 비동기 전송의 이해 때문에 애를 먹었던 적이 있었기에.. (..//) 지금이라도 정리를 해서 저같이 헷갈려하는 사람이 없었으면 좋겠네요 :)

네이버 국어사전에 의하면..

동기식 전송 방식(STM : synchronous transfer mode)

전송로상에서 신호 정보를 일정 주기의 프레임(frame)으로 구획짓고, 프레임을 시간 슬롯(time slot)으로 분할해서 전송하는 시분할 다중 방식. ITU-T(구 CCITT)에서 1986년 광대역 종합 정보 통신망(B-ISDN)의 전송 방식을 검토할 때에 비동기 전송 방식(ATM)과 함께 용어를 결정했다. 
회선 교환 방식과 같이 하나의 호를 위하여 하나의 채널을 발착신 단말 사이에 점유시키지 않고 다중화하는 이점이 있으나, 동기화를 위해서 발신자와 수신자가 같은 클록 신호를 사용해야 하기 때문에 1채널당 최대 통신 속도가 일정해야 하는 제약이 있다....(이하 생략)

(출처 : http://krdic.naver.com/user.nhn?docid=e3b7bd1f0479a9750f4bd1504fd71736)

비동기 전송 방식(ATM : asynchronous transfer mode)

ITU-T에서 1988년에 광대역 종합 정보 통신망(B-ISDN)의 전송 방식으로 결정하여, B-ISDN의 핵심이 되는 전송ㆍ교환 기술. 모든 정보를 ATM 셀이라는 고정 길이의 블록으로 분할하여 이것을 순차적으로 전송하는 방식이다.

(중략) 이와 같이 ATM은 패킷 교환의 높은 전송 효율을 이어받고, 회선 교환의 단점인 교환 지연 회선 사용 효율의 저하를 시정하여 다양한 정보를 고속으로 처리할 수 있는 기술이다.

(출처 : http://krdic.naver.com/user.nhn?docid=c1c0b4c11bba29af8193679325726886)

네. 무슨 소리인지 저도 잘 모르겠습니다 :D 

저 내용을 모두 이해할 수 있다면 정말 좋겠지만! 소프트웨어 관점에서의 동기식/비동기식 전송 방식의 풀이를 최대한 간략하게 풀이하자면..

동기식 : Request의 결과값 = Return되는 값

비동기식 : Request의 결과값 != Return되는 값 (!는 아니함을 의미합니다. !=는 같지 않다는 뜻이 되죠)

중요한 차이점은 제어권을 어떻게 넘기느냐 입니다.

동기식은 한 개의 동작이 완전히 종료되고 나서 제어권을 반납하고, 비동기식은 한 개의 동작이 끝나지 않았어도 제어권을 반납하고 동작을 계속 수행합니다.

정말로 좋은 예시가 있기에 출처를 남기고 사진을 올려봅니다. (출처 : https://bluekms21.blog.me/10171193149)

동기와 비동기는 각각의 장단점이 존재합니다.

동기식은 명령이 들어온 순서대로 빠르게 하나하나 수행이 가능하지만 여러 일을 동시에 수행하는 멀티태스킹이 불가능합니다.

멀티태스킹을 목적으로 탄생한 비동기식은 여러 일을 동시 수행을 가능하게 한다는 장점이 있지만 동기식보다 속도가 저하될 가능성이 있고 과한 명령을 프레임에 쌓아둘 경우 부하가 발생할 수 있습니다. 이러한 Request들을 처리하기 위해 쓰레드에서 Callback(콜백)함수로 제어하고 Handler(핸들러)로 요청 결과를 확인합니다.

비트코인 열풍으로 가상화폐에 대한 뜨거운 관심이 지속되고 있는 가운데, 다른 사용자들의 PC를 이용해 화폐를 채굴하는 신종 '범죄'가 유행하고 있다고 합니다.

그렇다면 이러한 크립토재킹은 어떠한 원리로 작용하길래 다른 PC가 접속만 해도 자동으로 채굴해주는 것일까요?

우선 크립토재킹이란 디지털 화폐를 의미하는 cryptocurrency와 납치하다를 의미하는 hijacking의 합성어입니다.(crypto+jacking)

말그대로 다른 사람의 컴퓨터를 이용해 디지털 화폐를 캐고 그것을 납치한다라는 의미라 보시면 되겠습니다.

기존에는 Coinhive 라는 업체에서 웹에서 비트코인을 채굴할 수 있게 함으로써 스크립트로서 하여금 수익을 벌 수 있는 순수한 목적으로 만들어졌습니다. 하지만 선이 존재하면 악도 존재하는 법이죠. 이를 이용하여 악의적으로 사이트에 스크립트를 삽입하거나 다운로드 후 실행파일로써 채굴하게 하는 것이죠. 크게 보는 스크립트 실행 과정은 이러합니다.

만일 사용하고 있는 단말기 혹은 PC가 급속도로 느려지거나 사용 플랫폼의 CPU 점유율이 100% 가까이 올라간다면 채굴 스크립트나 프로그램이 실행되었음을 의심해보셔야 합니다. 만약 크립토재킹이 의심된다고 하시면 현재 백그라운드에 실행되고 있는 의심되는 프로세스나 웹사이트를 다 종료시켜 주시거나 PC 전원을 껏다 켜주심이 좋을 것 같습니다. 

또한 whoismining.com - 후이즈마이닝이라는 사이트를 통해 코인하이브의 유무를 확인할 수 있다고 합니다.

사이트 접속에 있어 각별한 주의가 필요할 것 같습니다.

[출처]

http://news.naver.com/main/read.nhn?mode=LS2D&mid=shm&sid1=105&sid2=732&oid=015&aid=0003872329

정보처리기능사 필기 취득을 위한 메모장입니다.

계속해서 공부하면서 업데이트할 예정이고 시험보시기 전에 잠깐씩 공부할 수 있는 목적으로 만들었습니다. 

상반되는 내용이나 비슷한 내용은 /* */을 이용한 주석으로 묶어두었습니다.

영어 단어장처럼 봐주셨으면 하고 도움이 되었으면 하는 바람입니다. 감사합니다. 

<용어 정리>

이항 연산 : 두 개의 항으로부터 결과를 얻어내는 연산. ex)AND

단항 연산 : ex) ROTATE, SHIFT, MOVE, NOT(COMPLEMENT)

전가산기 : 반가산기 2개와 OR 게이트로 구성

명령어 : [Op-Code] | [Operand]로 구성

PSW : CPU에서 명령이 실행될 차례를 제어하거나 특정 프로그램과 관련된 컴퓨터 시스템의 상태를 나타내고 유지해 두기 위한 제어 워드. 실행중인 CPU 상태 저장

버퍼 레지스터 : 서로 속도가 다른 장치의 속도를 맞추는 보조 역할을 하는 기억장치

도메인 : 하나의 속성이 취할 수 있는 속성 값들의 집합

DSU(Digital Service Unit) : 디지털 신호를 디지털 그대로 전송해주는 장치

/*

* 프로세스 상태 변화

디스패치(Dispatch) : 다중 태스킹 환경에서 우선순위가 가장 높은 작업이 수행될 수 있도록 시스템 자원을 할당하는 것. 컴퓨터 처리결과를 데이터 처리 의뢰처에 배포하는 것.

블록, 보류(Block) : 실행 상태의 프로세스가 종료되기 전에 입출력이나 기타 다른 작업을 필요로 할 경우 CPU를 반납하고 작업의 완료를 기다리기 위해 대기 상태로 전환

깨움, 웨이크 업(Wake Up) : 입출력 작업 종료 등 기다리던 사건이 일어났을 때 보류 상태에서 준비 상태로 넘어가는 과정

타이머 종료, 시간제한(Timeout) : 운영체제는 프로세스가 프로세서를 계속 독점해서 사용하지 못하게 하기 위해 clock interrupt를 두어서 프로세스가 일정 시간동안만 프로세스를 점유할 수 있게함

*/

/*

프로그램 카운터: 다음에 실행될 명령어의 주소가 저장되어 있는 기억장소

명령어 레지스터 : 현재 실행중인 명령어의 주소가 저장되어 있는 기억장소

*/

/*

Hamming 코드 : 에러를 검출하고 검출된 에러를 교정하기 위하여 사용되는 코드

패리티 비트 : 에러 검출만 가능

*/

/*

0-주소 형식 : OP코드로만 구성. 스택을 이용하여 연산

1-주소 형식 : 

*/

/*

- 프레젠테이션 기본단위 : 슬라이더

> 슬라이더 개개의 구성요소 : 개체

> 화면 전체를 전환하는 단위 : 쪽(슬라이드)

> 흐름을 기획한 것 : 시나리오

- 스프레드시트 기본단위 : 셀

*/

/*

<주소 지정 방식> - 프로그램이 수행되는 동안 사용될 데이터의 위치를 지정하는 방법

* 주소 표현 방식

- 절대 주소 : 기억장치 고유의 번지로 0,1,2,3.. 과 같이 16진수 순서대로 결정한 주소

- 상대 주소 : 기준 번지로부터 상대적으로 어느 정도 떨어져 있는지 변위로 표현하는 주소

* 주소 지정 방법

- Direct Addressing Mode(직접 번지 지정) : 메모리 참조 1회. 지정하려는 위치를 번지부에서 직접 표현한 형식

- Indirect Addressing Mode(간접 번지 지정) : 메모리 참조 2회 이상

- Immediate Addressing Mode(즉시 주소 지정) : 메모리 참조 x

- 색인 Addressing : 순차적 주소지정 등에 유리. 주소지정에 2개의 레지스터 사용

- 계산의 의한 주소 지정방식

> Relative Mode(상대주소) : 명령어의 주소 부분 + PC(프로그램 카운터)
                                    명령어 자신의 기억장소를 기준으로 하여 데이터의 위치를 지정하는 방식

> Base Register Mode(베이스 레지스터) : 명령어의 주소 부분 + Base Register

   프로그램을 재배치할 때 이용

> Index Register Mode(인덱스 레지스터) : 명령어의 주소 부분 + Index Register

* 처리 속도(빠른 순서대로)

묵시적 - 즉시 - 직접 - 간접

*/

<설명충>

* op code를 N bit 사용하면 인스트럭션은 2^N개 사용할 수 있다.

* 윈98에서 디스켓을 포맷할때 파일 복구 기능은 없다.

* 윈98의 작업 표시줄 위에서 오른쪽 마우스 버튼을 누르면 나타나는 도구 모음 : 연결, 주소, 빠른 실행(2006.10)

* 윈98에서 시작버튼을 누를 때 나오는 주(main)메뉴 : 문서, 도움말, 프로그램(2002.10)

* 유닉스의 명령어 해석기는 쉘(SHELL)이고, DOS의 명령어 해석기는 COMMAND.COM

* 망형 망의 필요 회선수는 n(n-1)/2

* 데이터 통신 시스템의 구성요소 : 전송계, 처리계, 단말계

<DATABASE>

데이터베이스 작업의 최소 단위 : 트랜젝션

DB Language 종류

DDL(Data Definition Language) : 데이터베이스 정의어

DML(Data Manipulation Language) : 데이터베이스 조작어

DCL(Data Control Language) : 데이터베이스 제어어

<DOS 명령어 모음>

FDISK : 파티션 분할 명령어(파티션 디스크의 약자)

CHKDSK : 체크 디스크의 약자로 디스크 오류 수정

MD : Make Directory 의 약자. 디렉토리 만들기

DELETE : 삭제

UNDELETE : 삭제 한것 복구

안드로이드 스튜디오를 하다가 종종 만나는 오류들 중 하나. Cannot resolve symbol 'R'(저도 방금 발생한 오류이기에 이렇게 글을 적어봅니다)

R.java를 건들지도 않았는데 왜 안스를 켤때마다 이런 에러가 뜨는지 고민이신 분들에게 해결 방법을 제시해..보도록 하겠습니다.

1) 원인

R.java가 빌드가 제대로 되지 않았거나 오타가 있는 경우가 대부분을 차지합니다.

2) 해결방법

1. AndroidManifest.xml, layout의 ~.xml 파일 등(대부분 건드리는 부분)에 오타가 있는지 확인 한다.

2. Build > Clean project를 시도해본다.

말그대로 전에 빌드했던 project를 비운다는 뜻입니다 :D

3. File > Invalidate Caches/Restart를 시도해본다.

'캐시 무효화 후 재시작'이라는 의미입니다. 때로는 많은 양의 캐시가 우발적으로 에러를 발생시킬 수 있기에 캐시를 비워줍시다.

모두가 이 세가지 범위 안에서 이 에러를 고쳤으면 좋겠습니다 :)

만약 그래도 고쳐지지 않는다면.. 프로젝트를 다시 만드는게.. 더 빠를 수도 있을겁니다!