1. 자료구조란
- 데이터를 저장하고 관리하는 방식
데이터를 저장하고 관리하는 방식을 자료구조라고 함
자료구조는 데이터를 체계적으로 저장하여 메모리를 효율적으로 사용할 수 있게 하고, 빠르고 안정적으로 데이터를 처리할 수 있도록 도와줌
예를 들어 보자면
변수가 많다면 하나하나 저장하기가 힘드니까, 비슷한 성질의 데이터를 모아서
array자료 구조 같은 걸 사용해서 더 효율적으로 관리할 수 있음.
우리가 앞으로 배울 자료구조들은 아래 구조를 보면 알 수 있음.
메모리에는 크게 하드디스크와 램 메모리가 있음
우리가 코딩을 하고 저장 버튼을 누르면 코드들이 하드디스크에 저장이 됨
저장된 코드를 실행하면 램 메모리에 데이터가 올라가게 됨
우리의 관심사는 램 메모리에 있는데 만약에 우리가 비효율적인 자료 구조를 사용하면 램 메모리 낭비를 초래하고 프로그램 성능 저하의 원인이 됨, 그래서 용도와 상황에 맞는 자료 구조를 잘 선택해야 됨
1-1. Array
List를 잠깐 보자면 데이터를 순차적으로 나열해 놓은 집합임
LIST를 각각을 하나의 문자라고 생각했을 때, Array로 구현한다면 데이터가 메모리상에 연속되게 저장이 됨
1-2. Linked List
Linked List로 구현을 한다면 그림처럼 메모리상에 불연속적으로 저장이 되지만, 다음 데이터의 위치를 가리킴으로써 연속성을 유지할 수 있음
Array는 데이터 접근이 쉽고 Linked List는 데이터 추가가 쉬움
2. 메모리
자료구조를 공부하기에 앞서 메모리에 대해서 알아보자면
RAM 메모리는 전기신호를 저장할 수 있는 트랜지스터라는 작은 반도체 소자로 이우어져 있음
트랜지서트에 전기가 ON 되면 1, OFF 되면 0을 나타냄
이를 이용해서 이진수, 즉 binary digit 0과 1을 표현할 수 있음 이를 bit라고 함
여기서 2bit는 몇가지를 숫자를 표현할 수 있을까?
00, 01, 10, 11 총 4가지의 숫자를 표현할 수 있음
그럼 8bit는 총 몇가지를 표현할 수 있을까? 먼저 8bit는 1byte라고 함
총 2^8가지 저장할 수 있음
이처럼 컴퓨터는 이진법(binary)을 사용하기 때문에 제대로 알고 넘어가야 됨
이와 더불어 16진법, 즉 헥사데시멀(hexadecimal)도 같이 살펴보자
이진수는 보통 2진수에 0b를 붙이고 16진수에는 0x를 붙임
8자리 이진수는 0부터 25까지 숫자를 표현할 수 있음
217은 이진수로 표현하면 1101 1001이 됨
16진수로 217을 나타내자면, 위의 표를 참고했을 때 0xD9가 됨
데이터의 기본 단위인 비트랑 바이트에 대해 알게 됐으니 이제 본격적으로 실제 우리 컴퓨터의 램이 얼마만큼의 비트를 저장할 수 있는지 한번 확인해 보자
만약에 내 노트북 램 메모리가 1MB 메모리를 사용한다고 가정했을 때
-> 메모리 단위란? 컴퓨터는 우리가 알고 있듯이 bit단위로 저장하는데, 이게 가장 작은 단위임.
-> 그 단위를 점점 크게 묶어서 우리가 보기 쉽게 만든 게 바이트, 킬로 바이트(KB), 메가바이트(MB) 같은 단위들임
8 bit, 즉 1바이트가 있는데 1바이트가 1024개 모이면 1KB(키로바이트 = 1,024 Byte )가 됨
1KB가 1024개가 모이면 1MB( 1,024 KB = 1,048,576 Byte )가 됨
-> 1,048,576개의 바이트 공간을 쓴다는 것은 100만 개 정도 문자를 저장할 수 있는 크기라는 의미
1GB로 할 수 있는 것들
| 📄 워드 문서 (글자만 있는 경우) | 100KB ~ 1MB |
| 🖼️ 사진 (고화질 1장) | 약 2~5MB |
| 🎵 음악 (MP3 1곡) | 약 3~5MB |
| 📹 동영상 (HD 영화 1편) | 약 700MB~1.5GB |
| 📱 모바일 앱 (일반) | 50MB ~ 300MB |
| 📱 게임 앱 | 500MB ~ 3GB 이상 |
이 넓은 메모리 공간 속에서 컴퓨터가 데이터를 찾으려면 어떤 지표가 있어야 됨
그래서 하나하나의 바이트마다 주소값을 달아놨음. 10진법으로 표현하기엔 너무 길어지기 때문에 16진법으로 주소를 표시할 것
첫 번째 바이트는 0x0, 두 번째 바이트는 0x1, 마지막으로 2^20은 0xFFFFF가 될 수 있음
10진수 16진수
| 0 | 0x0 |
| 1 | 0x1 |
| 10 | 0xA |
| 15 | 0xF |
| 16 | 0x10 |
| 255 | 0xFF |
2-1. 메모리 할당
이번에는 메모리 할당에 대해서 알아보자
c언어에서는 정수를 저장하는 int 데이터 타입이 있음
int는 메모리에서 4byte를 차지하게 되는데
int price = 290000000;
10진수: 290,000,000
2진수: 0001 0001 0100 0100 0010 0100 0000 0000
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
총 32비트 = 4바이트이라는 2억 9천만 이라는 숫자를 저장해 본다고 했을 때
2억 9천만을 바이너리로 변환하고 4byte씩 나눠서 저장됨
Array는 메모리 상에서 연속적으로 할당됨
만약 1,2,3,4라는 인트형 변수 4개를 묶어서 저장하고 싶다면 이렇게 배열을 선언할 수 있음
int array[4] = {1, 2, 3, 4};
하나하나가 int형 변수이기 때문에 각각 4바이트씩 총 16바이트의 메모리를 차지함
메모리에서 연속적으로 할당하기 위해 16바이트의 메모리에 1,2,3,4를 이진법으로 저장을 하면 됨
각 데이터는 가장 작은 address를 대표 어드레스로 설정함
이번에 Linked List를 한번 본다고 했을 때
LinkedList는 Array와 다르게 메모리상에서 불연속적으로 저장이 됨
값만 저장한다면 1 다음의 값을 알 수 없음
그래서 value와 address를 같이 저장하는데 -> 노드라고 함
address의 메모리는 편의상 4바이트를 차지한다고 가정해 보면 하나의 노드당 메모리는 8byte가 됨
Linked List는 메모리상 불규칙하게 할당되어 있지만 다음 주소값이 적혀있기 때문에 연결된 채로 연속성을 유지할 수 있음
2. 알고리즘 algorithm
- 문제 해결 방법: 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법
- 자주 쓰이는 문제 해결 방법은 패턴화
-> BFS, DFS, Binary Search, Dijkstra 등
- 한 문제에 해결할 수 있는 알고리즘은 다양함
-> 각 문제에 적합한 알고리즘을 선택할 수 있어야 함
-> 알고리즘을 평가할 수 있어야 함
알고리즘 평가 기준
- 시간 복잡도(Time Complexity)
- 공간 복잡도(Space Complexity)
- 구현 복잡도
시간복잡도와 공간복잡도는 보통 trade-off 관계임. 실행시간을 줄이기 위해서는 메모리를 더 사용해야 하고, 메모리 사용량을 줄이다 보면 실행시간이 늘어나게 됨. 코딩 테스트에서는 보통 실행시간을 줄이는 게 중요하기 때문에 메모리를 사용해서 실행시간을 줄이는 방법들을 배울 예정, 구현하기 쉬운 알고리즘을 선택하는 것도 중요
-> 다음 블로그에서는 시간 복잡도에 대해 공부할 예정