c++7 이진 탐색 (binary search) 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 -이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 중간점이 두 개라면 소수점 이하를 제거해서 중간점을 설정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log_2*N에 비례 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장 4를 찾는다고 가정 중간점이랑 비교해서 중간보다 값이 작으면 중간점을 포함해서 오른쪽 범위를 볼 필요가 없다 이번에 보면 중간점이랑 비교해서 값이 작기 때문에 중간점을 포함해서 왼쪽 범위를 볼 필요가 없다. 원하는 값을 찾았기 때문.. 2021. 4. 13. 정렬(sorting) 알고리즘 정렬 1. 선택 정렬 처리되지 않은 데이터 중에서 [가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복] 이중 반복문을 통해 구현 선형 시간 소요 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 시간 복잡도 O(N^2) 과정 처리되지 않은 데이터 중 가장 작은 0을 선택해 가장 앞자리 7과 바꿈 처리되지 않은 데이터 중 가장 작은 1을 선택해 가장 앞자리 5과 바꿈 처리되지 않은 데이터 중 가장 작은 2을 선택해 가장 앞자리 9과 바꿈 이 과정을 반복하면 C++ 코드 #include using namespace std; int main(void) { int n = 10; int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 }; for (int i =.. 2021. 4. 13. 재귀(recursive) 함수 재귀 함수 자기 자신을 다시 호출하는 함수 재귀 함수 사용시 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 명시하지 않으면 무한히 호출될 수 있다. 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. - 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수 사용 가능 #include using namespace std; void recursive(int i) { if (i == 100) return; cout 2021. 4. 12. C++에서 문자 형태의 숫자를 입력 받았을 때 숫자 형태로 변경하는 방법 0에서 9까지의 숫자를 문자 형태로 입력 받았을 때 int 형태로 바꾸는 방법 #include #define _CRT_SECURE_NO_WARNINGS using namespace std; int main(void) { char num; scanf_s("%c", &num); printf("받은 숫자 : %c \n", num); printf("아스키코드 : %d \n", num); int change_num = num - '0'; // 숫자형태로 변경 printf("\n\n"); printf("%d\n", change_num); } 2021. 4. 11. 이전 1 2 다음
