문제를 풀기 전, 7~8 강을 시청하시고, “ 셋째주 추가자료 ”를 읽고 숙지하시기 바랍니다 . 그들은 검색 알고리즘(선형 및 이진), 정렬(많은 것들이 있습니다!) 및 디버거 작업(디버거를 사용하여 프로그램을 디버깅하는 능력은 매우 중요한 기술입니다!)에 전념합니다. 강의와 이론대로 모든 것이 진행되었다면 시험 문제에 쉽게 답할 수 있습니다.
이진 검색에 정렬된 배열이 필요한 이유는 무엇입니까?
버블 정렬이 O(n2)로 추정되는 이유는 무엇입니까?
삽입 정렬 추정값이 Ω(n)인 이유는 무엇입니까?
선택 정렬은 어떻게 작동하나요? 세 문장(또는 그 이하)으로 설명하세요.
병합 정렬을 실행할 수 있는 시간의 상한(최악의 경우)은 무엇입니까?
GDB 디버거를 사용하면 프로그램을 디버깅할 수 있습니다. 그리고 좀 더 구체적으로 공식화하면 정확히 무엇을 할 수 있게 됩니까?
목표
여러 파일이 포함된 프로젝트 작업 방법 알아보기
다른 사람의 소스 코드를 읽는 법을 배우세요
다양한 알고리즘과 재귀함수 이해
이러한 목표의 대부분은 공식적으로 평가하는 것이 사실상 불가능합니다. 따라서 문제를 정식으로 검증하는 관점에서 보면 어렵게 느껴질 부분은 거의 없습니다. 하지만 프로그래밍은 지속적인 연습을 통해서만 배울 수 있다는 점을 상기시켜 드립니다! 따라서 작업을 해결하는 것뿐만 아니라 추가 시간과 노력을 투자하여 이번 주에 논의된 모든 알고리즘을 구현하는 것이 좋습니다. 앞으로!
시작하다
1주차와 2주차의 연습 문제에서는 처음부터 프로그램을 작성하고 mkdir 명령을 사용하여 자신만의 pset1 및 pset2 디렉토리를 만들었습니다 . 세 번째 주의 연습 과제에서는 우리가 작성한 배포판(또는 "distro"라고 부름)을 다운로드하고 여기에 자신만의 코드 줄을 추가해야 합니다. 먼저 코드를 읽고 이해해 보세요. 이번 주 가장 중요한 기술은 다른 사람의 코드를 읽는 방법을 배우는 것입니다. 따라서 cs50.io에 로그인하고 터미널 창에서 명령을 실행하여 작업 영역 버전이 최신인지 확인하세요. 실수로 터미널 창을 닫았으나 찾을 수 없는 경우 보기 메뉴로 이동 하여 콘솔 옵션이 선택되어 있는지 확인하세요(그렇지 않은 경우 확인). 터미널 창 프레임의 녹색 원 안에 있는 (+)를 클릭하고 New Terminal 을 선택합니다 . 그런 다음 명령을 실행 하고 작업 공간 디렉터리(사용자 디렉터리) 내에 있는지 확인하세요. 그런 다음 다음 명령을 실행하여 문제집의 ZIP 아카이브를 작업 공간에 다운로드합니다(wget은 Linux 다운로드 명령입니다). 모든 것이 정상이면 줄에 다음 문구가 표시됩니다. 다음 명령을 실행하여 pset3.zip을 실제로 다운로드했는지 확인한 다음 실행하여 파일의 압축을 풉니다. 이제 ls 명령을 다시 실행하면 pset3 디렉토리 도 표시됩니다 . 명령을 실행하여 해당 디렉토리로 이동한 다음 디렉토리의 내용을 다시 보도록 요청하십시오. 이 디렉토리에는 두 개의 하위 디렉토리가 있음을 알 수 있습니다. 이미 흥미롭습니다! update50cd ~/workspacewget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip'pset3.zip' savedlsunzip pset3.zipcd pset3lsfifteen find
찾다
이제 이러한 하위 디렉터리 중 하나를 살펴보겠습니다. 이를 위해 다음 명령을 실행합니다. cd ~/workspace/pset3/find 이 폴더의 내용을 화면에 표시하면(이 작업을 수행하는 방법을 이미 기억하고 있을 것입니다) 다음과 같이 표시됩니다. 와, helpers.c helpers.h Makefile find.c generate.c 파일이 많습니다. 하지만 걱정하지 마세요. 지금 처리하겠습니다. generate.c 파일에는 "의사 난수 생성기"(drand48 함수 에 의해 생성됨 )를 사용하여 다수의 무작위(실제로 의사 난수, 컴퓨터는 순수한 무작위성을 처리할 수 없음!) 숫자를 생성하는 프로그램에 대한 코드가 포함되어 있습니다. 을 입력하고 한 번에 하나씩 한 줄에 배치합니다. 프로그램을 컴파일합니다. make generate 이제 다음 명령을 실행하여 실행합니다. ./generate 프로그램은 다음 메시지를 표시합니다. Usage: generate n [s] 이는 프로그램이 하나 또는 두 개의 명령줄 인수를 예상한다는 의미입니다. 첫 번째 인수를 사용하여, n은 필수입니다. 이 숫자는 생성하려는 의사 난수 수를 의미합니다. 매개변수 s는 대괄호로 표시되는 선택 사항입니다. 숫자 s는 의사 난수 생성기의 "시드"라고 할 수 있습니다. 출력에 영향을 미치는 의사 난수 생성기에 대한 입력 데이터를 의미합니다. 예를 들어, drand48을 사용하는 경우 먼저 인수 1을 사용하여 srand48(drand48을 "시드"하는 또 다른 함수)을 호출하고 그런 다음 drand48을 세 번 호출하면 drand48은 2728, 29785, 54710을 반환할 수 있습니다. 이전 호출 대신 drand48을 사용하는 경우 먼저 2라는 인수로 srand48을 호출한 다음 다시 drand48을 세 번 사용하면 drand48이 59797, 10425, 37569를 반환합니다. 그러나 인수 1을 사용하여 srand48을 다시 호출하여 drand48을 다시 보면 drand48에 대한 다음 세 번의 호출 결과는 다시 2728, 29785, 54710을 얻게 됩니다! 알다시피, 모든 일에는 이유가 있습니다. 프로그램을 다시 실행하십시오. 이번에는 아래와 같이 n=10이라고 가정해 보겠습니다. 10개의 의사 난수 목록이 표시됩니다. ./generate 10 동일한 n 값을 사용하여 프로그램을 세 번째 실행해 보겠습니다. 10개의 숫자가 포함된 또 다른 목록이 표시됩니다. 이제 두 개의 매개변수를 사용하여 프로그램을 실행해 보세요. 아래와 같이 s=0을 가정하겠습니다. ./generate 10 0 이제 동일한 명령을 다시 실행하십시오. ./generate 10 0 논쟁할 수도 없습니다. 10자리의 동일한 "무작위" 시퀀스를 다시 보았습니다. 의사 난수 생성기 시드를 변경하지 않으면 이런 일이 발생합니다. 이제 generate.c 프로그램 자체를 살펴보겠습니다.(어떻게 기억하시나요?) 이 파일 시작 부분의 주석은 프로그램의 일반적인 기능을 설명합니다. 하지만 우리는 코드 자체에 대해 언급하는 것을 잊어버린 것 같습니다. 코드를 주의 깊게 읽고 각 줄의 의미를 이해할 때까지 읽으십시오. 그런 다음 이 코드를 주석 처리하여 각 TODO를 해당 코드 줄의 목적이나 기능을 설명하는 문구로 바꿉니다. (참고: unsigned int는 "unsigned" int이므로 음수일 수 없습니다.) rand 또는 srand에 대한 자세한 정보를 얻으려면 다음을 실행하십시오. man drand48 또는 man srand48 generate.c에서 최대한 많은 주석을 처리한 후 프로그램을 다시 컴파일하여 아무것도 손상되지 않았는지 확인하십시오. make generate generate가 더 이상 컴파일되지 않으면 수정하십시오. 고장났어요: )! 참고로 make 명령은 코드 컴파일을 자동화하므로 여러 스위치를 수동으로 삽입하여 clang 명령을 실행할 필요가 없습니다. 그러나 실제로 make는 입력을 단순화할 뿐이지만 실제로는 필요한 매개변수가 포함된 동일한 클랭이 그 뒤에 숨겨져 있습니다. 그러나 프로그램이 커질수록 make는 더 이상 코드를 컴파일하는 방법을 컨텍스트에서 파악할 수 없습니다. 이 경우, 특히 다른 소스 파일(예: .c)을 사용하는 경우 프로그램을 컴파일하는 방법을 make에게 알려주어야 합니다. 이 문제를 해결하기 위해 우리는 Make가 무엇을 해야 할지 정확하게 알려주는 구성 파일(Makefile)을 사용할 것입니다. make 명령은 생성을 컴파일하는 방법을 어떻게 알았습니까? 실제로 팀에서는 이미 작성한 구성 파일을 사용했습니다. 이 파일은 Makefile 이라고 불리며 generate.c 와 같은 디렉토리에 있습니다 . Makefile은 generate.c에서 생성된 파일을 생성하는 방법을 지정하는 규칙 목록입니다. 파일에서 특히 관련 라인을 찾을 수 있습니다. generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c 첫 번째 라인은 두 번째 라인에서 명령을 호출하여 generate라는 "대상"을 생성해야 함을 make에게 알려줍니다. 더욱이, 첫 번째 줄은 생성이 generate.c에 의존한다는 것을 make에게 알려줍니다. 이는 해당 파일이 변경된 경우 make가 후속 실행에서만 생성을 다시 빌드한다는 것을 의미합니다. 시간을 절약해 주는 나쁜 방법은 아니죠? 실제로 generate.c 를 변경하지 않았다면 아래 명령을 다시 실행하세요 . make generate 생성이 이미 현재 버전으로 업데이트되었다는 알림을 받게 됩니다. 참고 : 두 번째 줄 시작 부분의 들여쓰기는 일련의 공백이 아니라 탭 문자입니다. 불행하게도 make에서는 명령 앞에 탭이 와야 하므로 공백으로 변경하지 않도록 주의하세요. 그렇지 않으면 이상한 오류가 발생합니다! -Werror 플래그는 clang 명령을 알려줍니다.경고(나쁜)를 오류(심지어 더 나쁨)로 처리하면 이를 수정해야 합니다(좋은 교육적 방법으로!). 이제 find.c 파일을 살펴보겠습니다 . 이 프로그램에는 값의 "건초 더미"에서 찾아야 하는 "igloo"라는 하나의 명령줄 인수가 필요합니다. 그런 다음 코드를 검토하고 아래 명령을 실행하여 프로그램을 컴파일합니다. make find make는 기본적으로 다음을 제공했습니다. clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 주의하세요! 방금 helpers.c 및 find.c 라는 두 개의 파일로 구성된 애플리케이션을 컴파일했습니다 . 이 사실을 어떻게 알았나요? 이를 이해하려면 Makefile을 다시 열어 실제로 무슨 일이 일어나고 있는지 확인하세요. 관련 줄은 다음과 같습니다. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 종속성(콜론 뒤)이 의미하는 바는 find.c , helpers.c 또는 helpers.h 에 대한 모든 변경 사항이 다음에 해당 목적으로 호출될 때 make가 find를 다시 빌드하도록 강제한다는 것입니다. 이제 예를 들어 다음을 수행하여 이 프로그램을 실행하십시오. ./find 13 그런 다음 특정 스택(즉, 정수)을 제공하고 한 번에 빨대 하나씩 공급하라는 메시지가 표시됩니다. 숫자 입력이 지겨워지면 Ctrl-D 키 조합을 누르세요 . 이 조합은 프로그램에 EOF(파일 끝) 문자를 보냅니다. 기호는 CS50 라이브러리의 GetInt 함수가 상수 INT_MAX 를 반환하도록 강제 하고, 결과적으로 find.c 에서 find가 "stack" 입력을 중지하도록 강제합니다. 이제 프로그램은 귀하가 제공한 건초 더미에서 바늘을 찾고, 바늘이 발견되었는지 알려줄 것입니다. 즉, 프로그램은 배열에서 일부 값을 검색합니다. 최소한 그래야 하지만 문제는 그녀가 아직 아무것도 찾지 못한다는 것입니다! 하지만 여기 당신이 구출하러 왔습니다! 역할의 중요성에 대해서는 잠시 후에 이야기하겠습니다. 실제로, 건초 더미를 제공하는 프로세스는 적어도 생성 출력을 입력으로 찾기에 "병합"함으로써 자동화될 수 있습니다. 예를 들어 아래 명령은 find에 1000개의 의사 난수를 전달한 다음 해당 값 중에서 42를 검색합니다. ./generate 1000 | ./find 42 생성이 find에 원시 데이터를 전달할 때 생성 번호는 표시되지 않지만 find 실행 중은 표시됩니다. . 또는 다음과 같은 명령을 사용하여 generate 출력을 파일로 "리디렉션"할 수 있습니다. ./generate 1000 > numbers.txt 이 파일의 내용은 다음 명령을 사용하여 find 입력으로 리디렉션할 수 있습니다. ./find 42 < numbers.txt Makefile의 코드를 다시 살펴보고 다음 줄: all: find generate 이는 다음 명령을 실행하여 생성 및 찾기를 빌드할 수 있음을 의미합니다. make all 게다가 이 줄 아래의 명령은 위의 명령과 동일합니다. 왜냐하면 make가 기본적으로 Makefile의 첫 번째 항목을 빌드하기 때문입니다. make 이 모든 연습 과제를 하나의 명령으로 요약할 수 있다면! 하지만-아아! 마지막으로 Makefile의 마지막 줄에 주의하세요. clean: rm -f *.o a.out core find generate 이 항목을 사용하면 .o로 끝나거나 core라고 불리는 모든 파일을 제거할 수 있으며(이에 대해서는 잠시 후에 설명하겠습니다!), 간단히 프로그램 찾기 또는 생성을 실행할 수도 있습니다. 행을 실행하여: 실험하고 싶다면 make clean 여기에 주의해야 할 것이 있습니다. 예를 들어 Makefile의 마지막 행에 *.c를 추가하지 마십시오! (왜?) # 기호로 시작하는 모든 줄은 단지 주석일 뿐입니다.
작업 1: 검색
흥미로운 일을 할 시간입니다! find.c는 helpers.h 에 선언된 함수인 search를 호출 합니다 . 불행하게도 우리는 helpers.c 에서 이 기능을 완전히 구현하는 것을 잊어버렸습니다 ! ( helpers.h 와 helpers.c 의 내용을 하나의 find.c 에 넣을 수 있다는 점에 유의해야 합니다. 그러나 때로는 프로그램을 여러 파일로 분리하는 것이 더 좋습니다. 특히 일부 기능 또는 오히려 유틸리티 기능이 유용할 수 있는 경우 다른 프로그램의 경우 예를 들어 CS50 라이브러리 함수와 같습니다. helpers.c를 살펴보면 주어진 값이 값에 있는지 여부에 관계없이 검색이 항상 false를 반환하는 것을 볼 수 있습니다. 선형 검색을 사용하도록 검색을 다시 작성하고 true를 반환합니다. , 값이 값에 있으면 false 값이 값에 없으면 false입니다. n이 양수가 아니면 즉시 false를 반환하도록 주의하세요. 유효성을 확인할 준비가 되면 다음 명령을 호출해 보세요. 인쇄된 숫자 중 하나 이므로 50이 시드되었을 때 생성은 127이므로 코드는 바늘을 찾아야 합니다! 대조를 위해 다음 명령을 시도하십시오: 128은 50이 시드되었을 때 생성에 의해 생성된 숫자 세트에 포함되지 않으므로 코드는 "바늘"을 찾지 않아야 합니다. . 일부 시드를 사용하여 생성을 실행하고, 출력을 분석하고, 건초 더미에 있어야 할 바늘을 찾아 다른 테스트를 실행합니다. find.c의 main은 find가 "바늘"을 찾으면 0을 반환하고 그렇지 않으면 1을 반환하는 방식으로 작성되었습니다. 다른 것을 실행한 후 main이 실행될 때 반환하는 소위 "출력 코드"를 확인할 수 있습니다. 명령 . 예를 들어, 검색 구현이 올바른 경우 실행하면 0이 표시되고 127은 시드 50으로 생성하여 출력한 1000개 숫자 중 하나이므로 작성한 검색은 true를 반환해야 합니다. 이 경우 main(우리가 작성한)은 0(즉, 종료)을 반환해야 합니다. 다음과 같이 입력하면 128이 생성에 의해 출력된 1000개의 숫자 중 시드 50이 아니기 때문에 1이 표시됩니다. 이 경우 검색(귀하가 작성한)은 false를 반환하고 기본(저희가 작성한) )는 1을 반환하고 (그런 다음 작업을 완료합니다) 논리를 이해하시나요? check50을 사용하여 모든 것을 확인할 준비가 되면 다음 명령을 실행합니다. ./generate 1000 50 | ./find 127./generate 1000 50 | ./find 128echo $?./generate 1000 50 | ./find 127 echo $?./generate 1000 50 | ./find 128 echo $?check50 2015.fall.pset3.find helpers.c 그런데 직접 테스트하기 전에 check50을 사용하여 코드를 테스트하는 데 익숙해지면 안 됩니다. 결국, check50은 실제로 존재하지 않으므로 자신의 입력 샘플로 코드를 실행하고 실제 출력을 예상 출력과 비교하는 것이 이 시점에서 얻을 수 있는 가장 좋은 습관입니다. 사실입니다. 중독되지 마세요! cs50 도우미의 find 구현을 가지고 놀고 싶다면 다음 명령을 실행하세요. ~cs50/pset3/find
정렬
선형 검색은 정말 인상적인 것이 아니지만 첫 번째 강의에서(7번째 강의에서 이 트릭을 다시 반복했습니다!) 건초 더미에서 바늘을 훨씬 더 빨리 찾을 수 있다는 것을 기억하실 것입니다. 하지만 먼저 건초 더미를 정리해야 합니다. find.c는 helpers.h 에 선언된 함수인 sort를 호출 합니다 . 불행하게도 우리는 helpers.c 에서 이 기능을 완전히 구현하는 것을 "잊었습니다" ! helpers.c를 살펴보면 find의 주 함수가 실제로 실제 배열을 전달하더라도 해당 정렬이 즉시 반환되는 것을 볼 수 있습니다. 이제 배열 선언 구문을 기억하세요. 이 배열의 요소 유형을 지정할 뿐만 아니라 대괄호로 크기도 지정합니다. 이것이 find.c 에서 haystack에 대해 수행하는 작업입니다 . 하지만 배열을 순회할 때는 배열 이름만 지정하면 됩니다. 그리고 find.c 에서 정렬을 수행하기 위해 haystack을 통과할 때와 똑같은 방식으로 수행합니다 . (왜 해당 배열의 크기를 별도로 전달하는지 추측해 보세요.) 1차원 배열을 인수로 사용하는 함수를 선언할 때, 배열의 크기를 지정할 필요가 없습니다. 마찬가지로 helpers.h(및 helpers.c)에서 sort를 선언할 때 이 작업을 수행하지 않았습니다. 함수가 실제로 숫자 배열을 작은 것부터 큰 것까지 정렬하도록 sort를 구현합니다. O(n 2 ) 와 동일한 실행 시간이 필요합니다 . 여기서 n은 배열의 크기입니다. 3주차에 배운 대로 버블 정렬, 선택 정렬 또는 삽입 정렬을 구현하고 싶을 것입니다. 그러나 이러한 알고리즘을 구현하는 "올바른" 방법은 없다는 점에 유의하는 것이 중요합니다. 엄청난 수의 변형이 있습니다. 실제로 구현이 O(n2 ) 로 수렴되는 한 적절하다고 판단되면 언제든지 개선할 수 있습니다 . 그러나 실험은 함수 본문에 맡기고 테스트를 단순화하기 위해 정렬 선언을 변경하지 마세요. 다음과 같아야 합니다. 함수가 void 값을 반환하므로 정렬된 배열을 반환하면 안 됩니다. 대신, "실행 중인" 실제 배열을 "파괴적으로" 정렬하여 해당 요소를 이동해야 합니다. 4주차에는 배열이 값이 아닌 참조로 전달된다는 점을 논의하겠습니다. 즉, sort는 배열의 복사본을 받지 않고 원본 배열 자체를 받습니다. 정렬 선언을 변경할 수는 없지만 언제든지 helpers.c에서 자신만의 함수를 정의할 수 있으며, 그런 다음 정렬에서 호출할 수 있습니다. 정렬 구현을 테스트하는 가장 좋은 방법을 스스로 결정하십시오. printf와 GDB가 도움이 될 것임을 잊지 마세요! 그리고 생성 시 시드 값을 명시적으로 지정하여 동일한 의사 난수 시퀀스를 반복해서 생성할 수 있다는 점을 잊지 마세요. int haystack [MAX];sort (haystack, size);void sort (int values [] int n);void sort (int values [] int n);
바이너리 검색, 팁
find 함수 에 대해 가장 먼저 이해해야 할 것은 우리가 이미 코드(배포)를 작성했다는 것입니다. 우리는 단지 기존 코드의 일부 공백을 메울 뿐입니다. find.c 프로그램은 숫자 입력을 요청한 다음(즉, "스택"을 채우기 위해) 사용자의 요청에 따라 helpers.c 에 정의된 정렬 및 검색 기능을 사용하여 "바늘"을 검색합니다 . 따라서 find 는 이미 작성되었으므로 helpers를 작성해야 합니다 . 따라서 우리가 해야 할 일은 다음과 같습니다.
검색을 구현합니다. 이 함수는 스택에 값이 있으면 true를 반환하고, 없으면 false를 반환해야 합니다.
값 배열을 정렬하는 함수인 sort를 구현합니다.
처음에는 검색이 선형으로 구현되었습니다. 하지만 당신은 더 잘할 수 있습니다. 선형 검색 알고리즘은 O(n) 시간 에 실행됩니다 . 당신의 임무는 이진 검색 알고리즘을 작성하는 것입니다. 실행 시간은 O(log n) 입니다 . 그러나 문제는 입력으로 정렬된 데이터가 필요하다는 것입니다. 그렇지 않으면 작동하지 않습니다. 당신은 찢어진 책의 예를 기억하고 아마도 이것이 왜 그런지 알 것입니다. 요소에 대한 이진 검색을 수행했고 더 이상 요소가 남아 있지 않은 경우(즉, 이 "스택"에 "바늘"이 없음) false를 반환하는 함수가 필요합니다. 이진 검색은 반복적으로 또는 재귀적으로 구현될 수 있습니다(David Malan은 8번째 강의에서 재귀에 대해 이야기했습니다).
GO TO FULL VERSION