cs78 4: 알고리즘-3(선형 검색:Linear Search) 선형검색 찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘 중 하나 선형검색은 원하는 값이 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 방법 효율성과 비효율성 선형 검색 알고리즘은 정확하지만 효율적이지 못한 방법 리스트의 길이가 n일 때, 최악의 경우 리스트의 모든 값을 확인해야 해서 n번만큼 실행됨 최악의 상황(worst case)은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우 선형검색은 자료가 정렬되어 있지 않거나 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용함 정렬은 시간이 오래 걸리고 공간을 더 차지하지만 이 과정을 진행하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시.. 2021. 11. 29. 4: 알고리즘-2(알고리즘 표기법) 알고리즘을 설명하기 위해 특정 표기법을 사용하는 이유(Big-O와 Ω:오메가) - 알고리즘이 얼마나 잘 설계되어 있는지 확인하기 위해 - 코드가 얼마나 잘 구현되었는지 확인하기 위해 - 일반적으로는 Big-O 표기법 사용 n은 일일이 하나씩 다 찾아보는 경우 n/2는 두 칸씩 찾아보는 경우(2,4,6,8...) logn는 이진 탐색처럼 반으로 쪼갠 다음에 거기서부터 비교하는 경우 Big-O 표기법 알고리즘을 수행하는 데 필요한 시간의 상한선을 의미 여기서 대문자 O는 “on the order of”의 약자로, 쉽게 보면 “~만큼의 정도로 커지는”것이라고 볼 수 있음 O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됨. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지기.. 2021. 11. 29. 4: 알고리즘-1(검색 알고리즘) 배열: 한 자료형안에 여러 값들이 메모리상에 모여 있는 구조 - 컴퓨터는 모든 숫자를 한 번에 파악할 수 없어서 배열의 인덱스 하나하나에 다 접근함 - 어떤 값이 배열 안에 있는지를 찾아보기 위해서는 배열이 정렬되어 있는지 여부에 따라 여러 방법을 사용할 수 있음 선형 검색(Linear Search) 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문해 그 값이 속하는지 검사함(처음부터 끝까지 하나씩 순서대로 비교) 의사코드로 아래와 같이 나타낼 수 있음 For i from 0 to n-1 //배열안에 n개의 인덱스가 있고 찾으려는 i요소가 있다. If i'th element if 50 //i요소가 50이라면 return true //True 값 반환 Return false //False값 반환 이.. 2021. 11. 29. 3: 배열-6(명령행 인자:command-line arguments) 명령행 인자: 사용자가 명령행에서 명령을 실행할 때 해당 명령과 함께 지정하는 인자를 의미함 Make나 clang 같은 프로그램 실행 시, 컴파일하려는 코드 외에도 컴파일 후 저장하려는 파일명 등 추가적인 정보를 줄 수 있음(ex. clang -o 같은 것) 명령행 인자를 사용하면 프로그램 실행 후 변수에 값을 저장하는 게 아니라, 프로그램 실행과 동시에 인자가 활용됨 명령행 인자는 자동으로 프로그램의 main 함수에 전달되기 때문에 프로그램 내부의 코드를 사용하지 않고도 데이터를 입력할 수 있음 main도 하나의 함수이다. main() 안에 void라는 인자를 입력하는 대신 int argc, string argv[] 를 정의! #include #include int main(int argc, strin.. 2021. 11. 28. 3: 배열-5(문자열의 활용) 문자열의 길이 및 탐색 사용자로부터 문자열을 입력받아 한 글자씩 출력하는 프로그램을 만들기 For 루프를 통해 문자열의 인덱스를 하나씩 증가시켜가면서 해당하는 문자를 출력하면 됨 #include int main(void) { string s = get_string("Input: "); print("Output: "); for(int i = 0, ???, i++) { printf("%c", s[i]); } print("\n"); } for 루프에서 조건은 문자열의 길이만큼 나와야 함. 그래서 ???조건에서는 i가 문자열의 길이보다 작아야 함 이때 strlen()이라는 함수를 사용할 수 있음! strlen은 문자열의 길이를 알려주는 함수로 라이브러리에 포함되어 있음 를 포함하지 않으면 컴파일할 때 clang.. 2021. 11. 28. 3: 배열-4(문자열과 배열) 문자열(string) 자료형의 데이터 == 문자(char) 자료형의 데이터들의 배열 s는 문자의 배열이기 때문에 메모리 상에 아래 그림과 같이 저장되고, 인덱스로 각 문자에 접근할 수 있음 널 종단 문자(null-terminator): 문자열의 끝을 나타내는 문자로, '\0'라고 정의함 널 종단은 문자열에게 문자열이 끝났고 더 이상의 문자가 남아있지 않다고 말하는 문자 여러 이름이 포함된 names라는 문자열이 선언된 경우 #include #include int main(void) { string names[4]; names[0] = "EMMA"; names[1] = "RODRIGO"; names[2] = "BRIAN"; names[3] = "DAVID"; printf("%s\n", names[0]); .. 2021. 11. 27. 이전 1 ··· 8 9 10 11 12 13 다음
