배열
char ‘ ’ String “ ”
여러개의 값을가진 하나의 변수를 만들고 싶을 때 배열을 마든다
int score[3] //정수 3개를 위한 메모리 요청
c언어에서의 상수 선언
const int N = 3;
변수의 이름은 시작점에 대한 정보를 알려준다
문자열이 언제 끝나는지를 알려주는 문자 : null -> \0로 표현
문자열은 컴퓨터가 가진 메모리 용량만큼의 길이 제한이 있다
get_String을 제외하고는 더 큰 값을 입력하면 오류가 발생한다
for(int I =0, n = strlen(s); I < n; I++
if(s[i] >= ‘a’ && s[i] <= ‘z’
strlen은 문자열의 길이를 알려주는 함수로, string.h 라이브러리 안에 포함되어 있다
위 코드는 n이라는 변수에 문자열 s의 길이를 저장하고, 해당 길이 만큼만 for 루프를 순환한다
uppercase : 대문자 toUpper
명령행 인자 : command-line arguments
argc는 main 함수가 받게 될 입력의 개수이다
그리고 argv[]는 그 입력이 포함되어 있는 배열을 의미한다
argv[0]는 기본적으로 프로그램의 이름으로 저장
int main(int argc, string argv[]) 인자들의 배열(인자벡터)
선형 탐색 알고리즘 -> 왼쪽에서 오른쪽까지 순차적으로 검색
숫자가 정렬되지 않은 상태에서 하나하나 확인한다
이진 탐색 알고리즘 -> 정렬되어 있는 상태에서 반을 나눠서 효율적 검색(탐색)
배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복한다
알고리즘은 직선으로 그려지는 선형방식이나
곡선으로 그려지는 이진탐색 방식이 있다
코드의 효율성을 묻는다면 O(n) O(log n) O(n/2) 의 형식으로 대답한다
-> 빅 O 표기법이라고 함
O : on the order of의 약자 ~만큼의 정도로 커지는 것을 의미
선형검색은 모든 경우를 확인하기 때문에 O(n)이고
이진 탐색은 나눠서 찾기 때문에 O(log n)이다
운이 좋아 한번에 찾는 경우 O(1)이라고 표기한다
Ω(오메가)은 빅 O와 반대되는 개념이다
-> Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면,
반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것이다
**상한이 낮은 알고리즘이 더 좋기 때문에 Big O를 더 고려해야 한다
버블정렬 : 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다
배열순서가 임의일 때는 비효율적이고 정렬 되어있을 때 효율적이다
상한 : O(n^2) 하한 : Ω(n)
선택 정렬 : 매번 목표를 세워 가장 작은 값을 순차적으로 찾는다
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다
앞에 놓인 수만 알 수 있어서 최선의 경우에도 같은 시간이 걸린다
상한 : O(n^2) 하한 : Ω(n^2)
**(n^2) = n의 2제곱을 의미한다
재귀(recursion) 호출 : 함수가 본인 스스로를 호출해서 사용 = 내부에서 자기 자신을 호출
병합정렬 알고리즘
입력으로 어떤 배열의 정보가 입력되었을 때,
원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다
숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고,
각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문에
상한 O(n log n) 하한 Ω(n log n)이다
왼쪽 정렬 + 오른쪽 정렬 -> 병합
무언가를 계속 반으로 나누는 알고리즘 : 로그
실행이 빠른 순서
O(1) > O(log n) > O(n) > O(n log n) > O(n+1) > O(n^2)
같은 입력에 대한 알고리즘마다의 출력차이가 어느정도인지를 보며
무엇이 효율적인지 파악해야한다
메모리
메모리를 다룰때는 16진수를 사용한다
00(16 1) == FF
16진수를 사용할 때는 모든 수 앞에 0x를 붙인다 : hex
&n ~의 주소 //C언어에서 사용
%p 주소를 출력
변수의 타입을 모를 때는 char float등 우리가 추정해서 사용해야 한다
16진수를 사용하면 10진수보다 2진수를 간단하게 나타낼 수 있다
&n으로 n의 주소 불러오기
어떤 변수에 주소를 저장하고 싶다면
자료형 뿐만 아니라 별 연산자 또한 적어야 한다 *p : 포인터
문자열 = 포인터
int *p = &n; 정수의 주소를 저장
typedef : 다양한 변수를 묶음
typedef chat *string; string 어떤 char변수를 가지고 있는 문자
&s[0] 첫 번째 문자의 주소 확인
여러 문자의 묶음을 추상화 한 것 = 문자열
문자열은 결국 문자의 배열이고, s[0], s[1], s[2], … 와 같이 하나의 문자가 배열의 한 부분을 나타낸다
\0은 0으로 이루어진 바이트로, 문자열의 끝을 표시하는 약속이다
char *를 사용하는 것보다 string 자료형을 사용하는 것이 추상화가 더 잘 되어있어 가독성이 뛰어나다.
= 직관적이다
*s 해당주소로 이동
왜 s를 출력하면 전체를 출력하는가?
-> printf의 특성이다