기본 지식

  • 컴퓨터는 메모리에 저장할 떄 입력한 값에 오른쪽에서 부터 왼쪽으로 저장한다
int num = 0x41424344;	//A B C D 16진수
// 메모리: D C B A
  • 다차원 배열은 1차원으로 매핑 후 메모리에 저장한다
int i = {{ 1, 2, 3 }, { 4, 5, 6 }}
// 메모리: 1, 2, 3, 4, 5, 6 
  • 배열로 다항식 표현
// 3x^10+x+4
{{10, 3}, {1,1}, {0, 4}}
// 지수, 정수 
  • 배열 문자열과 포인터 문자열에 차이
char a[10] = {"hello"} //hello\0, ...빈값
char *a = {"hello"} // hello\0
  • 2의보수

    1. 2진수 반전
    2. 끝에 +1
  • 메모리 영역 구분

    1. 프로그램

      프로그램 코드

    2. 데이터

      전역 변수와 정적 변수 저장

    3. 사용자가 직접 정의 하는 메모리 공간

    4. 스택

      함수에 호출과 관련된 지역변수와 매게변수 저장, 스택이므로 가장 늦게 저장된게 가장 먼저 호출

부동 소수 저장

  • 소수를 2진수로 (저장할 소수: 13.625)

    1. 13 을 2진수로 (1101)
    2. 정수 부분을 때고 0.625 만 남긴다.
    3. 정수 부분이 1로 떨어지거, 똑같은 숫자가 나올때 까지 2를 곱한다. 이때 정수부분은 버리고 계산한다 계산 하면서 나온 정수값에 순서가 소수에 2진수 이다 101
    4. 13을 2진수로 계산한 1101 과 소수 부분을 계산 하면서 나온 값 101 을 합쳐
      1101.101 이라는 결과를 얻게 된다
  • 부동 소수 저장

  1. 1101.101 을 정수 부분 하나만 남긴 체 소수로 이동 1.101101 소수점을 3번 옮겼으니 지수는 2^3
  2. 가수 부분 왼쪽에서 부터 소수부분 101101 입력 (나머지는 0으로)
  3. 지수 부분에 지수 + 127(8비트) 한 수를 2진수로 입력 10000010
    (즉, 아까 구한 지수가 2^3 이니까 3+127 = 130 = 10000010)

로그

log₂8 = 3

  • 해석: 2를 몇번 곱해야 8이 나오는가? 이것이 로그에 정의이자 답
    여기서 2 는 8은 진수 라고 한다.
    결국은 로그는 지수를 찾는 것
  • 빅-오 표기법 에서 O(logN) 은 O(log₂N) 을 줄여서 부르는 것
    즉 정수(밑) 이 2인 상황이다

용어

알고리즘: 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서
(입력, 출력, 명확성, 유한성, 효과성)
힙: 완전 이진 트리로 구성된 자료공간
큐: 선입선출(나중에 온게 먼저 나감) 하는 자료공간
스택: 후입 선출(먼저온게 먼저나감) 하는 자료공간

공간복잡도: 프로그램 실행 시 들어가는 총 용량
시간복잡도: 실행완료 시간

빅-오 표기법: (O(n)): 어떤 수행 작업이 걸리는 시간의 최악의 경우
빅-오메가 표기법: (Ω(n)): 어떤 수행 작업이 걸리는 시간이 최상인 경우
빅-세타 표기법: (θ(n)): 어떤 수행 작업이 걸리는 시간에 평균

  • O(1): 수행 시간이 일정할 때
  • O(n log n): 수행해야하는 양이 두 배로 늘어날 때 올라가는
  • O(n): 수행해야하는 만큼 걸리는 시간이 비례할 때
  • O(2n): 수행해야하는 만큼 걸리는 시간이 2배 일 때
  • O(n^2): 수행해야하는 만큼 걸리는 시간이 재곱 수 일 때
  • O(2^n): 수행해야하는 만큼 걸리는 시간이 2 에 n승일 때

자료 분류

단순 구조

  • 정수, 실수, 문자열 등

선형 구조

  • 순차리스트, 선형리스트, 연결리스트, 큐, 스텍
    (자료 사이의 1대1관계)

비선형 구조

  • 트리, 그래프
    (자료 사이의 1대 N 관계)

선형 이냐 아니냐 이 말은 1 차원이냐 2차원 이냐를 묻는거, 자료가 한쪽 방향으로만 정리된다면 1차원, 아니면 2차원

순차자료 구조와 연결자료 구조

  • 순차 자료구조: 빈 자리 없이 서로 연속하는데로 (배열)

    배열을 이용한 구현

  • 연결 자료구조: 논리적 순서에 의해 저장 (연결리스트)

    포인터를 이용한 구현

시간복잡도

  • 탐색
    • 배열: O(1)
    • 연결리스트: O(n)
  • 추가 및 삭제
    • 배열: 맨앞 = O(n), 맨뒤 = O(1),
    • 연결리스트: 맨앞 = O(1), 맨뒤 = O(n)

재귀함수

정의: 함수 안에서 자기 함수를 호출하는

  • 재귀 함수가 효과 적인 경우 (팩토리얼 계산)
int fact(int a) {
	if (a <= 1) {
		return 1;
	} else {
		return (a * fact(a - 1));
	}
	// 일반적인 반복문 보다 깔끔 하면서 더 빠르다
}
  • 반복 구조 써야 하는 경우 (피보나치 수열)
void main() {
	int temp1 = 1, temp2 = 0, now = 0;
	for (int i = 0; i < 10; i++) {
		printf("%d ", now);
		now = temp1 + temp2;
		temp2 = temp1;
		temp1 = now;
	}
}
  • 재귀함수로 처리할 시
int fib(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return (fib(n - 1) + fib(n - 2));
	// 순환 호출에 비효율
	// 이렇게 되면 fib 함수 실행이 무한대로 늘어남 (2^n)
}