*두* 스토어

*두*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

22개
전체 판매량

55개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

50%

전체자료 22개

일렬의 연속적으로 나열되어 있는 정수들로 이루어진 합의 값들 중 최대의 값을 지니는 찾는 프로그램을 작성하여라.

□ 문제정의일렬의 연속적으로 나열되어 있는 정수들로 이루어진 합의 값들 중 최대의 값을 지니는 찾는 프로그램을 작성하여라.1. 아래의 세 가지 알고리즘을 가지고 시간복잡도를 분석하시오방법 1) 모든 구간 i, j (i ≤ j) 에 대하여 구간 [i, j]의 정수들 ai, ..., aj의 합을 구하여 이들 합 중 최대값을 찾는다.방법 2) 모든 구간 i, j (i ≤ j)에 대하여 구간 [i, j]의 정수들 ai, ..., aj의 합을 구할 때, 구간 [i, j-1]의 합을 이용한다.방법 3) 모든 i에 대하여 i에서 끝나는 구간 중 합이 최대인 것을 구하여 S[i]에 저장한다.S[i] = S[i-1] + ai if S[i-1] > 0이면= ai 그렇지 않으면.2. 위의 각 방법을 구현한 후, 이를 다음의 각 n에 대하여 수행 시간을 측정하여 그래프로 나타내시오.N = 10, 100, 500, 1000, 2000, 5000, 10000, 20000□ 문제 해결방법 & 분석1. 방법 1 : 문제 정의에서 나타내는 첫 번째 알고리즘은 총 3개의 loop를 이용한다. 가장 상위에 있는 loop는 i부터 j까지 순차적으로 하나씩 증가한다. 그리고 그 하위에 있는 loop는 그 바로 위의 상위 loop처럼 i부터 j까지 순차적으로 하나씩 증가한다. 그리고 제일 하위에 있는 세 번째 loop는 첫 번째 loop가 가리키고 있는 수부터 두 번째 loop가 가리키고 있는 수까지 또 순차적으로 증가하면서 그에 해당하는 수(배열의 인덱스 값을 이용)를 계속 더해준다. 그래서 지금 더해서 나온 값이 현재 저장하고 있는 가장 큰 값보다 크다면 그 값을 대체시킨다.즉, 이 알고리즘을 사용하게 된다면 총 n(전체 나열되어 있는 수들의 개수)을 수행하는 loop가 3개가 존재하므로 전체적인 시간복잡도는 θ(n³) 이다.현재 이 알고리즘을 이용하여 문제정의 2의 입력된 값을 이용하여 수행시간 그래프를 그리면 다음과 같다.2. 방법 2 : 문제 정의에서 나타내는 두 번째 알고리즘은 총 2개의즘을 사용하게 된다면 총 n(전체 나열되어 있는 수들의 개수)을 수행하는 loop가 2개 이므로, 전체적인 시간복잡도는 θ(n²) 이다.현재 이 알고리즘을 이용하여 문제정의 2의 입력된 값을 이용하여 수행시간 그래프를 그리면 다음과 같다.3. 방법 3 : 문제 정의에서 나타내는 세 번째 알고리즘은 총 1개의 loop를 이용하여 문제에서 원하는 값을 구한다.전체 n개인 임시 배열을 한 개 만든다. 그런 후 그 배열을 문제에서 주어진 일렬의 수와 비교를 한다. 만약 예를 들어 -1 5 6 -9 6 2 이라는 수열이 있다고 가정해보자.첫 번째 배열에서 가장 큰 값을 가질 수 있는 것은 당연히 당연히 -1, 즉 바로 첫 번째 값이다. 임시의 배열의 두 번째에 들어갈 수 있는 가장 큰 값을 5 이거나, -1 + 5인 4일 것이다. 하지만 5가 4보다 큰 값이므로 당연히 5가 저장이 된다.임시의 배열에서 세 번째에 들어갈 수 있는 값은 6이거나 5+6일 것이다. 당연히 여기에서도 만찬 가지로 5+6이 6보다 큰 값이므로 5+6이 저장이 된다. 이런 방법으로 계속 수행하다 보면 다음과 같은 공통적인 공식이 나온다.지금 내가 가리키고 있는 값이 가장 큰 지는 전의 값을 보면 알 수 있는 것이다. 전의 값이 음수라면 당연히 현재 나 자신의 값이 가장 큰 값이 되는 것이고, 만약 양수라면 현재 나 자신의 값 + 전의 값을 해주는 것이 큰 값이 나 올 것이다.즉, 이 알고리즘을 사용하게 된다면 한 개의 loop를 사용하게 되므로 전체적인 시간복잡도는 θ(n) 가 되는 것이다.현재 이 알고리즘을 이용하여 문제정의 2의 입력된 값을 이용하여 수행시간 그래프를 그리면 다음과 같다.4. 3개 알고리즘의 비교(단위 : sec)비 고1 case2 case3 case4 case5 case6 case알고리즘 10.00040.00040.00040.00040.00040.019알고리즘 20.00020.00020.00020.00020.00020.0004알고리즘 30.00130.00130.00130.0번Test case 7번Test case 8번Test case 9번Test case 10번Test case 11번Test case 12번□ 결 론처음에는 알고 있는 Language가 C++뿐이어서 소스코드를 C++ 로 하려고 마음을 먹었었다. 하지만 어차피 지금 Java를 공부하고 있던 중이라, 알고리즘을 Java로 프로그래밍했다. 처음 접하는 Language인 만큼 걸림돌이 많았다. 한 이틀 동안은 계속 파일 스트림에 대해서만 공부하였다. 왜냐하면 C++와 달리 Java에서는 서로 다른 Type에 대입을 하려면 Casting을 해야 되기 때문이다. 즉, 이 말은 파일에서 입력을 받을 경우 int와 string을 모두 구분을 시켜야 하기 때문이다.(C++에서는 단순히 >> 로 모든게 이루어진다) 아무튼 이번 과제로 Java에 대해서도 많이 공부할 수 있었다.이번 과제를 통해 한 문제를 가지고 여러 개의 알고리즘을 사용하여 시간복잡도를 구하고 소요되는 시간을 측정하여 그래프를 그려보았다. 결과는 위에서 그래프를 보았듯이 시간복잡도가 n³ 일 경우 20000개의 테스트 케이스가 들어올 경우 엄청난 소요시간을 보였다.(컴퓨터에서 2시간 가량의 연산은 엄청 오래 걸리는 것이다)위에서 알 수 있듯이 어떤 문제를 풀기 위해서는 가장 적절한 알고리즘을 구하는 것이 가장 중요하다. 왜냐하면 같은 문제를 풀더라고 빠르게 연산하고 정확한 결과 값을 구하는 것이 가장 효율적이기 때문이다.□ 소스 코드Max_sum_main . JAVA (메인메소드가 있는 클래스)import java.io.*;import java.util.*;public class Max_sum_main {/*** @param args* @throws FileNotFoundException*/public static void main(String[] args) throws FileNotFoundException {int[] data = new int[20000];int i = 0;int cases = 0; // cMax_sum_type1 type1 = new Max_sum_type1(i,data);System.out.println("First Algorithm ----------");System.out.print("Maxsum is : ");System.out.println(type1.calcul());System.out.printf("%s%.9fnn","Time is : ",(double)(System.nanoTime()-before_time)/Math.pow(10.0,9));}else if(cases == 1) // the second algorithm{before_time = System.nanoTime();Max_sum_type2 type2 = new Max_sum_type2(i,data);System.out.println("Second Algorithm ----------");System.out.print("Maxsum is : ");System.out.println(type2.calcul());System.out.printf("%s%.9fnn","Time is : ",(double)(System.nanoTime()-before_time)/Math.pow(10.0,9));}else // the third algorithm{before_time = System.nanoTime();Max_sum_type3 type3 = new Max_sum_type3(i,data);System.out.println("Third Algorithm ----------");System.out.print("Maxsum is : ");type3.calcul();System.out.println(type3.whatMax());System.out.printf("%s%.9fnn","Time is : ",(double)(System.nanoTime()-before_time)/Math.pow(10.0,9));}cases++;fIn.close();}}}Max_sum_type1 . JAVAi){for(int j = i ; j < number ; ++j){sum = 0;for(int k = i ; k maxsum)maxsum = sum;}}return maxsum;}private int[] data = new int[20000];private int number;}Max_sum_type2 . JAVA (알고리즘 2을 수행하는 클래스)public class Max_sum_type2 {public Max_sum_type2(int n, int[] datas){number = n;for(int i = 0 ; i < number ; ++i){data[i] = datas[i];}}public int calcul(){int maxsum = data[0];int sum = 0;for(int i = 0 ; i < number ; ++i){sum = data[i];if(i != number - 1) // when i point the last of elemnet of array{for(int j = i+1 ; j < number ; ++j){if(sum > maxsum)maxsum = sum;sum += data[j];}}if(sum > maxsum)maxsum = sum;}return maxsum;}private int[] data = new int[20000];private int number;}Max_sum_type3 . JAVA (알고리즘 3을 수행하는 클래스)public class Max_sum_type3 {public Max_sum_type3(int n , int[] datas){number = n;for(int i = 0 ; i < number ; ++i)data[i] = datas[i];}public void calcul(){for(int i = 0 ; i < number ; ++i){if(i > 0){if(temp[i-1] < 0){temp[i] = data[i];}elsetemp[i] = temp[i-1] + data[i];}else{temp[er;}

공학/기술| 2007.04.20| 14페이지| 1,000원| 조회(343)

JAVA, 알고리즘, 순차적, Loop

미리보기

닫기
라우터 망에서 각 라우터의 경로설정표를 구하는 프로그램을 작성하시오.

□ 문제정의n개의 라우터들과 이들을 연결하는 망이 있다. 그리고 두 라우터를 연결하는 각 통신링크에 대하여 단위 패킷을 보내는데 걸리는 시간이 주어진다. 이 라우터 망에서 각 라우터의 경로설정표를 구하는 프로그램을 작성하시오.□ 문제 해결방법1. 파일로부터 정점의 개수와 정점들 사이의 에지의 가중치를 입력을 받는다.정점들은 번호대신 문자열로 들어오기 때문에 문자열을 이에 해당하는 인덱스값으로 바꾸어주어야 한다. 또한 마지막 우리가 원하는 값을 출력 시 해당하는 인덱스를 이에 해당하는 문자열로 바꾸어야 하기 때문에 문자열을 저장할 수 있는 하나의 문자열 배열을 하나 생성한다.만약에 그 문자열 배열에 지금 들어온 라우터 이름이 존재 하지 않다면 그 배열에 순차적 뒤에 넣고, 존재 한다면 그냥 넣어간다. 그래서 각 문자열마다 고유의 인덱스값을 가지게 된다.들어온 라우터 이름을 고유의 인덱스 값으로 변경 후 그 인덱스 값을 이용하여 각 해당하는 링크드 리스트에 연결된 정점들은 추가(가중치도 포함)한다.무방향 그래프이므로 파일로 들어온 두 정점 모두 링크드 리스트로 연결한다.예를 들어 A B 2 가 들어왔다고 가정하고 또한 A의 해당하는 번호 0이고, B의 해당하는 번호 1이라고 가정해보면 1번의 링크드 리스트에 2번의 정점을 연결하고, 2번 역시 1번의 정점을 연결한다. 이로서 정점들과 에지의 가중치를 링크드 리스트로 구현할 수 있다.그리고 이제 출력을 해야하는 라우터 이름을 출력을 받는데 이것 역시 문자열을 고유의 인덱스 번호로 바꾸어 새로운 배열에 저장 후 각각의 고유의 번호를 이용하여 최단의 경로를 찾는 함수에 인자로 보내준다.2. 출력을 원하는 라우터 이름을 파일로부터 입력을 받으면 그에 해당하는 인덱스 값을 얻어서 다이스트라 알고리즘을 이용한 최단 경로를 찾는 함수에 보낸다.3. 최단 경로를 찾는 함수2번에서 인자로 받는 인덱스 값이 이제 최단 경로를 찾을 때 source가 된다.3-1. dist, state, parent 배열을 만든다.dist : sour9 r19 1r18 r18 3r8 r8 1r12 r12 2r9 r5 3r13 r5 3r17 r2 6r16 r2 8r6 r2 6r7 r2 7r10 r2 8r14 r2 8r11 r2 8r15 r2 9r20 - 0r21 - 0r20 - 0r1 - 0r2 - 0r3 - 0r4 - 0r5 - 0r19 - 0r18 - 0r8 - 0r12 - 0r9 - 0r13 - 0r17 - 0r16 - 0r6 - 0r7 - 0r10 - 0r14 - 0r11 - 0r15 - 0r21 r21 2#3Answer #1Answer #2Answer #3r4 - 0r1 r1 2r2 r2 1r5 r1 3r3 r3 2r7 r7 3r6 r6 3r13 r1 4r8 r6 5r12 r7 4r9 r1 5r10 r6 6r11 r7 6r14 - 0r15 - 0r16 - 0r8 - 0r1 r13 4r2 r13 5r4 r6 5r5 r13 3r3 r6 5r7 r6 4r6 r6 2r13 r13 2r12 r12 4r9 r10 2r10 r10 1r11 r10 4r14 - 0r15 - 0r16 - 0r15 - 0r1 - 0r2 - 0r4 - 0r5 - 0r3 - 0r7 - 0r6 - 0r13 - 0r8 - 0r12 - 0r9 - 0r10 - 0r11 - 0r14 r14 1r16 r16 1#4Answer #1Answer #2Answer #3Answer #4r3 - 0r1 r2 2r2 r2 1r6 r2 3r14 r14 3r4 r4 1r12 r12 2r7 r7 1r9 r11 2r11 r11 1r13 r13 2r5 r4 2r8 r11 3r10 r7 2r6 - 0r1 r1 1r2 r2 2r14 r14 1r3 r2 3r4 r2 3r12 r2 3r7 r2 4r9 r11 4r11 r11 3r13 r2 5r5 r5 2r8 r11 5r10 r11 5r10 - 0r1 r7 4r2 r7 3r6 r11 5r14 r7 5r3 r7 2r4 r7 3r12 r7 2r7 r7 1r9 r9 2r11 r11 2r13 r13 2r5 r7 4r8 r8 1r11 -r3 4r3 r3 1r9 r3 2r12 r3 3r13 r3 3r4 r4 1r6 r4 4r7 r4 2r8 r4 4r18 r4 6r10 r3 3r11 r3 4r15 r3 6r14 r3 4r16 r3 9r17 r3 8r25 r4 9r26 r4 11r28 r4 13r19 r4 7r21 r4 7r20 r4 9r22 r4 8r23 r4 9r24 r4 10r27 r4 12r16 - 0r1 r17 11r2 r17 9r3 r17 8r5 r17 9r9 r17 7r12 r17 10r13 r17 10r4 r25 9r6 r25 7r7 r25 8r8 r25 6r18 r25 4r10 r17 7r11 r17 5r15 r17 3r14 r17 11r17 r17 1r25 r25 1r26 r26 3r28 r28 5r19 r25 3r21 r25 5r20 r25 5r22 r25 2r23 r25 7r24 r25 3r27 r25 4r25 - 0r1 r22 11r2 r15 10r3 r15 9r5 r22 9r9 r15 8r12 r15 11r13 r15 11r4 r22 8r6 r22 6r7 r22 7r8 r22 5r18 r22 3r10 r15 8r11 r15 6r15 r15 4r14 r15 12r16 r16 1r17 r16 2r26 r26 2r28 r27 4r19 r22 2r21 r22 4r20 r22 4r22 r22 1r23 r22 6r24 r24 2r27 r27 3#10Answer #1Answer #2Answer #3Answer #4Answer #5r2 - 0r1 r1 2r3 r1 3r17 r1 3r4 r4 4r18 r19 2r19 r19 1r21 r21 1r5 r1 4r6 r21 3r29 r1 6r7 r21 5r8 r21 4r23 r19 2r9 r19 5r28 r21 6r10 r19 3r11 r19 6r27 r19 7r22 r19 3r12 r19 4r26 r19 8r13 r21 6r14 r21 5r25 r21 8r15 r19 5r16 r19 4r20 r21 2r24 r19 6r9 - 0r1 r7 6r2e;}2. FindingPath.JAVApublic class FindingPath {public FindingPath(ArrayNode arrayNode1,int num){aNode = arrayNode1;this.num = num;}/*** 다이스트라 알고리즘을 이용하여 최단 경로 찾는 메소드* @param start 시작정점*/public int[][] setAnswers(int start){int[] dist = new int[num]; //source로 부터의 거리int[] state = new int[num]; //tree,fringe,unseenint[] parent = new int[num]; //source의 넥스트 값을 저장하는 변수int startPoint = start; //source를 저장for(int i = 0 ; i < num ; ++i)//모두 -1로 만들어서 나중에 값이 -1이라면 그것은 source이다.{parent[i] = -1;}int[][] answer = new int[num][3];NodeList nltmp = aNode.getNodeList(start); //시작정점에 해당하는 링크드리스트boolean change = true; //다이스트라 알고리즘 사용중 루프를 빠져나오기 위해while(change){state[start] = 2;//상태를 tree로 만듦for(int i = 0 ; i < nltmp.getSize() ; ++i) //링크드리스트 크기만큼 루프{Node nodeTmp = nltmp.getNode(i); //순차적으로 노드들을 가지고 온다.if(state[nodeTmp.getVertex()] != 2) //만약 트리가 아니라면{//source로 부터 거리가 0이라면(처음접근하는것)if(dist[nodeTmp.getVertex()] == 0){dist[nodeTmp.getVertex()] = dist[start] + nodeTmp.getheight();if(start == startPoint)pareA/*** 문자열을 고유의 번호와 매칭하는 클래스* @author NO. : 200300372 Name : 김두원*/public class StringToInt {public StringToInt(int num){vName = new String[num];size = 0;}/*** 문자열을 넣으면 순차적으로 넣는다.* @param name*/public void setIndex(String name){vName[size] = name;size++;}/*** 문자열을 입력받으면 고유의 인덱스 값을 return* @param name* @return 문자열에 해당하는 고유의 인덱스 값*/public int findIndex(String name){if(vName.length >= 1) //문자열이 하나이상 있을 때{for(int i = 0 ; i < vName.length ; ++i){if(vName[i] != null)if(vName[i].equals(name)){return i;}}}return -1; //못 찾을 시 -1을 반환}/*** 인덱스 값을 넣으시 해당하는 문자열 반환* @param i* @return*/public String findName(int i){return vName[i];}private String[] vName; //문자열 저장하는 변수private int size;}6. TestAlgo5.JAVAimport java.io.File;import java.io.FileNotFoundException;import java.util.*;public class TestAlgo5 {public static void main(String[] args) throws FileNotFoundException {// TODO Auto-generated method stubint numOfrouter;int numOfprint;int numOfrink;Scanner fIn = new Scanner(new File("MyText.txt"));String }}}}

공학/기술| 2007.04.20| 22페이지| 1,000원| 조회(271)

JAVA, 알고리즘, 라우터, 배열, 문자열

미리보기

닫기
스파르타의 교육의 한계점

스파르타의 교육의 한계점서 론요즘 현대기아자동차에서 신입사원들을 스파르타식으로 교육한다는 것이 한 일간지신문에 실리면서 화제가 되었다. 그 교육 방식에 대해서 잠시 간략히 알아보면 이 연수기간동안 연수생들은 집 생각을 절대 할 수 없게 만들고 또한 지난해까지만 해도 매주 주말 외박이 허용됐으나 이번에는 5주 동안 단 한 차례만 외박을 나갈 수 있게 만들어서 연수생으로 하여금 강도가 심한 교육을 시키고 있다.현대기아자동차와 같은 신입사원 연수프로그램 뿐만 아니라 대학에서도 위의 유사한 교육방식을 채택하고 있다. 상하이에 있는 한 차이나 · 유럽 인터내셔널 비즈니스 스쿨 역시 스파르타 교육방식을 채택을 하면서 아시아 MBA명문대학으로 도약하려고 한다. 예를 들어 C를 두 번 맞으면 자동으로 퇴학을 당하는 등 고강도 교육방식을 이용하고 있다.그리고 또한 스파르타식 학습법을 도입한 학원이 인기를 끌고 있다고 한다. 그런 학원들은 학생들의 성적을 단기간에 향상시켜주어 학부모들 사이에서 선풍적인 인기를 끌고 있다고 한다.이와 같이 현재 많은 기업, 학교, 학원 등에서는 다시 스파르타식 교육 방식이 각광을 받고 있는데, 이런 스파르타 교육방식이 어떤 한계점이 있는지에 대해서 자세히 알아보자.본 론1. 스파르타 교육이란?)다들 스파르타 교육이라고 들으면 다들 고강도의 교육을 생각한다. 즉, 군사적 목적을 둔 교육 방식을 사용하였기 때문이다. 그렇다면 왜? 군사적 목적을 둔 교육 방식을 채택하였을까? 그 정답은 바로 스파르타라는 역사와 지리를 보면 알 수 있다.스파르타라는 나라는 BC 12C경 도리아족이 라케라이모니아에 세운 국가이다. 라케라이모니아라는 지형은 험준한 산악지대에 위치해 있었기 때문에 농토를 확보하기가 어려웠다. 그래서 결국 다른 국가의 영토 정복을 위해서 끊임없이 전쟁을 치러야만 했고, 정복한 나라를 다스리는 것 역시 뭔가 강력한 힘이 필요로 하였다. 그리고 또한 사회적 내부 역시 극소수의 귀족과 그에 30배에 달하는 평민과 노예로 구성되어 있었다. 당연히 노예들의 잦은 반란이 있었을 것이고, 이를 통제하기 위해서는 위에서 언급한 뭔가 강력한 힘이 필요로 하였다. 이러한 상황에서 스파르타라는 국가에서는 가장 적합한 국가체제를 강력한 군국주의 국가체제로서 일종의 군대식 국가로 선택할 수밖에 없었을 것이다.이러한 국가체제를 유지하기 위해서 사용된 가장 효과적인 방법은 바로 교육을 이용하는 것이다. 즉, 자라라는 아이들로 하여금 국가에 대한 충성심과 복종력 그리고 전쟁에 나가서도 물러서지 않고 끝까지 싸울 수 있는 강인 힘, 인내력, 용기 등을 가지게 만들게 하였다. 이러한 교육적 방법은 자기의 희생을 통하여 국가에게 봉사하는 인간을 양성을 목적을 두고 하였다.여기서 주목할 부분은 여성교육인데, 그 당시 여성을 하나의 인격체로 보기보다는 강인한 전사를 분만하도록 하기 위해 신체를 건강하게 단련하였다. 즉, 여자역시 남자들과는 방법이 다르지만은 그래도 목적만은 동일하다는 것을 알 수 있다.2. 스파르타 교육의 한계점위에서 언급했듯이 스파르타라는 국가에서는 나라의 체제를 유지하기 위해 교육을 가장 최선의 선택 방안으로 선택하였다. 마치 현재의 북한에서 공산주의 체제를 유지하기 위해 교육을 이용하는 것과 마찬가지로 말이다. 저번에 수업시간에 교수님이 보여주신 북한의 교과서를 통해 나는 정치를 위해 교육을 이용한 다는 것을 다시 한 번 일깨워주었다. 초등학교학생들에게 “미국을 때려잡자“, “위대한 수령님을 찬양하자“, 그리고 수학에서는 북한의 탱크 한 대가 미국탱크 5대를 부실 수 있을 때, 미국탱크 10대와 북한의 탱크3대가 결전에서 누가 이길 것인가. 그리고 북한의 탱크가 몇 대가 남을 것인가에 대해서 언급을 하는 등 우리의 정서에는 도저히 맞지 않는 그런 교육을 정치를 위해 이용을 하고 있다.이러한 통일된 교육 즉, 획일 된 교육을 통해 교육을 받는 학생들은 자신을 스스로 생각을 하지 못하게 되고, 또한 내가 왜 공부를 해야 되는 지를 가지게 되는 목적의식이 없어지게 된다. 이러한 문제는 다들 중학교, 고등학교를 다녔다면 느꼈을 것이다.개개인의 개성보다는 전체를 중시하는 이러한 교육풍토는 위에서 말한 북한, 스파르타뿐만 아니라, 우리나라 교육실정 또한 이러하다는 것을 알아야 할 것이다.우리는 눈에 쉽게 보이는 결과물에 너무 현혹을 잘한다. 예를 들어 한 학원의 광고지를 보면, 우리학원 학생들은 전교 10등 안에 드는 사람이 몇 명이라면서 그것이 마치 자랑인 듯이 광고를 하고 있다. 그 안에 전교 10등 안에 들어간 사람보다는 안 들어간 사람이 더 많을 것이고, 그 학원에서 적응을 못하고 심지어 더 성적이 떨어진 학생들도 있을 텐데 말이다. 내가 여기서 하고 싶은 말은 우리는 쉽게 접할 수 있는 결과물에만 충실한 편의주의에 빠져있는 것이다.

교육학| 2007.04.20| 3페이지| 1,000원| 조회(341)

교육, 교육학, 스파르타

미리보기

닫기
[공학]전치그래프,

□ 문제정의n개의 task들로 구성된 프로젝트가 있다. 이들 task를 수행하는데 걸리는 시간이 주어지고, 또한 이들 task 사이의 선후관계가 주어진다.1) 이때, 이 프로젝트의 task들을 선후관계를 만족하면서 모든 task들을 순서대로 수행하려고 한다. 이를 만족하는 task들의 수행 순서들 중 하나를 출력하라. 만약 이러한 순서가 존재하지 않으면 “수행순서가 존재하지 않음”을 출력한다.2) 임계경로(임의의 하나)를 구하고, 이 프로젝트를 완료하는데 걸리는 최단시간을 출력하라.□ 문제 해결방법1. 테스트 케이스는 전체적으로 3부분으로 나누어지는데, 첫 번째는 일의 개수고, 두 번째는 순차적으로 일들의 수행시간이다. 마지막으로 세 번째는 각 일들간의 선후관계이다. 이것을 메모리에 저장을 하게 되는데, 두 번째 부분인 일들의 수행시간은 time 이라는 배열에 저장을 한다. 그리고, 선후관계는 Linked List를 이용하여 표현한다. 하지만 우리가 사용할 것은 전치그래프이므로 들어오는 값을 반대로 한다.While(true){fin >> tmp1 >> tmp2;if(fin.fail())break;ptr = new NodeType;ptr->vertex = tmp1;ptr->link = adjV[tmp2];adjV[tmp2] = ptr;ptr2 = new NodeType;ptr2->vertex = tmp2;ptr2->link = adjV2[tmp1];adjV2[tmp1] = ptr2;}예를 들어 9의 값과 1의 값이 들어온다면 선후관계는 9 1이 된다. 하지만 우리는 전치그래프를 이용할 것이므로 9의 값과 1의 값이 들어온다면 선후관계는 1 9이 된다. 즉, 반대로 된다는 것이다.이런 식으로 전치그래프를 만든다.2. 전치그래프에서 시작하는 시작정점은 원래 그래프의 맨 마지막의 값이다. 이 말은 원래 그래프에서 null의 값을 가지고 있는 노드를 찾으면 되는 것이다. 그래서 위에서 소스와 마찬가지로 원래 그래프를 하나 더 생성하여 null의 값을 가지고 있는 시작 정점을 찾는다.3. 이번 알고리즘은 dfs를 이용하여 풀게 된다. 시작정점을 dfs라는 함수에 보내주면서 이번 문제는 풀기 시작한다.4. dfs이라는 함수에서는 방문한 정점의 색깔을 gray로 바꾸고, 지금 방문한 정점을 이용하여 LinkedList를 따라가면서 정점을 찾는데, 만약 방문하지 않았다면(색깔이 흰색) 재귀적으로 dfs함수를 다시 호출하게 된다.5. 풀고자 하는 1번 문제는 task의 임의의 수행순서를 하나 출력을 하기 위해서는 역위상 순서를 구해야 한다. 그래서 dfs함수에 topo라는 배열을 하나 더 생성한다. topo배열은 dfs함수를 재귀적으로 돌고 다시 돌아올 때 topNum(초기값 0)이라는 변수를 하나 증가하면서 해당하는 topo배열에 topNum을 저장한다. 결국 전치 그래프에서 역위상 순서를 구하면 DAG G 에서 위상순서를 구하는 것과 마찬가지이라는 것을 알 수 있다. 만약 시작정점이 여러 곳일 경우에는 각 해당하는 시작정점을 모두 dfs함수의 시작정점을 넣어야 한다.그러나 만약 싸이클이 존재한다면(back edge가 있다면) 이 그래프는 위상 순서가 없는 것이다. 그러기 위해서는 이 그래프에 싸이클이 있는 지 없는 지를 판단하여야 하는데 그것은 dfsNum이라는 배열을 통해 dfs 재귀적으로 돌면서 방문했던 정점들은 기록하게 된다. 어떤 정점보다 나중에 방문한 정점이 있다면 그 정점의 dfsNum의 값은 전에 방문했던 dfsNum값보다 큰 것을 이용하여 back edge를 구하면 된다.6. 2번 문제는 임계 경로와 프로젝트를 완료하는데 걸리는 최단시간을 구하는 것인데, 이 문제도 동일하게 dfs함수를 이용하여 푼다. 어떤 정점에서 시작을 할 때 est는 0으로 초기화를 하고 해당하는 정점의 전순서 처리를 하는 critDep 배열은 -1로 초기화를 한다. 그런 후 해당하는 정점의 eft[w]가 전 정점의 est(v)보다 크다면 est(v)에 eft[w]의 값을 넣는다. 그런 후 critDep[v]에 현재 정점의 값(w)을 넣어준다. 그래서 해당하는 eft의 값은 est 와 해당정점이 수행되는 시간의 값을 더하여 계산한다.프로젝트 완료하는 최단시간은 전치 그래프에서의 시작정점의 eft이다. 결국 여러 개의 시작정점이 나올 경우 각 정점의 값들 중 가장 큰 값을 이용하면 우리가 원하는 값을 구할 수 있다.임계 경로는 위에서 구한 critDep를 이용하여 구할 수 있다. 즉, 시작 정점이 오기 전의 정점을 이용한다.예를 들어 밑의 표와 같은 값이 있다고 가정해보자.1234-1421시작정점은 3이라면 3이라는 정점에 오기 위해서는 4의 정점을 거치게 되는 것이고 4의 정점은 1의 정점을 통해 들어는 것이다. 1은 -1(초기값)의 값을 가지고 있으므로 맨 처음 시작되는 정점을 말한다. 결국 1 4 2 3 이라는 임계 경로가 생기는 것이다.□ 수행결과#1#2#3#4#5#6#7#8#9#10#11#12#13#14#15□ 결 론이번 과제는 전체적으로 DFS 이라는 알고리즘을 이용하여 문제를 해결하였다.처음에 DFS함수에 시작정점을 찾아 보내야 하는데, 어떻게 찾을 방법을 구상하던 중 생각해낸 것이 바로 DAG G의 마지막 정점이 전치 그래프에서의 시작 정점이라는 것이다. 그래서 시작 정점을 구하기 위해서 DAG G 와 전치 그래프 두 개를 생성하였다.그리고 생각하지 못했던 것이 바로 여러 개의 시작정점들이었다. 하나의 시작 정점만을 생각했었는데, 테스트 케이스 3번부터는 여러 개의 시작 정점이 있다는 것을 알 수 있었다. 그래서 시작정점의 개수만큼이나 loop를 돌아 원하는 값을 구한다. Loop를 돌 때 마다 나오는 eft의 값을 비교하면서 우리가 원하는 프로젝트 완료하는 최단 시간을 구할 수 있다.이 2개의 정도의 예외를 처리하는 것이 가장 어려웠다.이번 과제를 통해 임계 경로, 위상 정렬을 더욱 더 잘 알 수 있는 계기가 되었다.□ 소스 코드#include #include using namespace std;struct NodeType{int vertex;NodeType *link;};enum colorType{white, gray, black};int critDep[1000]; //지나온 경로 저장double eft[1000]; //조기종료시간bool isCycle = false; //싸이클 있는지 없는 지 판단.void dfs(NodeType** adjV, colorType color[], int v, int topo[], int& topNum, int dfsNum[], int& dfsNumber, double time[]){int w;NodeType* ptr;color[v] = gray; //방문했다는 표시dfsNum[v] = ++dfsNumber; //double est = 0.0;critDep[v] = -1;ptr = adjV[v];while(ptr != NULL){w = ptr->vertex;if(color[w] == white){dfs(adjV, color, w ,topo,topNum,dfsNum,dfsNumber,time);if(eft[w] >= est){est = eft[w];critDep[v] = w;}}else{if(dfsNum[v] > dfsNum[w]) //싸이클 있을 경우if(color[w] == gray)isCycle = true;if(eft[w] >= est){est = eft[w];critDep[v] = w;}}ptr = ptr->link;}topo[v] = ++topNum;eft[v] = est + time[v];color[v] = black;}//위상 순서 출력하는 함수// v는 1부터 순차적으로 증가하면서 num 까지void printOrder(int v, int topo[], int num){//모든 정점을 확인해하므로 v != num + 1 이다.while(v != num + 1){//해당하는 v의 값을 찾기 위해 모든 정점을 찾는다.for(int i = 1 ; i

공학/기술| 2007.04.20| 10페이지| 1,000원| 조회(207)

JAVA, 알고리즘, 그래프, 전치, adjV

미리보기

닫기
고교 평준화체제 어떻게 해야 하나

고교 평준화체제,어떻게 해야 하나.서 론고교 평준화 제도는 1970년대, 1980년대에는 상당한 성과를 거뒀다. 국가와 학교와 교육 내용과 평가 등을 표준화하여 국가의 교육의 질을 전체적으로 높이고자 하였다. 그래서 국가적 표준화를 통해 양질의 교육이 값싸고 신속하게 보급될 수 있었다. 게다가 경제사정이 중하위층 학생들의 학력을 끌어올려 학력 신장에도 기여했다. 평준화는 이처럼 산업화시대, 소품종 대량생산시대에는 나름의 역할을 훌륭히 수행해왔다.하지만 예전과 달리 1990년대 들어오면서 우리나라 사회는 많은 변화를 겪게 되었다. 개인보다는 단체를 중시여기는 산업주의 사회에서 단체보다는 개개인을 중시하는 지식기반사회로 변화하기 시작하였다. 이로 인해 교육을 표준화시켜 교육시키는 것이 이제 더 이상 시대 흐름과 맞지 않게 되었다.게다가 얼마 전 김신일 부총리겸 교육인적자원부 장관이 취임을 하면서 현재 논란이 되고 있는 고교평준화 정책에 대해서 계속 지속적으로 유지할 것이라고 하였다. 이로 인해 고교 평준화 제도에 대해서 서로 입장차를 다르게 가지고 있는 찬성론자와 반대론자들 사이의 논쟁이 더욱 거세졌다.고교 평준화란 정확히 무엇이며, 고교 평준화를 바라보는 다양한 시각을 알아보고 만약 문제가 존재하다면 어떻게 이 문제를 개선을 할 것인가에 대해서 자세히 알아보자.본 론1. 고교평준화란? (도입배경, 의미, 현황, 역사)1-1. 도입배경1959년 시작된 초등교육 의무화까지 거슬러 올라가게 되면, 초등교육이 의무화되면서 취학인구가 폭발적으로 늘어났고 이는 중학교 진학 열기로 이어졌으나 교육기회가 제한돼 중학교 입시경쟁이 치열해지면서 나타난 과외과열 등 부작용을 해결하기 위해 1969년 중학교 무시험제가 실시되었다. 이 제도가 실시된 이후 중학교 입시과열은 가라앉았다 하지만 당시 모든 중학교에서는 명문 고등학교 진학을 가장 큰 목표로 삼고 학생들은 가르쳤다. 결국 중학교 입시과열이 없어지는 대신 고등학교 입시과열이 더욱 심해지게 된 것이다. 이로 인해 중3학생들은 과중한 학습노동과 합격에 대한 부담감으로 인해 지금의 고3병와 같은 중3병 당시 존재하기도 하였다.이런 신체적, 정신적 문제뿐만 아니라, 교육적, 사회적 문제가 또한 존재하였다. 암기 위주의 주입식 교육, 고등학교 간의 심한 학력격차, 고입 재수생 양산으로 사교육비 증가, 청소년 비행, 학생 인구의 도시집중 현상 등 이런 문제들은 해결하고자 1973년 입시제도 연구위원회의 제안으로 서울과 부산에서 1974년 시행되었다. 올해로 시행 32년째를 맞이하고 있다. 이 연구위원회에서 제시한 보고서에서는 인문 고등학교의 경우 고등학교 학군을 설정하고, 연합고사에 의하여, 입학자격자를 선발한 후, 추첨으로 학생을 학교에 배정하되, 후기에 실시하고 실업고등학교의 경우에는 시를 하나의 단위로 하여 학교를 임의 지원하게 하고, 연합고사 성적 및 체력장 성적에 의거하여 학생을 학교별로 선발하되, 전기에 실시할 것을 제안하고 있다.1-2. 의 미종전의 학력고사로 고등학교에 입학하는 것과는 달리, 학력고사를 폐지하고 추첨식으로 입학하는 것이다. 그런 점에서 엘리트 중심의 교육(elitism)에서 교육기회의 평등을 우선시 하는 대중주의에 그 정책이념의 토대를 두고 있다.1-3. 시행과정 및 현황1981년까지 꾸준히 평준화제도 적용지역이 확대되어 21개 지역에 이르게 되었는데, 평준화의 전제 조건이 되는 교원, 시설, 교육의 질 등을 위한 재정적, 행정적 지원이 미흡한 나머지, 대부분을 차지하던 사립학교에 대한 정부 지원이 한계에 이르자 학교간 격차가 심화되었고 평준화 지역에 새로운 명문, 일류 고교가 탄생하여 더욱 치열한 입시 경쟁이 생겨났다. 이에 일부 지역이 평준화를 해제하였지만, 2000년부터 다시 평준화 지역을 확대시켜 2002년까지 22개 지역에 고교평준화 제도를 적용하고 있다. 이후에도 여러 가지 문제점과 비판이 잇달았으나 교육 기회의 평등, 입시 경쟁의 완화 등을 이유로 정부는 완강히 이 제도를 보완, 유지하겠다고 주장하는 가운데, 자립형 사립고 유치가 그 대안으로 등장한 것이다.위의 표를 보면 2003년 기준으로 서울특별시와 6대 광역시, 제주도에서 고교 평준화 정책을 전면 실시하고 있고, 경기도, 충청북도, 전라북도, 경상남도에서 부분적으로 실시하고 있으며, 강원도, 충청남도, 전라남도, 경상북도에서는 고교 평준화 정책을 실시하지 않음을 알 수 있다.2. 성 과고교 평준화 정책이 우리 교육에 미친 영향은 다음과 같이 3가지로 나누어 볼 수 있다.첫째, 중학교 교육을 정상화를 하였다는 점이다. 위에서 언급하였듯이 당시에 가장 사회적 문제였던 고등학교 입시 위주 교육에 따른 중학교 교육을 폐해를 일시에 해결할 수 있었다. 이런 영향으로 중학생의 입시 부담을 크게 경감되었고 전인적인 발달 촉진에 크나큰 영향을 주었다.둘째, 교육기회를 확대를 하였다는 점이다. 사실 고교평준화 정책이 자유주의보다는 평등주의의 이념을 더 앞세우기 때문에 모두다 고등학교에 진학을 할 수 있게 만들었다. 그래서 그 당시 고교 평준화 실시 직전에 20%대에 불과했던 고등학교 취학률이 시행 바로 직후 40%대로 확대되었고, 현재 거의 100%를 이르게 되었다.셋째, 고등학교 간의 차이를 어느 정도 줄였다는 점이다. 고교 평준화 정책이 수행하기 전에는 고등학교가 지금의 대학과 마찬가지로 그 사람의 간판이 될 정도였을 정도였다. 그러나 이 정책이 시행 이후에는 선발시험 방식에서 추첨방식으로 전환시킴으로써 고등학교 간 학생의 질을 같게 만들어 고등학교가 모두 같은 고등학교로 만들었다. 그리고 학생의 질뿐만 아니라 학교의 시설과 인적 구성을 평준화하는 방향으로 추진함으로써 외형적인 모습 역시 평준화를 이루었다.3. 한계와 과제위에서 성과만을 보게 되면 긍정적으로 평가를 받을 것만 같은 고교평준화 정책에 대한 비판 역시 끊임없이 이어지고 있다. 이러한 비판을 간략히 알아보면 크게 네 가지로 나눌 수 있다.첫째, 학생들과 학부모들의 학교 선택권이 지극히 제한이 되고 있다는 점이다. 학생과 학부모들은 경제학적 측면으로 보게 되면 수요자가 된다. 이러한 수요자가 어떤 물건을 사고자(어떠한 교육을 받고자) 할 때 정부가 지극히 제한을 하고 있다는 것이다. 국민의 기본권이자 헌법이 보장하고 있는 교육기본권과 행복추구권의 본질적 내용이 고교평준화 정책에 있는 우연적인 결과에 의존하는 추첨에 의해 침해하고 있는 것이다.둘째, 효율적인 학습지도가 불가능하다는 것이다. 우연의 의해 추첨을 해 3년 동안 다닐 고등학교를 결정하는 이러한 제도에서는 당연히 능력 차이가 뚜렷한 학생들이 한 교실에 있을 가능성 크다. 이로 인해 교사들은 누구의 수준을 맞추어 교육을 해야 되는 지에 대한 딜레마에 빠지게 되는 것이다. 이에 정부는 보완조치로 능력에 따른 이동 수업 등을 강화하는 방안이 제시되었으나 이러한 제도가 우리나라에서는 맞지 않는 가상적인 정책일 뿐이라는 것이 현실이다. 이러한 문제들이 해결되지 않은 채 학교가 운영이 되다보니 학생들은 공교육에 대한 신뢰가 없어지게 되고, 결국 교실 붕괴가 이루어지고 있는 것이다. 공교육의 붕괴는 바로 사교육 시장으로 흘러가게 되고, 고교평준화의 정책이 무의미해지게 된다.셋째, 학교의 자율성이 침해를 당하고 있는 점이다. 고교 평준화 정책으로 인해 정부의 보조금을 받다보니, 당연히 정부의 간섭이 있을 것이다. 이러한 간섭은 사립학교의 정체성을 뿌리 채 흔들고 있다. 간섭을 하는 정부의 문제뿐만 아니라, 사립학교 역시 문제를 지니고 있는데 그것은 정부의 지원금을 통해 학교 운영을 하다 보니, 그 지원금에 안주한 채 발전을 위한 학교 스스로의 노력이 없다는 것이다.넷째, 학력의 하향평준화이다. 정부는 평준화를 통해 고등학교간의 격차를 줄여 고등학교 전반의 향상을 의도하였다. 하지만 너무 평등을 주장한 나머지 경쟁이라는 것을 빼버려서 학생들의 학습 의욕을 떨어뜨렸다. 경쟁이 없이 평온한 상태의 학생들은 스스로 목표를 잃어버린 채 의욕이 상실하게 되고, 이러한 문제는 바로 학생들의 학업성취도에도 영향을 미친다. 이러한 문제들이 학력의 하향평준화를 만들고 있는 것이다.4. 바라는 시각4-1 찬성론중학교 교육의 비정상적 운영, 중학생의 신체적, 정신적 발달 저해, 고등학교의 서열화, 교육기회의 불균등 등을 해결하는데 크게 강조한다. 따라서 교육적 문제점과 사회경제적 문제점을 해결하는 데에는 고교 평준화 제도가 더욱 완강히 정착이 되어야 한다고 주장한다. 하지만 그들은 학생과 부모들의 학교 선택권을 무시하는 행동이며, 또한 우리나라가 선진국 대열에 나란히 서기 위해서는 교육을 통해 고급인력 양성을 해야 하는데 그런 제도를 지원해줄 제도적 장치에는 무관심한 태도로 보고 있다는 것이다.

교육학| 2007.02.20| 8페이지| 1,000원| 조회(200)

평준화, 표준화, 학력, 고교평중화, 중하위

미리보기

닫기