[알고리즘] 기본 추상자료형(2) - 예제(집합ADT) [문제1] 집합A와 B를 입력받고, A가 B의 부분집합인지를 검사하는 프로그램(단일연결리스트) - 오름차순 양의 정수로 저장 및 출력 - A ⊂ B이면 0을 출력, A ⊄ B이면 집합B에 속하지 않은 집합 A의 가장 작은 원소를 출력 입력예시 출력예시 3 5 10 15 4 5 20 25 30 10 입력예시 출력예시0 3 5 10 15 0 입력예시 출력예시 3 5 10 15 0 5 #include #include struct node { int number; struct node *next; }; void addSet(struct node *set, int number){ struct node *newElement = (struct node*)malloc(sizeof(struct node)); newEle.. [알고리즘] 기본 추상자료형(1) - 설명(리스트ADT, 집합ADT) 추상자료형이란 데이터구조의 추상형으로서, 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것이다 종류로는 리스트ADT, 집합ADT, 큐ADT, 트리ADT등이 있다 기억장소 사용량은 모두 O(n)이다 추상자료형 가운데 가장 먼저 알아야할 것은 리스트ADT로, 리스트ADT는 연속적인 임의개체들을 모델링한다 리스트ADT 메소드 1) 일반 메소드 integer size() - 리스트의 크기, 즉 원소 수를 반환 boolean isEmpty() - 리스트가 비어 있는지 여부를 반환 iterator elements() - 원소 전체를 반환 2) 접근 메소드 element get(r) - 순위r에 저장된 원소를 반환 3) 갱신 메소드 element set(r, e) - 순위r에 저장된 원소를 e로 대체 add(r.. [알고리즘] 기초 데이터구조(2) - 예제 [문제1] 이중연결리스트 + 헤더 및 트레일러 노드 프로그램 - addList: position과 element를 받아 list를 추가한다 - deletList: position을 받아 list에서 삭제한다 - getElement: position을 받아 element를 RETURN한다 - printList: list의 모든 element를 순서대로 출력한다 - freeList: list의 메모리할당을 해제한다 입력예시 출력예시9 A 1 A A 2 B A 3 C A 3 D P D 2 P A 1 E P G 4 ABDC ADC EADC invalid position #include #include struct node { char element; struct node *next; struct node *pr.. [알고리즘] 기초 데이터구조(1) - 설명 * 가장 기본이되면서, 중요하기 때문에 모르겠으면 알때까지 공부하세요 데이터를 구축하는 방법으로는 배열과 연결리스트가 있다 배열은 인덱스를 이용해 접근하기 때문에, 접근하기가 쉽다 하지만 추가와 삭제의 경우에는 불편하다 중간에 추가를 하는경우, 한칸씩 미뤄줘야하고 / 삭제의 경우에도 한칸씩 땡겨줘야하기 때문이다 1차원배열을 만드는 코드 int *arr = (int*)malloc(sizeof(int)*100) 또는 int arr[100] 2차원배열을 만드는 코드 int **arr = (int**)malloc(sizeof(int*)*100) for(int i=0; i [알고리즘] 재귀(2) - 예제 [문제1] 양의 정수 n을 입력 받아, 1부터 n까지의 합을 구하는 프로그램 #include int sum(int n){ if (n == 1){ return 1; } else{ return n + sum(n - 1); } } void main(){ int n; scanf("%d", &n); printf("%d\n", sum(n)); } [문제2] 양의 정수를 입력 받아, 각 자리의 수를 높은 자릿수부터 출력하는 프로그램 #include void mod(int n){ if (n >= 10){ mod(n / 10); printf("%d\n", n % 10); } else{ printf("%d\n", n); } } void main(){ int n; scanf("%d", &n); mod(n); } [문제3] .. [알고리즘] 재귀(1) - 설명 재귀 알고리즘은 문제를 해결하는 과정에서 자기 자신을 사용하여 문제를 해결하는 것이다 예시로 1부터 n까지 합을 구하는 sum을 들어보겠다 Alg sum(n) 1. if (n=1) return 1 else return n + sum(n-1) 여기서 if(n=1)은 베이스케이스(base case)로 루프문을 나가기 위한 조건이 된다 else는 재귀케이스(recursive case)로 자기자신을 계속 호출한다 재귀 알고리즘 프로그램을 작성할때에 항상 베이스케이스(탈출조건)가 있어야하고, 재귀케이스는 베이스케이스를 향하는 방향으로 진행되어야 한다 예시에서는 n값이 1씩 감소하면서 베이스케이스n=1이라는 조건을 향하고 있다 출처 제목: 알고리즘 원리와 응용 저자: 국형준 출판사: 21세기사 [알고리즘] 알고리즘 분석(2) - 예제 [문제1] 나머지연산을 덧셈과 뺄셈만을 이용해서 실행하는 프로그램#include int mod(int num1, int num2) { while (num1 >= num2) { num1 = num1 - num2; } return num1; } void main() { int num1, num2; scanf("%d", &num1); scanf("%d", &num2); printf("%d", mod(num1, num2)); } [문제2] n x n 비트행렬(0과 1로 구성)에서 가장 많은 1을 포함하는 행을 찾는 프로그램 (n jmax) { row = i; jmax = j; } } return row; } void main() { int n; int matrix[100][100]; scanf("%d", &n).. [알고리즘] 알고리즘 분석(1) - 설명 알고리즘이란?? - 주어진 문제를 유한한 시간 내에 해결하는 단계적 절차이다 데이터구조란?? - 데이터를 조직하고 접근하는 체계적 방식이다 우리가 좋은 프로그램을 만들기 위해서는 첫째로 소요되는 "실행시간"을 줄이고, 둘째로 "기억장소 사용량"을 최소화해야 한다 실행시간은 대체로 입력의 크기와 함께 증가한다 입력의크기란 프로그램이 처리해야 하는 어떤 큰 수의 자릿수라던가, 처리해야 하는 데이터원소들의 개수 등을 말한다 실행시간에는 최선실행시간, 평균실행시간, 최악실행시간이 있다 최선실행시간 - 제일 운 좋은 경우의 성능 평균실행시간 - 알고리즘을 평균적인 입력으로 실행한 결과 최악실행시간 - 어떤 알고리즘이 입력에대한 출력을 얻기 위해 가장 오랜시간이 걸리는 경우(분석이 비교적 용이) 실행시간을 구하는 .. 이전 1 ··· 9 10 11 12 13 다음