자료구조 중간 정리

기본 지식

컴퓨터는 메모리에 저장할 떄 입력한 값에 오른쪽에서 부터 왼쪽으로 저장한다

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 이라는 결과를 얻게 된다
부동 소수 저장

1101.101 을 정수 부분 하나만 남긴 체 소수로 이동 1.101101 소수점을 3번 옮겼으니 지수는 2^3
가수 부분 왼쪽에서 부터 소수부분 101101 입력 (나머지는 0으로)
지수 부분에 지수 + 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)
}

Hi! My Name is...

탐색기