본문 바로가기
728x90
반응형

IT204

1장 프로세스와 방법론 연습문제 1-1 소프트웨어에 대한 올바른 상식은? 4 소프트웨어 프로젝트의 요구 사항은 지속적으로 변경되지만 소프트웨어는 유연하기 때문에 변경을 반영하는 것이 쉽다. 프로그램을 실제 작동해 보기 전까지는 소프트웨어의 품질을 평가하는 것은 불가능하다. 소프트웨어 공학은 별로 필요 없는 많은 문서를 생성하게 하여 개발을 지연시킨다. 지체된 프로젝트에 인력을 뒤늦게 투입하는 것은 오히려 프로젝트의 일정을 더욱 지연 시킬 수 있다. 프로그램을 실제 작동해 보기 전까지는 소프트웨어의 품질을 평가하는 것은 불가능하다.지체된 프로젝트에 인력을 뒤늦게 투입하는 것은 오히려 프로젝트의 일정을 더욱 지연 시킬 수 있다. → 지연 됨. 소프트웨어 공학은 별로 필요 없는 많은 문서를 생성하게 하여 개발을 지연시킨다. 소프트웨어 프로젝.. 2023. 3. 1.
그래프의 응용 스패닝 트리 부속 그래프로 다음을 만족한다. connect가 필요하다 스패닝 트리 종류 깊이 우선 스패닝 트리 dfs 알고리즘을 사용하여 방문되어진 에지로 만들어진 스패닝 트리 너비 우선 스패닝 트리 bfs 알고리즘을 사용하여 방문 되어진 에지로 만들어진 스패닝 트리 최소 스패닝 트리 스패닝 트리에서 각 에지의 비용 값이 주어진다면 부여된 비용 값의 합을 최소로 하는 스패닝 트리를 구할 필요가 있다 가중치 그래프를 생각해야 한다 코드 while(T contains less than n—l edges && E is not empty) choose a least cost edge (v,w) from E; delete (v,w) from E; if((v,w) does not create a cycle in T.. 2023. 3. 1.
그래프 개념과 탐색 그래프 개념 오래된 그래프 문제로 다음과 koenigsberg 다리 문제가 있다. 임의의 한곳(A,B,C,D)에서 출발하여 a부터 f까지 “모든 다리를 한 번씩 건널 수 있는가? 하는 문제이다. 정의 그래프의 수학적 정의 그래프 : G(V,E)이고 V,E는 다음과 같다. V(G): 정점 E(G) : 간선, 정점을 연결하는 선, VXV의 부분집합 우방향 그래프 : 예를 들면 쌍방 통행이 가능한 도로의 지도이다. 정점을 연결하는 선에 방향이 없다 방향 그래프 : 예를 들면 일방 통행만 있는 도로의 지도이다 정점을 연결하는 선에 방향이 있다. 그래프의 예와 수학적인 표현 : 그래프를 표현하는 방법은 여러 가지이다. 아래 방법은 그림으로 그리는 그래프의 모습과 수학적인 기로호 표현하는 방법이다. 그래프에서의 제.. 2023. 3. 1.
검색 선형검색 선형 검색이란? 선형검색은 주어진 데이터에서 키 값에 의하여 데이터를 찾는 과정이다. 검색 방법 중 가장 단순하다. 선형검색 알고리즘 int sequential_search(int keys[], int find_key, int n) { int i=0; while(i searchnum ) right = middle - 1; else if ( list[middle]==searchnum ) return middle; } return —1 ; } 이진탐색 알고리즘-순환 int binsearch(int list[], int searchnum, int left, int right) {int middle; if(left5개->2개->1개 이므로 최악의 경우 4번 비교하게 된다. 11개의 데이터 데이터가 10.. 2023. 3. 1.
정렬 버블 정렬 버블정렬 : 버블 정렬은 정렬이 진행되는 모양이 비누거품과 같다고 하여 붙여진 이름이다. 나란히 있는 두개의 데이터를 계속하여 바꾸어 나간다. 전체 비교 횟수 : T(n)=n(n-1)/2 시간 복잡도 : O(n²) 알고리즘 list에 대한 기본 버블정렬 알고리즘 void bubble_sort(element list[], int n){ int i, j; element next; for (i=n-1;i>0;i--){ for(j=0;jlist[j+1]{ swap(list[j],list[j+1]}}}} 개선된 버블정렬 버블정렬 각 단계에서 데이터의 이동이 일어나지 않으면 다음 단계로 진행할 필요가 없다. 즉 중간과정에서 정렬이 끝나면 더 이상 비교와 교환이 필요없다. void bubble_sort(e.. 2023. 3. 1.
이진트리 이진트리 탐색 알고리즘 트리의 탐색은 트리의 각 노드를 방문하는 작업을 말한다. 👉 다음과 같은 방법들을 생각해 볼 수 있다. 레벨 순 : 레벨이 낮은 순으로 방문 왼쪽 트리 L→ A → 오른쪽 트리 R (중위 탐색) A→왼쪽 트리 L → 오른쪽 트리 R (전위 탐색) 왼쪽 트리 L → 오른쪽 트리 R → A (후위 탐색) 중위 탐색(inorder traversal) 왼쪽 트리 → 루트 노드 → 오른쪽 트리 순으로 방문 주의점 : 왼쪽 트리를 방문할 때 왼쪽 트리 자체가 트리이기 때문에 왼쪽 트리 안에서도 다시 중위 탐색을 한다. 왼쪽 트리로 간 다음 왼쪽 트리의 왼쪽 트리, 왼쪽 트리의 루트노드, 왼쪽 트리의 오른쪽 트리 순이 된다. 예시 1 중위 탐색을 하면 왼쪽 트리(B D E H 0, 루트(A),.. 2023. 3. 1.
728x90
반응형

티스토리툴바