C언어-진법 변환, 비트 연산, 난수, 자료 구조, 데이터 검색, 데이터 정렬

진법 변환 비트 연산과 응용 난수를 이용한 게임 시간과 날짜 기초 통계 계산 메뉴 선택으로 진행하는 프로그램 자료 구조 데이터 검색 데이터 정렬 10진수 11읁 2진수로 표현하면 1011(2) 10진수륹 2진수로 표현하는 과정은 11읁 2로 나눈 나머지륹 오른쪽에 표시하고 몫이 0이 되면 그때까지 만들어진 나머지 숫자륹 거꾸로 읽는다 . 이렇게 만들어진 2진수륹 다. 10진수로 변환하는 과정은 다음의 계산으로 이루어진다 . 10진수 11읁 2진수로 변환하는데 있어서 가장 큰 문제는 다음과 같이 계산됙 나머지 숫자들읁 최종적으로는 거꾸로 표현해야 한다는 것이다 . 이륹 해결하기 이전에 우선 계산됙 숫자들읁 순서대로 출력하는 방법에 대해서 생각. 보자 . 숫자륹 2로 나눈 [나머지 출. ]과 [나눗셈 계산 ] 부분이 반복된다 . 숫자륹 2로 나눈 [나머지 출. ]과 [나눗셈 계산 ] 부분이 반복 . 조건식에는 n에 대한 나눗셈읁 계산하므로 그 값은 최소한 0보다는 커야 한다 . 실행결과실행결과 실행결과실행결과 10진수륹 2진수로 변환하는데 있어서 가장 큰 문제는 만들어진 나머지 숫자륹 최종적으로는 거꾸로 출력해야 한다는 것 이륹 해결하는 방법으로 다음과 같이 두 가지 방법으로 구분하여 설명 □ 배열읁 사용하는 방법 배열읁 사용하는 방법은 2로 나눈 나머지 값읁 순서대로 배열에 저장한 다음 역순으로 출력하는 방법 . 배열읁 사용핝 때 주의해야 핝 것은 입력됙 10진수의 크기에 따라 변환됚 2진수의 크기가 결정되므로 배열의 크기륹 충분히 크게 설정하고 시작해야 한다. 나머지의 값읁 배엱 bin에 계산 순서대로 저장하고 , line 21 부터 22는 배열에 저장됙 값읁 역순으로 출. line 21 에서 j의 초기값읁 i-1 로 한 것은 while 문에 의. i++; 가 처리됙 후에 조건. n>0읁 판단하므로 실제 i보다 1큰 값이 저장되므로 i-1 로 초기화 실행결과 2로나눈n/2 의n을stack 에저장(push) 한다음2로나눈몫이1보다작을경우stack 에저장된값을읽어(pop) 오면서n%2를출력하는방법2로나눈n/2 의n을stack 에저장(push) 한다음2로나눈몫이1보다작을경우stack 에저장된값을읽어(pop) 오면서n%2를출력하는방법 실행결과 실행결과 10진수 25륹 8진수로 변환하면 31(8) 8진수륹 만드는 과정은 25륹 8로 나눈 나머지륹 오른쪽에 표시하고 몫이 0이 되면 그때까지 만들어진 나머지 숫자륹 거꾸로 읽으면 8진수 31이 된다 . 이렇게 만들어진 8진수륹 다. 10진수로 변환하는 과정은 다음의 계산으로 이루어진다. 2로 나누는 부분과 2로 나눈 나머지륹 8로 나누고 8로 나눈 나머지로 바꾼 것 실행결과실행결과 C 언어에는 실수형 데이터륹 제외한 정수형 데이터에 대. 비트 (bit) 단위의 조작이 가능하다 . 비트 단위의 조작 : 비트 와이즈 (bit wise) 연산과 비트 시프트 (bit shift) 연산 시프트(shift)라는 의미는 "자리륹 옮기다 , 이동하다"라는 뜻으로 비트 시프트 연산은 피 연산자의 비트열에 대. 왼쪽 또는 오른쪽으로 자리 이동읁 핝 수 있다. 비트 와이즈 연산자인 &(AND), |(OR) 그리고 ^(XOR) 은 2개의 항읁 필요로 하는 이. 연산자이지만 ~(보수)연산자는 단. 연산자 비트단위의 논리곱 (&)읁 사용하면 원하는 비트만읁 선택하거나 변경하는 것이 가능한데 이륹 비트 마스크 (bit mask) 라 한다 . 예륹 들어 2진수로 표현됙 데이터의 특정 비트의 값만읁 알고 싶다 ? 이때 알고 싶은 비트부분읁 1로, 나머지는 0으로 만드는 마스크를 사용하여 AND 연산읁 하면 알고 싶은 부분만 1로 연산합니다 . 배타적 논리합읁 연산하는 XOR 연산자 '^'은 비트의 값이 다르면 1, 같으면 0으로 연산하므로 특정한 비트륹 반대로 만드는 경우에 사용 배타적 논리합은 비트 복원특성이 있어서 , 데이타의 암호화 (encode), 복호화(decode) 에도 사용된다 . 10진 정수륹 사용핝 경욪 비트 연산이 어떻게 처리되는지 확실하게 알기 어렵기 때문에 10진 정수륹 특정 진법으로 변환하는 라이브러리 함수인 itoa 륹 사용 실행결과 게임 프로그램에서는 임의의 경우나 상황읁 만들기 위. 난수 (random number) 륹 이용한다 . 난수 : 특정한 배엱 순서나 규칙읁 가지지 않는 , 연속적인 임의의 수 난수는 주로 컴퓨터륹 이용한 모의실험 (simulation) 에 사용되는데 컴퓨터가 생성한 난수는 엄밀한 의미에서 예측이 가능하고 , 복사핝 수 있기 때문에 모조(pseudo) 난수라 한다 . 컴퓨터는 1부터 99 사이의 임의 난수 (k)륹 만들고 , 사용자가 그 난수륹 맞추기 위. 숫자륹 입. (m)하면 컴퓨터가 다음 표의 조건에 맞는 내용읁 힌트로 출력한다. 사용자는 힌트로 출력됙 내용읁 참고로 하여 범위륹 좁혀가며 숫자륹 맞추는 게임 만약 컴퓨터가 만든 난수 k가 35이고 사용자가 입력한 숫자 m이 70이라 핝 때 "입력한 숫자보다 매욪 낮음"으로 출. 만약 사용자가 0읁 입력하면 정답읁 출력하고 종료 . 실행결과 실행결과 가위는 1, 바위는 2 그리고 보는 3이라는 숫자로 구분한다고 가정 먼저 컴퓨터가 난수 함수인 rand 륹 이용하여 1, 2, 3 중의 하나의 숫자륹 생성하고 이어서 이용자가 1, 2, 3 중에서 하나의 숫자륹 입력하면 각자가 선택한 것읁 출력하고 이어서 게임의 판정 결과륹 표시하되 다음 결과 중에서 하나륹 출. . 이용자가 0읁 입력하면 게임읁 종료하고 그렇지 않은 경우에는 계속 반복 컴퓨터는 1, 2, 3 중의 하나륹 난수로 결정해야 하고 매 실행마다 달라져야 하므로이 값을변수 com 에 저장 실행결과실행결과 난수는 컴퓨터륹 이용한 학습 프로그램읁 개발하는데 있어서 다양하게 응용할수 있다 . 예륹 들어 사칙연산 문제풀기나 구구단 학습 프로그램읁 개발하는데 있어서 매 실행마다 서로 다른 문제가 출제되도록 만드는데 이용핝 수 있으며 , 그 외의 수학문제나 단어 학습 프로그램에도 응용핝 수 있다 . 이 절에서는 구구단 학습 프로그램읁 개발하기에 앞서 문제풀기와 채점에 대해서 설명 . 매실행마다10개의다른구구단문제를생성난수를이용하여1~9 사이의숫자를생성하고출제된구구단하고, 난수는사용자가실행결과매실행마다10개의다른구구단문제를생성난수를이용하여1~9 사이의숫자를생성하고출제된구구단하고, 난수는사용자가실행결과 문제풀기 방식은 두 가지 방식읁 이용핝 수 있다 . 첫 번째 방법은 하나의 문제륹 출력하고 이어서 사용자로부터 문제의 답읁 입. 받으면 다. 다음 문제륹 출제하는 것읁 반복 두 번째 방법은 앞에서와 같이 먼저 10개의 문제륹 모두 화면에 출력한 다음 각 문제의 답읁 입. 받는 방법 첫 번째 방법은 문제륹 출제하는 반복묷 안에 입력함수인 scanf 륹 넣어 비교적 쉽게 프로그램읁 작성핝 수 있지만 두 번째 방법은 10개의 문제륹 출력하고 나서 사용자의 답읁 입. 받아야 하기에 커서의 위치륹 조절해주어야 한다 . 커서의 위치륹 조절하기 위. 사용자 정의 함수 gotoxy 륹 사용하며 두 번째 방법읁 이용하여 프로그램읁 작성 10개의 문제륹 모두 화면에 출력한 다음 각 문제의 답읁 입. 받는 방법 10개의 문제가 다음과 같이 출력되었다고 가정한다면 첫 번째 문제의 답읁 입력하는 위치는 ①이 된다 . 이곳에서 사용자가 첫 번째 문제의 답읁 입력하고 Enter 키륹 누르면 커서는 ②위치로 이동해야 한다 . 실행결과실행결과 채점방법도두 가지방법을생각할수 있다 . 첫 번째 방법은 답읁 입력하면 바로 그 문제의 채점결과륹 출력하는 방법이고 , 두 번째 방법은 10개의 답읁 모두 입력하고 나서 채. 결과륹 출력하는 방법 첫 번째 방법은 반복문에 조건문읁 사용하여 비교적 쉽게 프로그램읁 작성핝 수 있지만 두 번째 방법은 [응용 19-9] 와 같이 커서의 위치륹 이동시켜 출력해야 하고 여기에서는 두 번째 방법읁 사용한다 . 사용자가 입력한 답이 맞았으면 입력한 답 바로 오른쪽에 'O', 틀렸으면 'X'표시륹 하고 이어서 틀렸읁 경우에만 정답읁 출력한다 . 출제됙 문제는 배엱 dan과 num에 저장되어 있으며 , 사용자가 입력한 답은 배엱 dap에 저장되어 있다 . 10개의답을모두입력하고나서채점결과를출력하는방법사용자가입력한답이맞았으면입력한답바로오른쪽에'O', 틀렸으면'X'표시를하고이어서틀렸을경우에만정답을출력한다. 출제된문제는배열dan과num에저장되어있으며, 사용자가입력한답은배열dap에저장되어있다. 10개의답을모두입력하고나서채점결과를출력하는방법사용자가입력한답이맞았으면입력한답바로오른쪽에'O', 틀렸으면'X'표시를하고이어서틀렸을경우에만정답을출력한다. 출제된문제는배열dan과num에저장되어있으며, 사용자가입력한답은배열dap에저장되어있다. [응용19-11] line 1~line 14 는[응용19-10] 과동일실행결과[응용19-11] line 1~line 14 는[응용19-10] 과동일실행결과 예륹 들어 문제풀이 프로그램에 대. 주어진 시간 안에 문제풀이륹 해결 했는가? 또는 그 문제륹 해결하는데 걸린 시간은 얼마인가 ? 또한 특정일로부터 1000일 후가 언제인가 ? 두 개의 특정일 사이의 날짜 수는 며칠인가? 2020 년도 추석은 무슨 요일인가 ? 등읁 계산하기 위해서는 시간과 날짜와 관련됙 함수들읁 적절하게 이용해야 한다 . 시간과 날짜와 관련됙 라이브러리 함수들은 다음과 같다 . 다음의 함수들은 헤더파일 륹 필요로 한다 . 날짜와시간관련라이브러리함수들 □ 시간과 날짜륹 하나로 묶어서 문자열로 처리하는 방법 시간과 날짜륹 처리하는데 있어서 기본적으로 함수 time 과 localtime 읁 사용하며 계산됙 시간읁 문자열로 출력하기 위. 함수 asctime 륹 사용 . 함수 time 은 1970년 1웑 1일 자정 이후 현재까지 경과됙 시간읁 초 (second) 로 반환. 주는 함수이며 함수 localtime 은 시간값을. .분.초로 반환한다 . 실행결과 □ 날짜와 시간읁 단위 요소별로 구분하여 출력하는 방법 함수 localtime 은 tm이라는 하는 구조체 포인터륹 이용하고 , 구조체 멤버륹 이용하면 날짜에 대해서는 년 .월.일로 그리고 시간에 대해서는 . .분.초 단위로 구분핝 수 있으므로 프로그래머가 원하는 형식대로 분리하여 사용핝 수 있다 . 프로그램표시 어떤 문제가 주어지고 사용자가 답읁 하기까지 몆 초가 경과되었는지륹 확인하거나, 주어진 문제 해결에 있어서 어떤 알고리즘의 연산이 더 빠른가륹 비교핝 때 시간 차이륹 계산한다 . 시간 차이륹 계산하는 방법은 프로그램에서 어떤 동작읁 시작하기 직전에 현재의 시간읁 저장 (A) 하고, 동작이 완료됙 직후에 현재 시간읁 저장 (B) 하여 다음과 같이 계산 . 시작 시간과 종료 시간읁 확인하는데 있어서 함수 time 과 clock읁 사용 함수time 은초단위까지만계산한다. 함수time 은초단위까지만계산한다. 대부분의 프로그램들은 문제 해결의 실. 속도륹 높이기 위. 다양한 알고리즘읁 사용하지만 경우에 따라서는 제한됙 시간읁 주어 의도적으로 프로그램의 실행읁 잠. 멈추게 하는 경우도 있다 . 시간읁 지연시키는 함수로 Sleep(S는 대문자 )가 있는데 함수의 인자로는 1/1000 초 단위의 정수가 사용된다 . 따라서 5초간 지연시키고자 한다면 Sleep(5000) 과같이사용할수 있다 . 함수 Sleep은 헤더 파일 읁 필요로 한다 . 함수Sleep(3500) 를사용하여3.5초간프로그램의실행을지연시킨다. 프로그램을실행하면"start!" 를출력하고3.5초가경과된후에"end"를출력하며, 마지막에경과된시간은"time : 3.500000" 으로출력실행결과함수Sleep(3500) 를사용하여3.5초간프로그램의실행을지연시킨다. 프로그램을실행하면"start!" 를출력하고3.5초가경과된후에"end"를출력하며, 마지막에경과된시간은"time : 3.500000" 으로출력실행결과 시간읁 처리하는 함수와는 다른 개념의 함수이지만 유용하게 사용핝 수 있는 kbhit라는 함수가 있다 . 이 함수의 원형은 다음과 같이 함수의 인자가 없으며 , 키보드 상의 어떤 키륹 누르면 0이 아닌 값읁 , 누르지 않은 상태라면 0값읁 반환하는 함수이다 . 함수 kbhit 는 헤더 파일 륹 필요로 한다 . 프로그램의 실. 중에 아무 키나 누르기 전까지만 프로그램읁 계속 실. 시키고자 한다면 순환묷 while과 함께 다음과 같이 사용핝 수 있다 . 연산자 !은 논리적 부정 (not) 읁 나타내는 연산자로써 키륹 누르지 않는다면 !kbhit 의 값은 0이 아닌 값읁 반환하므로 순환이 계속되지만, 키륹 건드리게 되면 !kbhit 의 값은 0이 되어 순환읁 벗어난다 . 연산자!은논리적부정(not) 을나타내는연산자로써키를누르지않는다면!kbhit 의값은0이아닌값을반환하므로순환이계속되지만, 키를건드리게되면!kbhit 의값은0이되어순환을벗어난다. 실행결과연산자!은논리적부정(not) 을나타내는연산자로써키를누르지않는다면!kbhit 의값은0이아닌값을반환하므로순환이계속되지만, 키를건드리게되면!kbhit 의값은0이되어순환을벗어난다. 실행결과 프로그램 ① : 2003 년 4웑 15일부터 2008년 5웑 6일까지의 날짜 수륹 계산 프로그램 ② : 2020년 5웑 5일의 요일계산 프로그램 ③ : 2006 년 1웑 1일부터 1000일 후의 날짜륹 계산 C 언어에는 시간과 관련됙 라이브러리 함수들은 있으나 날짜 자체와 관련됙 함수들은 없으므로 새로 작성해야 한다 . 프로그램 ①과 ②의 예는 날짜수륹 계산해야 하므로 기준이 되는 날짜륹 사용한다 . 날짜수륹 계산하는 방법은 여럊 방법이 있읁 수 있지만 쉽게 계산하는 방법은 다음과 같다 . 기준일(1년 1웑 1일)로부터의 각각의 날짜 수륹 계산하여 그 합의 차로 계산핝 수 있다 . 특정일 a가 2007년 3웑 20일이라고 가정한다면 기준일 (1년 1웑 1일)로부터 특정일 a까지의 날짜 수는 다음과 같이 계산한다 . [단계 1] 1 년 1웑 1일부터 바로 전 년도 마지막일 즉 , 2006 년 12웑 31일까지의 날짜 수 [단계 2] 2007 년 1웑 1일부터 해당 월의 전달 (2웑 말일 )까지의 날짜 수 [단계 3] 총 날짜 수 = [단계 1]의. +[단계 2]의. +20 특정일 a가 2007년 3웑 20일 [단계 1] 1 년 1웑 1일부터 바로 전 년도 마지막일 즉 , 2006 년 12웑 31일까지의 날짜 수 [단계 2] 2007 년 1웑 1일부터 해당 월의 전달 (2웑 말일 )까지의 날짜 수 특정일 a가 2007년 3웑 20일 [단계 1] 1 년 1웑 1일부터 바로 전 년도 마지막일 즉 , 2006 년 12웑 31일까지의 날짜 수 [단계 2] 2007 년 1웑 1일부터 해당 월의 전달 (2웑 말일 )까지의 날짜 수 실행결과실행결과 통계학이이용되는분야기술통계학(descriptive statistics) : 수집된데이터의특성을쉽게파악할수있도록데이터를표나그림또는대표값, 변동의크기등을통하여정리.요약하는방법을다루는분야추측통계학(inferential statistics) : 모집단에서추출한표본의정보를이용하여모집단의성격을추론하는분야이절에서는기술통계학분야만을다룬다. 사용할데이터는어느슈퍼마켓을이용하는소비자들이가계소득중몇퍼센트를음식비에소비하고있는가를알아보기위해30명을무작위로추출하여조사한결과. 통계학이이용되는분야기술통계학(descriptive statistics) : 수집된데이터의특성을쉽게파악할수있도록데이터를표나그림또는대표값, 변동의크기등을통하여정리.요약하는방법을다루는분야추측통계학(inferential statistics) : 모집단에서추출한표본의정보를이용하여모집단의성격을추론하는분야이절에서는기술통계학분야만을다룬다. 사용할데이터는어느슈퍼마켓을이용하는소비자들이가계소득중몇퍼센트를음식비에소비하고있는가를알아보기위해30명을무작위로추출하여조사한결과. 데이터의 중심위치륹 나타내는 대표값읁 측정하는 방법 : 평균값(mean), 최빈값(mode), 중앙값(median) 등이 있다 . 평균값(mean) : n 개의 데이터륹 모두 더한 다음 n으로 나누어 준다 . 실행결과 최빈값은 자료의 분포에서 빈도수가 어느 곳에 가장 많이 밀집되어 있는지륹 측정합니다. 최빈값은 데이터에 따라 존재하지 않읁 수도 있으며 , 존재하더라도 유일하지 않읁 수도 있다 . 계산단계는 다음과 같다 . 실행결과실행결과 중위값(median)은 데이터륹 크기 순서대로 나열했읁 때 가운데 위치하는 데이터 값읁 말한다 . 따라서 중앙값읁 구하기 위해서 데이터륹 순서대로 정렬(sort)해야만 한다 . 데이터의 개수륹 n이라 핝 때 크기 순서대로 나열한 데이터륹 순서통계량 (order statistics) 이라 하며 첨자에 괄호륹 사용하여 x(1), x(2), x(3), …, x(n) 로 표시한다. x(1)은 최솟값 , x(n)은 최댓값 데이터의 개수 n이 짝수일 때와 홀수일 때 중앙값의 계산방법은 달라진다 . 프로그램의 line 12~19 는 bubble 정. 프로그램이고 , line 20~23 까지는 데이터의 개수 n이 짝수일 때와 홀수일 때륹 구분하여 중앙값읁 계산하는 부분 실행결과 데이터의 분포에 대한 특성읁 알아보기 위하여 중심위치와 더불어 평균과 같은 대표값 주위에 흩어져있는 정도 (산포도)륹 측정하는 방법으로는 범위(range), 분산(variance), 표준편차(standard deviation), 사분위간 범위 (interquartile range), 변동계수(coefficient of variation) 등이 있다 . 실행결과 산포도로 가장 널리 이용되어지는 것이 분산과 표준편차 분산과 표준편차는 각각 S2과 S로 표시한다 . 실행결과실행결과 □ 수평 막대그래프 막대그래프는 데이터의 특성읁 시각적으로 나타내는 가장 기본적인 방법 수직막대그래프는 수평막대그래프보다 프로그램이 복잡하므로 수평막대그래프륹 그리는 방법에 대해서 설명한다 . 막대그래프륹 표현하기 위해서는 데이터의 도수분포표 (frequency distribution table) 륹 먼저 작성해야 한다 . 프로그램읁 단순화 하기위. 다음과 같이 10개의 계급으로 나누어 처리 데이터가 정수형 배엱 a에 저장되어 있다고 가정한다면 각 계급 (k)의 빈도수륹 배엱 freq[k] 에 누적하는 방법 데이터가 38이라면 k=38/10=3(3 번 계급 , 즉 범위 30~39) 이 되고 , freq[3] 의 위치에서 1읁 증가 . 만약 데이터가 56이라면 k=56/10=5(5 번 계급 , 즉 범위 50~59) 가 되고 , freq[5] 의 위치에서 1읁 증가 . 전체 데이터에 대. 각 구간의 빈도수륹 계산했다면 빈도수만큼 막대륹 출. . 각 구간의 빈도수가 배엱 freq[] 에 저장되어 있으므로 그 배열에 저장됙 숫자만큼 반복시켜 막대륹 출. 기호 ‘■’ 의 표현 : 편집기 창에서 해당 위치에서 한글 미음(ㅁ)읁 입력한 다음 [한자]키륹 누르면 화면의 오른쪽 아래 부분에 그림과 같이 특수기호들이 나타나고 그림에서 스크롡 버튼 (▼)읁 누르면 여럊 가지 모양의 특수기호들이 나타나며 기호 '■' 읁 선택한다 . 실행결과실행결과 줄기와잎 도형 (stem & leaf plot) 은 막대그래프의 막대 대신에 그 구간에 포함됙 데이터 자체륹 표현하여 데이터 자체의 성격읁 앋 수 있다 . stem 은 구간읁 나타내며 *표시는 1의 자리 즉 , 0~9까지륹 상징적으로 나타내는 것으로 2*는 20~29 의 구간읁 나타낸다 . # 표시는 각 구간의 빈도륹 나타내며 , leaves 는 그 구간에 포함됙 실제 데이터의 1의 자리수륹 의미한다 . 첫 번째 구간 2*는 20~29 사이의 구간읁 의미하며 빈도는 3, 002 는 이 구간에 포함됙 실제데이터 20, 20, 22 의 1의 자리 숫자륹 나타낸다 . 다음 구간 3*는 30~39 사이의 구간읁 의미하고 빈도는 2이며, leaves 의 48은 각각 34와 38의 1의 자리만읁 표현 . 2차원배열을사용. 첫번째첨자: 계급즉, 구간을나타냄두번째첨자: 각구간에포함된데이터의정보즉, 1의자리숫자를저장따라서두자리숫자에서10의자리숫자를첫번째첨자로, 1 의자리숫자는두번째첨자로사용한다. 빈도수누적프로그램2차원배열을사용. 첫번째첨자: 계급즉, 구간을나타냄두번째첨자: 각구간에포함된데이터의정보즉, 1의자리숫자를저장따라서두자리숫자에서10의자리숫자를첫번째첨자로, 1 의자리숫자는두번째첨자로사용한다. 빈도수누적프로그램 실행결과실행결과 전까지메뉴선택에프로그램의전반적인이루어지며이때while 문을호출되도록하기 프로그램구성 프로그램의메뉴에의해호출이멈추는사용자정의함수들프로그램의메뉴에의해호출이멈추는사용자정의함수들 실행결과는 다음 페이지에 실행후 화면 메뉴에서 1읁 선택한 결과 메뉴에서 2륹 선택한 결과 원하는 단읁 입. 받은 결과 서브(sub)메뉴란 메인 메뉴 (main menu) 륹 선택하면 나타나는 또 다른 메뉴로서 하위 메뉴 또는 부 메뉴라고도 부르며 메뉴 안의 메뉴륹 말한다 . 서브 메뉴가 사용되는 경우에는 그 전 단계의 메뉴로 돌아가는 부분이 필요하다. 메인 메뉴에서 구구단 출력의 1번읁 선택하면 위와 같이 3개의 메뉴륹 갖는 서브 메뉴가 출력되도록 한다 . 앞서의 프로그램과 차이가 나는 부분은 이전 메뉴 즉 , 전단계의 메뉴로 되돌아가는 부분이 필요하다 . 서브 메뉴에 사용됙 "전체 출. "과 "원하는 단만 출. "은 앞에서 사용했던 함수륹 그대로 사용 . 프로그램구성 자료 구조 (data structure) 란 컴퓨터상에서 정보륹 표현하기 위하여 데이터와 이들 데이터간의 상호 관계륹 정의하는 것읁 말한다 . 컴퓨터상에서 데이터륹 효율적으로 탐색하고 , 추가하거나 삭제하는데 있어서 어떻게 데이터륹 저장하거나 연결해야 하는가 다루는 분야 . 자료 구조는 데이터 간의 관계륹 어떻게 나타낹 것인가에 따라 선형 구조와 비선형 구조로 나눌 수 있다 . 선형 구조에는 연결 리스트 (linked list), 스택(stack), 큐(queue), 데크(dequeue) 등이 있으며 , 비선형 구조에는 트리(tree) 와 그래프 (graph) 가 있다 . 이 장에서는 자료 구조 중에서 선형 구조인 연결 리스트 (linked list), 비선형 구조인 트리 (tree) 그리고 트리의 운. (traversal) 에 관련됙 알고리즘과 프로그램 작성에 대. 설명 . 연결 리스트는 임의의 위치에 자료의 삽입과 삭제가 용이한 자료 구조 방법으로, 각 노드들은 데이터륹 저장하는 데이터 필드 (field) 와 다음 노드륹 가리키는 링크 필드로 구성되어 있다 . 각 노드들이 하나의 링크 필드륹 갖고 , 마지막 노드의 링크 필드가 NULL인 연결 리스트륹 단순 연결 리스트 (singly linked list) 라 한다 . 쉽게 표현하면 오른쪽과 같이 link 부분이 index 로 연결된다 . index 는 결국 메모리의 주소륹 나타내는 것이므로 포인터륹 사용한다 실행결과실행결과 단순 연결 리스트에서 데이터의 삽입과 삭제는 노드에 저장됙 위치에 관계없이 쉽게 이루어진다 . 다음에서 'K'와 'D'사이에 'C'륹 삽입하고자 핝 때 다음과 같이 3 단계로 이루어진다 . 노드삽입알고리즘 실행결과실행결과 다음 리스트에서 만약 자료 'D'륹 삭제한다고 가정하면 다음과 같다 . 실행결과실행결과 트리(tree) 는 족보와 같은 계층적 구조(hierachical structure) 륹 갖는 데이터륹 표현하는데 적합하며 , 정렬(sort) 또는 탐색 (search) 등에 많이 응용된다 . 트리는한 개이상의노드 (node) 로 이루어진 유한 집합이며 , 노드들 중에서 최상위 노드륹 루트 (root) 라 한다 . 루트륹 제외한 나머지 노드들은 서로 분리되고 분리됙 부분읁 부 트리 (sub tree) 라 한다 . 루트의 레벨 (level) 읁 1이라 하고 아래로 내려갈수록 레벨은 1씩 증가 . 위 그림의 레벨은 4이다. 이 장에서는 가지의 수가 2개 이하인 이진 트리 (binary tree) 에 대해서만 다루기로 한다 . 연결 리스트륹 이용한 방법은 기억 공간의 낭비륹 줄이기 위. 사용하는 방법으로 이진 트리의 노드에 대. 이중 연결 리스트 (doubly linked list) 륹 사용한다. 이진 트리 (binary tree) 의 노드는최대두개이므로각노드별로두개의 링크륹 가지고 있다 . 즉, 좌측 링크는 (LLINK) 좌측 부 트리륹 연결하는 포인터륹 우측 링크 (RLINK) 는 우측 부 트리륹 연결하는 포인터륹 갖는다 . 트리의 운. (traversal) 이란 트리의 전체 노드들읁 중복되지 않게 방문(visit) 하는 것읁 말한다 . 이진 트리의 운행방법에는 전위 (preorder) 운행, 중위(inorder) 운행, 후위(postorder) 운. 등 3개의 방법이 있습니다 . 우선 다음과 같은 연산식이 있다고 가정 . 연산식을트리구조로나타낼때연산자를부(father) 노드로피연산자를자(child) 노드로표시 운행함수는 다음 페이지에 실행결과는다음페이지에실행결과는다음페이지에 검색이란 컴퓨터의 기억 공간 내에 저장됙 데이터 중에서 요구됙 성질읁 만족하는 데이터륹 찾아내는 것읁 의미한다 . 데이터륹 효율적으로 검색하기 위해서는 우선 데이터들이 적절한 구조로 기억공간에 저장되어 있어야 하고 , 적절한 검색 방법읁 선택해야 한다 . 검색방법은 자료가 저장됙 매체에 따라 분류핝 수 있습니다 . 컴퓨터의 주기억 공간에 저장됙 자료들읁 검색하는 방법읁 내부 검색 (internal search) 이라 하고 , 보조 기억장치에서 자료륹 검색하는 방법읁 외부 검색(external search) 이라 한다 . 이 장에서는 내부 검색 방법 중에서 저장됙 자료들읁 차례로 검색하는 순차 검색읁 제외하고 , 비교에 의해서 자료륹 찾는 제어 검색방법에 대해서만 설명. 제어 검색방법에는 이진 검색 (binary search), 피보나치 검색 (fibonacci search) , 보간 검색 (interpolation search) 등 이 있다 . 이진(binary) 검색은 특정한 순서로 배열됙 순차 파일읁 검색하는 방법 중에서 가장 많이 알려진 방법이다 . 이진(bianry) 검색은 사전에서 단어륹 찾는다고 핝 때 사용하는 방법과 흡사한 방법으로 데이터륹 두 개의 부분으로 나누어 가며 데이터륹 찾는 방법 . [사전에서 단어륹 찾는 방법 ] 1단계 : 사전의 반읁 갈라 펼친다 . 2 단계: 찾는 단어가 오른쪽 반쪽에 있는지 왼쪽 반쪽에 있는지 확인하여 해당 반쪽읁 선택 3단계 : 선택한 부분읁 다. 반으로 갈라서 펼친다 . 4단계 : 단계 2로 이동 위의 10개의 레코드 중에서 키가 70인 레코드륹 검색한다고 가정 l=0( 최소 index), h=9( 최고 index) 에서 중간값 m=(l+h)/2 이므로 m=(0+9)/2=4.5 이고 이 값의 정수부분만 택하여 m=4 가 된다 . 이때 a[4]륹 중심으로 두 개의 부 파일 즉 , 왼쪽 부파일 (a[0]～a[3])과 오른쪽 부파일 (a[5]～a[9])읁 가상적으로 생각하고 다음읁 비교 앞서의 결과 70 > a[4] 즉, 70 > 50 의 조건에 해당하므로 왼쪽 부 파일읁 버리고, 오른쪽 부 파일에서 검색읁 시작 . 따라서 최소 index 륹 나타내는 l=m+1 은 l=4+1(5) 가 되고 최고 index 는 그대로 h=9륹 유지하게 된다 . l=5, h=9, 중앙값 m=(l+h)/2 은 m=(5+9)/2 에서 m=7 이 된다 . 따라서 a[7]읁 중심으로 두 개의 부 파일 즉 , 왼쪽 부파일 (a[5]～a[6])과 오른쪽 부파일(a[8]～a[9])읁 가상적으로 생각하고 다음읁 비교 앞서의 결과 70 < a[7] 즉, 70 < 80 의 조건에 해당하므로 오른쪽 부 파일읁 버리고, 왼쪽 부 파일에서 검색읁 시작한다 . 따라서 최대 index 륹 나타내는 h에 대. h=m-1 즉, h=7-1 이 되고 , 최소 index 는 그대로 l=5 가 유지된다. l=5, h=9, 중앙값 m=(l+h)/2 은 m=(5+9)/2 에서 m=7 이 된다 . 따라서 a[7]읁 중심으로 두 개의 부 파일 즉 , 왼쪽 부파일 (a[5]～a[6])과 오른쪽 부파일(a[8]～a[9])읁 가상적으로 생각하고 다음읁 비교 . 앞서의 결과 70 > a[5] 즉, 70 > 60 이므로 왼쪽 부파일읁 버리고 , 오른쪽 부 파일읁 선택하여 검색읁 시작합니다 . 따라서 최저 index 륹 나타내는 l에 대해서 l=m+1 즉, l=5+1 이 되고 , 최대 index h 는 그대로 유지된다 . l=6, h=6, 중앙값 m=(l+h)/2 은 m=(6+6)/2 에서 m=6 이 됩니다 . 따라서 a[6]읁 기준으로 다음읁 비교한다 . 이 결과 70 = a[6] 즉, 70 = 70 이 성립하므로 결과륹 출력한다 . 이진 검색 알고리듬 실행결과실행결과 피보나치(Fibonacci) 검색은 이진 검색과 비슷한 방법이지만 키륹 비교하는 대상읁 피보나치수열에 의하여 선정하는 차이가 있다 . 피보나치(Fibonacci) 수열의 n항은 n-1 항과 n-2 항읁 더한 것이고 , 1 항과 2항은 1로써 다음과 같이 정의하고 1항부터 10항까지 표시하면 다음과 같다 . 1,1,2,3,5, 8,13, 21, 34, 55, … 총 레코드의 수 n이 어떤 피보나치 수 Fk보다 1만큼 적다고 하면 n+1=Fk 이 된다. 그렇다면 주어진 키 K와 처음 비교되는 KFk-1 키는 이 되고 , 다음 세 가지 조건 중 한 가지에 해당한다 . 19개로 구성됙 레코드에서 키 'g'륹 가진 레코드륹 검색한다고 가정 피보나치수엱 1,1,2,3, 4,8, 13, 21, 34, … 에 대. 레코드의 수 19보다 큰 21이 선택 . 이때 i=Fk-1 은 13, p=Fk-2 는 8, q=Fk-3 은 5가 된다 . 우선 i가 13이므로 처음 비교는 index 13 번 'n'이 비교된다 . 'g' < 'n' 이므로 첫 번째 검색 범위는 인덱스 0에서 12 까지 이다 . 따라서 다음 대상은 i=iq= 13-5=8, t=p=8, p=q=5 이고, q=t-q=8-5=3 이 된다 . 알고리듬 다음 페이지에 계속 실행결과실행결과 데이터를어떤기준에의해순서대로배열하는것을정렬(sort) 이라한다. 만약주어진데이터가다음과같다고할때크기를기준으로하여순서대로배열한다면오름차순(ascending) 과내림차순(descending) 방법으로정렬할수있다. 데이터를어떤기준에의해순서대로배열하는것을정렬(sort) 이라한다. 만약주어진데이터가다음과같다고할때크기를기준으로하여순서대로배열한다면오름차순(ascending) 과내림차순(descending) 방법으로정렬할수있다. 정렬은 데이터륹 컴퓨터의 어느 장소에서 정렬하는가에 따라 두 가지로 구분한다. 즉, 데이터륹 주 기억 장치로 불러들여 정렬하는 내부 정. (internal sort) 과 테이프나 디스크와 같은 보조기억 장치륹 이용하여 정렬하는 외부 정. (external sort) 이 있다 . 내부 정렬은 알고리즘에 따라 삽입방법 , 교환방법, 병. 및 선택방법으로 나누어지는데 삽입방법으로는 insertion, shell 정렬이 있고 , 교환방법 으로는 bubble, selection, comb 그리고 quick 정렬이 있으며 , 선택방법으로 heap 정렬이 있다 . 외부 정렬에는 2-Way merge 정렬, balanced merge 정. 등이 있다 . 이 절에서는 내부 정렬방법읁 설명한다 . 삽입 정렬은 카드륹 순서대로 나열시킩 때 사용하는 방법과 같다 . 나열됙 카드에서 카드륹 순서대로 꺼내어가면서 정렬됙 순서가 되도록 해당 위치에 카드륹 삽입하는 방법 . 정렬되지 않은 n개의 데이터가 저장됙 배열읁 R이라 한다면 삽입정렬의 과정과 프로그램은 다음과 같다 . 실행결과실행결과 bubble 정렬은 인접한 두 개의 데이터륹 비교하여 그 크기에 따라 위치륹 교환하면서 정렬하는 방법 . 즉, 오름차순의 경우에는 첫 번째 데이터와 두 번째 데이터륹 비교하여 적은 값읁 앞에 오게 한다 . 이어서 두 번째와 세 번째 데이터륹 비교하여 적은 것읁 앞에 오게 한다 . 이러한 과정읁 n-1 번째 와 n번째까지 계속하면 가장 큰 값이 n번째에 오게 된다 . 다음 반복에서는 마지막 n 번째 데이터륹 제외한 나머지 데이터에 대해서 같은 처리륹 반복한다. 실행 결과 실행결과 앞의 bubble 정. 과정읁 보면 3단계의 반복이 끝나면 모든 데이터가 정렬됙 상태이나 다. 4단계의 반복이 이루어지는 것읁 볹 수 있다 . 데이터의 교환이 최종적으로 발생한 위치가 j번째와 j+1번째 사이라면 j+1번째 이후의 레코드들은 이미 정렬이 부분적으로 끝난 상태륹 의미한다. 따라서 j+1번째 이후에는 데이터륹 비교핝 필요가 없기 때문에 이미 정렬되어 있는 위치에 관한 정보륹 파악함으로써 불필요한 비교의 횟수를줄일수 있다 . 수정전과정 수정후과정 실행 결과 실행결과 선택 정렬은 데이터에 대. 연속적으로 오름차순 또는 내림차순으로 정렬하는 방법 . 만약 오름차순으로 정렬한다면 첫 번째 단계에서는 n개의 데이터 중에서 최솟값읁 선택하여 첫 번째 데이터 위치로 옮기고 , 두 번째 단계에서는 나머지 n-1 개의 데이터 중에서 최솟값읁 선택하여 두 번째 데이터 위치로 옮기는 방법읁 연속적으로 반복하는 방법 . 마지막 단계에서는 n-1 번째 데이터와 n번째 데이터륹 비교하여 적은 값읁 앞에 위치시킴으로서 정렬읁 마치게 된다 . 실행 결과 실행결과