ETC./Algorithm(38)
-
ETC./Algorithm
2019.06.06
[Algorithm] 소수를 판별하는 알고리즘
1보다 큰 임의의 정수를 입력하여 소수를 판별 1. 입력받은 숫자보다 작은 모든숫자를 다 나누어본다. 어떤 수 X가 소수 인지를 판별하려면 X를 2부터 X보다 작은 수(X-1)까지 차례대로 나누어 떨어지는지 검사하면 됩니다. 예컨데 5는 2,3,4,로 나누었을때 한번도 나누어 떨어지지 않으므로 소수이고, 4는 2로 나누었을때 나누어 떨어지므로 소수가 아닙니다. C언어 / C++ 코드 #include main(){ int a, i, j; scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다. i=2; j=a-1; f(a==1){ //1은 소수가 아님 printf("소수아님"); return; } while(1){ //무한루프 if(i
-
ETC./Algorithm
2019.06.05
1
[Algorithm] 피보나치 수열의 합계 구하기
피보나치 수열이란? 피보나치 수열은 첫번째 항과 두번쨰 항을 더해서 세번째 항을 만들고 두번쨰 항과 세번쨰 항을 더해서 네번쨰 항을 만드는 방법으로, 계속해서 다음항을 만들어가는 수열입니다. 피보나치 수열의 10번째 항까지의 합계 구하기 3개의 변수로 먼저 첫번째 항(A), 두번째 항(B), 세번째 항(C)를 만든 후, 두번째 항(B)를 첫번째 항(A)에 치환하고 세번째 항(C)를 두번째 항(B)에 치환한 후 첫번째 항(A)와 두번째 항(B)를 더하여 다시 세번째 항(C)를 만드는 방법을 반복합니다. C언어 / C++ 코드 #include main() { int a = 1, b =1; //첫번째항, 두번쨰항 int c; //세번째항 int sum = 2, cnt = 2; //합계 sum, 항의갯수 cnt..
-
ETC./Algorithm
2019.06.04
[Algorithm] 팩토리얼 수열의 합계 구하기
팩토리얼 수열이란? 수학에서, 자연수의 계승 또는 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱입니다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말입니다. 기호는 느낌표(!)를 사용합니다. 팩토리얼이라고 읽으며 팩토리얼을 줄여서 팩이라고 읽기도 합니다. 팩토리얼 수열의 5번째 항까지의 합계구하기 (1!+2!+3!+4!+5!) 팩토리얼의 합계를 구하는 알고리즘을 풀기 위해서는 각 항 사이에서 일정한 비율로 증가하여 곱할 값으로 사용할 증가 배수 변수 i, 증가 배수를 곱하여 수열의 각 항을 만들어 저장할 변수 Sum, 그리고 수열의 각 항인 j가 만들어질때마다 그 값을 누적할 변수 K가 필요합니다. C언어 / C++ 코드 #include main() { ..
-
ETC./Algorithm
2019.06.03
[Algorithm] 여러가지 수열의 합계 (다양한 유형)
1번문제 : 1 ~ 100까지의 합계 (1+2+3+4···+100) 0에서 1씩 증가시켜 100까지 변경되는 수열을 더하려면 두개의 변수를 선언하셔야 합니다. 변수 i에는 수열의 각항을 만들기 위하여 반복문을 사용하여 +1씩 더하여주고, 또다른 변수 Sum에는 수열의 각 항이 1씩증가할때마다 그값을 누적하여 저장하면 됩니다. C언어 / C++ 코드 #include main(){ int i,sum; //정수형변수 i와 sum을 선언 i=0; sum=0; //i와 sum을 0으로 초기화 do{ i++; //i를1씩 증가 sum +=i; //sum값에 i를 누적시켜 저장 }while(i
-
ETC./Algorithm
2018.08.28
[Algorithm] 인덱스 구조란 무엇인가?
인덱스의 개념 인덱스는 데이터 레코드를 빠르게 접근하기 위해서 구성하는 것으로 다음과 같은 특징이 있다. 1. 인덱스는 데이터가 저장된 물리적 구조와 밀접한 관계가 있다. 2. 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다. 3. 인덱스를 통해서 파일의 레코드에 대한 액세스를 빠르게 수행할 수 있다. 4. 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는것이 효율적이다. 트라이(Trie)색인 트라이 색인은 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조이다. 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 떄 적합하다. 1. 가변 길이의 키 값을 효율적으로..
-
ETC./Algorithm
2018.08.27
[Algorithm] 해시테이블과 해싱함수에 대해서
해싱이란? 해싱은 Hash Table이라는 기억공간을 할당하고, 해시 함수(Hash Table)이라는 기억공간을 할당하고, 해시함수(Hash Function)을 이용하여 레코드 키에 대한 Hash Table내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다. 1. 해싱은 DAM(직접 접근)파일을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구된다. 2. 다른 방식에 비해 검색 속도가 가장 빠르다. 3. 삽입 삭제 작업의 빈도가 많을 때 유리한 방식이다. 4. 키-주소 변환 방법이라고도 한다. 해시테이블(HashTable) 해시테이블은 레코드를 한개 이상 보관할 수 있는 Bucket들로 구성된 기억공간으로 보조기억장치에 구성할 수..
-
ETC./Algorithm
2018.08.26
[Algorithm] 여러가지 검색(Search)기법
여러가지 검색의 종류 검색이란 컴퓨터를 이용해서 기억공간에 보관중인 특정 레코드를 찾아내는 작업이다. 선형 검색(Linear Search) 1. 선형 검색은 순서화되어 있지 않은 파일에서 순차적으로 검색하는 방식으로 찾고자 하는 Key값을 첫번째 레코드 Key값으로부터 차례로 비교하여 검색하는 방식이다. 2. 순차검색(Sequential Search)라고도 한다. 3. 프로그램 작성이 비교적 간단하다. 제어 검색(Control Search) 1. 제어 검색은 반드시 순서화된 파일이어야 검색할 수 있다. 2. 한번의 비교 동작이 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용하여 검색하는 방식이다. 이분 검색(이진 검색, Binary Search) 1. 이분검색은 전체 파일을..
-
ETC./Algorithm
2018.08.25
[Algorithm] 트리(Tree)구조란 무엇인가?
트리(Tree)의 정의 트리는 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태이다. 가족의 계보(족보), 연산수식, 회사 조직 구조도, 히프등을 표현하기에 적합하다. 트리(Tree) 관련용어 노드(Node) : 트리의 기본요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것 EX : A, B, C, D, E, F, G, H, ,I ,J ,K ,M 근 노드(Root Node) : 트리의 맨 위에 있는 노드 EX : A 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수 EX : A=3 , B=2, C=1 단말 노드(Terminal Node) : 자식이 하나도 없는 노드 EX : K, L, F, G, M, I, J 비단말 노..
-
ETC./Algorithm
2018.08.24
[Algorithm] 큐(Queue)와 데크(Deque)에 대해서
큐(Queue) 1. 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다. 2. 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO)방식으로 처리한다. 3. 시작과 끝을 표시하는 두 개의 포인터가 있다. 프런트(F) 포인터 1. 가장 먼저 삽이된 자료의 기억공간을 가리키는 포인터이다. 2. 삭제 작업을 할때 사용한다. 리어(R) 포인터 1. 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터이다. 2. 삽입 작업을 할 때 사용한다. Queue의 응용분야 1. 창구 업무나 택시 정거장처럼 서비스 순서를 기다리는 등의 대기행렬의 처리에서 사용한다. 2. 운영체제의 작업 스케줄링에 사용한다. 데크(Deque) 1. 삽입과 삭제가 ..
-
ETC./Algorithm
2018.08.23
[Algorithm] 스택(Stack)이란 무엇인가?
스택의 개념 1. 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다. 2. 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO)방식으로 자료를 처리한다. Overflow : 스택으로 할당받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow를 발생시킨다. Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시킨다. ※ Stack에 기억되어 있는 자료를 삭제시킬 때는 제일 먼저 삭제할 자료가 있는지 없는지부터 확인해야 한다. Stack의 응용분야 ..
-
ETC./Algorithm 2019.06.06[Algorithm] 소수를 판별하는 알고리즘 1보다 큰 임의의 정수를 입력하여 소수를 판별 1. 입력받은 숫자보다 작은 모든숫자를 다 나누어본다. 어떤 수 X가 소수 인지를 판별하려면 X를 2부터 X보다 작은 수(X-1)까지 차례대로 나누어 떨어지는지 검사하면 됩니다. 예컨데 5는 2,3,4,로 나누었을때 한번도 나누어 떨어지지 않으므로 소수이고, 4는 2로 나누었을때 나누어 떨어지므로 소수가 아닙니다. C언어 / C++ 코드 #include main(){ int a, i, j; scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다. i=2; j=a-1; f(a==1){ //1은 소수가 아님 printf("소수아님"); return; } while(1){ //무한루프 if(i
-
ETC./Algorithm 2019.06.05 1[Algorithm] 피보나치 수열의 합계 구하기 피보나치 수열이란? 피보나치 수열은 첫번째 항과 두번쨰 항을 더해서 세번째 항을 만들고 두번쨰 항과 세번쨰 항을 더해서 네번쨰 항을 만드는 방법으로, 계속해서 다음항을 만들어가는 수열입니다. 피보나치 수열의 10번째 항까지의 합계 구하기 3개의 변수로 먼저 첫번째 항(A), 두번째 항(B), 세번째 항(C)를 만든 후, 두번째 항(B)를 첫번째 항(A)에 치환하고 세번째 항(C)를 두번째 항(B)에 치환한 후 첫번째 항(A)와 두번째 항(B)를 더하여 다시 세번째 항(C)를 만드는 방법을 반복합니다. C언어 / C++ 코드 #include main() { int a = 1, b =1; //첫번째항, 두번쨰항 int c; //세번째항 int sum = 2, cnt = 2; //합계 sum, 항의갯수 cnt..
-
ETC./Algorithm 2019.06.04[Algorithm] 팩토리얼 수열의 합계 구하기 팩토리얼 수열이란? 수학에서, 자연수의 계승 또는 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱입니다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말입니다. 기호는 느낌표(!)를 사용합니다. 팩토리얼이라고 읽으며 팩토리얼을 줄여서 팩이라고 읽기도 합니다. 팩토리얼 수열의 5번째 항까지의 합계구하기 (1!+2!+3!+4!+5!) 팩토리얼의 합계를 구하는 알고리즘을 풀기 위해서는 각 항 사이에서 일정한 비율로 증가하여 곱할 값으로 사용할 증가 배수 변수 i, 증가 배수를 곱하여 수열의 각 항을 만들어 저장할 변수 Sum, 그리고 수열의 각 항인 j가 만들어질때마다 그 값을 누적할 변수 K가 필요합니다. C언어 / C++ 코드 #include main() { ..
-
ETC./Algorithm 2019.06.03[Algorithm] 여러가지 수열의 합계 (다양한 유형) 1번문제 : 1 ~ 100까지의 합계 (1+2+3+4···+100) 0에서 1씩 증가시켜 100까지 변경되는 수열을 더하려면 두개의 변수를 선언하셔야 합니다. 변수 i에는 수열의 각항을 만들기 위하여 반복문을 사용하여 +1씩 더하여주고, 또다른 변수 Sum에는 수열의 각 항이 1씩증가할때마다 그값을 누적하여 저장하면 됩니다. C언어 / C++ 코드 #include main(){ int i,sum; //정수형변수 i와 sum을 선언 i=0; sum=0; //i와 sum을 0으로 초기화 do{ i++; //i를1씩 증가 sum +=i; //sum값에 i를 누적시켜 저장 }while(i
-
ETC./Algorithm 2018.08.28[Algorithm] 인덱스 구조란 무엇인가? 인덱스의 개념 인덱스는 데이터 레코드를 빠르게 접근하기 위해서 구성하는 것으로 다음과 같은 특징이 있다. 1. 인덱스는 데이터가 저장된 물리적 구조와 밀접한 관계가 있다. 2. 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다. 3. 인덱스를 통해서 파일의 레코드에 대한 액세스를 빠르게 수행할 수 있다. 4. 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는것이 효율적이다. 트라이(Trie)색인 트라이 색인은 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조이다. 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 떄 적합하다. 1. 가변 길이의 키 값을 효율적으로..
-
ETC./Algorithm 2018.08.27[Algorithm] 해시테이블과 해싱함수에 대해서 해싱이란? 해싱은 Hash Table이라는 기억공간을 할당하고, 해시 함수(Hash Table)이라는 기억공간을 할당하고, 해시함수(Hash Function)을 이용하여 레코드 키에 대한 Hash Table내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다. 1. 해싱은 DAM(직접 접근)파일을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구된다. 2. 다른 방식에 비해 검색 속도가 가장 빠르다. 3. 삽입 삭제 작업의 빈도가 많을 때 유리한 방식이다. 4. 키-주소 변환 방법이라고도 한다. 해시테이블(HashTable) 해시테이블은 레코드를 한개 이상 보관할 수 있는 Bucket들로 구성된 기억공간으로 보조기억장치에 구성할 수..
-
ETC./Algorithm 2018.08.26[Algorithm] 여러가지 검색(Search)기법 여러가지 검색의 종류 검색이란 컴퓨터를 이용해서 기억공간에 보관중인 특정 레코드를 찾아내는 작업이다. 선형 검색(Linear Search) 1. 선형 검색은 순서화되어 있지 않은 파일에서 순차적으로 검색하는 방식으로 찾고자 하는 Key값을 첫번째 레코드 Key값으로부터 차례로 비교하여 검색하는 방식이다. 2. 순차검색(Sequential Search)라고도 한다. 3. 프로그램 작성이 비교적 간단하다. 제어 검색(Control Search) 1. 제어 검색은 반드시 순서화된 파일이어야 검색할 수 있다. 2. 한번의 비교 동작이 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용하여 검색하는 방식이다. 이분 검색(이진 검색, Binary Search) 1. 이분검색은 전체 파일을..
-
ETC./Algorithm 2018.08.25[Algorithm] 트리(Tree)구조란 무엇인가? 트리(Tree)의 정의 트리는 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태이다. 가족의 계보(족보), 연산수식, 회사 조직 구조도, 히프등을 표현하기에 적합하다. 트리(Tree) 관련용어 노드(Node) : 트리의 기본요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것 EX : A, B, C, D, E, F, G, H, ,I ,J ,K ,M 근 노드(Root Node) : 트리의 맨 위에 있는 노드 EX : A 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수 EX : A=3 , B=2, C=1 단말 노드(Terminal Node) : 자식이 하나도 없는 노드 EX : K, L, F, G, M, I, J 비단말 노..
-
ETC./Algorithm 2018.08.24[Algorithm] 큐(Queue)와 데크(Deque)에 대해서 큐(Queue) 1. 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다. 2. 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO)방식으로 처리한다. 3. 시작과 끝을 표시하는 두 개의 포인터가 있다. 프런트(F) 포인터 1. 가장 먼저 삽이된 자료의 기억공간을 가리키는 포인터이다. 2. 삭제 작업을 할때 사용한다. 리어(R) 포인터 1. 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터이다. 2. 삽입 작업을 할 때 사용한다. Queue의 응용분야 1. 창구 업무나 택시 정거장처럼 서비스 순서를 기다리는 등의 대기행렬의 처리에서 사용한다. 2. 운영체제의 작업 스케줄링에 사용한다. 데크(Deque) 1. 삽입과 삭제가 ..
-
ETC./Algorithm 2018.08.23[Algorithm] 스택(Stack)이란 무엇인가? 스택의 개념 1. 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다. 2. 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO)방식으로 자료를 처리한다. Overflow : 스택으로 할당받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow를 발생시킨다. Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시킨다. ※ Stack에 기억되어 있는 자료를 삭제시킬 때는 제일 먼저 삭제할 자료가 있는지 없는지부터 확인해야 한다. Stack의 응용분야 ..