ASCII 문자열: ASCII 인코딩을 사용하여 문자열을 바이트로 표현할 수 있습니다. 예를 들어, "Hello"라는 문자열은 각 문자를 ASCII 코드에 맞게 바이트로 표현하면 다음과 같습니다:
'H': 72 (01001000)
'e': 101 (01100101)
'l': 108 (01101100)
'l': 108 (01101100)
'o': 111 (01101111)
따라서 "Hello"는 바이트로는 72 101 108 108 111로 표현됩니다.
이미지 파일: 이미지 파일은 픽셀 데이터로 구성되며, 각 픽셀의 색상 정보를 바이트로 표현합니다. 예를 들어, 24비트 컬러 이미지에서 각 픽셀은 빨강(R), 초록(G), 파랑(B)의 성분을 8비트씩 가집니다. 이진수로 표현된 색상 값은 픽셀마다 다양한 바이트로 구성됩니다.
음악 파일: 음악 파일은 소리의 파형 데이터로 구성되며, 일반적으로 디지털 오디오 형식을 사용하여 바이트로 표현됩니다. 각 샘플은 일정한 시간 간격으로 샘플링되고, 이러한 샘플링 데이터는 바이트로 표현됩니다.
실행 파일: 컴퓨터 프로그램은 실행 파일로 저장되고, 이 파일은 기계어로 표현된 바이너리 코드로 구성됩니다. 각 명령어와 데이터는 바이트로 표현되어 컴퓨터의 프로세서가 이를 이해하고 실행할 수 있습니다.
자료의 표현 형식
텍스트 자료의 표현
ASCII
가장 일반적으로 사용되는 문자 인코딩 중 하나는 ASCII (American Standard Code for Information Interchange)입니다.
7비트로 표현된 ASCII 코드는 2^7 = 128개의 고유한 값을 나타낼 수 있습니다. 이는 영어 알파벳, 숫자, 특수 문자 등을 포함한 기본적인 문자 집합을 표현하기에 충분합니다. 초기 컴퓨터 시스템에서는 주로 영문 텍스트를 다루기 때문에 7비트로 구성된 ASCII 코드가 널리 사용되었습니다.
7비트 ASCII는 0부터 127까지의 값을 사용하여 문자를 나타내는데, 예를 들어 'A'는 65, 'a'는 97로 표현됩니다. 나머지 128부터 255까지의 값은 사용되지 않거나, 다른 문자 인코딩 체계에 따라 확장 문자나 특수 문자로 사용될 수 있습니다.
유니코드 와 UTF-8
유니코드(Unicode):
유니코드는 전 세계의 모든 문자를 고유한 코드 포인트로 나타내는 국제 표준입니다.
유니코드는 "U+"로 시작하며, 각 문자는 16진수 값으로 표현된 코드 포인트를 나타냅니다.
각 문자에는 유니코드 코드 포인트라고 불리는 고유한 식별자가 할당됩니다. 이 코드 포인트는 16진수로 표현되며, 예를 들어 "A"는 U+0041과 같이 표현됩니다.
UTF-8(Unicode Transformation Format-8):
UTF-8은 유니코드를 컴퓨터에서 저장하고 전송하기 위한 가변 길이 문자 인코딩 방식입니다.
UTF-8은 ASCII 문자에 대해서는 7비트로 표현하며, 다른 유니코드 문자는 8비트 이상으로 확장하여 표현합니다. 이를 통해 유니코드 문자를 효율적으로 저장하고 전송할 수 있습니다.
UTF-8은 가변 길이 인코딩이기 때문에 유니코드 코드 포인트를 다양한 크기의 바이트 시퀀스로 변환합니다. ASCII 문자는 1바이트로 표현되며, 추가적인 문자는 2바이트부터 최대 4바이트까지 사용될 수 있습니다.
2의 보수 변환을 위해 42의 이진수에 대해 1의 보수를 취합니다. 1의 보수는 0을 1로, 1을 0으로 반전시키는 작업입니다.
42의 1의 보수는 11010101입니다.
00101010를 반전한것
2의 보수:
1의 보수를 취한 결과에 1을 더함으로써 2의 보수를 얻을 수 있습니다.
11010101에 1을 더하면 11010110이 됩니다.
이는 -42를 음수로 표현한 2의 보수 표현입니다.
따라서, 42를 2의 보수로 변환하면 -42로 표현되는 것을 확인할 수 있습니다. 이러한 2의 보수 방식은 부호 있는 정수 표현에서 음수 값을 표현하는 데에 주로 사용됩니다.
자료구조의 동작과 활용
자료구조
Array (배열)
[ 배열의 특징 ]
순서가 있습니다. (메모리 순서대로)
연속된 공간을 '미리' 정해서 사용해야 합니다. (확정된 메모리 공간을 할당받아 써야 하므로)
N번째 데이터에 접근하기 위해 복잡한 과정 필요 없이 그냥 덧셈과 곱셈 한 번이면 가능합니다. (n번째 데이터 접근 : 시작 주소 + (n-1) * 해당 자료형 크기)
Create : 이미 new int [5];로 만들어져 있는 데이터인데 새로운 6번째 데이터를 새로 배열에 넣으려고 한다. 방법은 새로운 연속된 공간을 다시 할당받고 기존에 있던 데이터를 모두 새로운 곳으로 옮기는 방법입니다.
int[] arr = new int[5];
arr[0] = 1;
...// 무언가 넣음int[] tmp = new int[6];
for (int i = 0; i < arr.length; i++) {
tmp[i] = arr[i];
}
arr = tmp;
Read : 몇 번째 데이터라도 덧셈과 곱셈 한 번씩이면 접근할 수 있으므로 매우 빠르게 접근할 수 있습니다.
Update : Read와 마찬가지로 매우 쉽게 접근해서 수정 가능합니다.
Delete : Create처럼 어렵다. int [] arr = new int [5];에서 arr [3]을 제거하려고 할 때, Create의 예시처럼 new int [4]; 를 만든 후 복사해 넣어야 합니다. 혹은 공간 자체는 안 줄여도 된다고 해도 arr [3] 이후의 모든 값을 한 칸씩 앞으로 당겨줘야 합니다. (예외로 배열의 크기를 사용하는 데이터의 개수와 관계없이 유지해도 되고 마지막 데이터를 삭제하는 경우라면 한방에 가능합니다.)
맨앞이나 맨 뒤에 데이터를 확인하거나 바꿀 경우 : O(1) - 일반적으로 이 경우가 많음
❓ 배열은 언제 쓰고 리스트는 언제 쓸까?
결국 시간복잡도와 상황에 맞게 적절하게 사용하면 됩니다.
리스트
일반적으로 데이터의 추가, 삭제가 많은 경우 리스트를 사용하는 것이 효율이 좋습니다.
배열
데이터가 자주 추가, 삭제되지 않고, 읽고 수정하는 경우가 많을 때 배열을 사용하는 것이 효율이 좋습니다.
ArrayList (벡터)
기본 동작 원리 및 CRUD에 따른 효율성은 모두 배열과 동일합니다.
이걸 이해하는 게 매우 중요한 게, 보통 자료구조에 대해 잘 모르고, 자바 자체도 초보인 사람들은 리스트를 처음 사용할 때 ArrayList와 LinkedList 둘 중 대충 아무것이나 쓰고 한번 써봤으니깐 그걸로 앞으로 계속 써버립니다.
당연히 LinkedList와 ArrayList의 CRUD 효율성은 매우 다르므로 아무꺼나 쓰면 매우 비효율적인 코드가 돼버립니다. 자바에서 ArrayList는 배열을 썼을 때 효율적으로 동 잘할 로직을 수행하려고 하는데, 배열의 크기를 모를 때, 혹은 배열로 구현하기 귀찮을 때 어차피 메모리 크기 여유롭면 대충 넣기 좋으니까 사용하는 것입니다.
심지어 배열로 해도 그냥 미리 넉넉하게 만들거나, 다 차면 미리 한 2배 정도로 늘려서 새로 만들어버리면 ArrayList와 동일하게 사용 가능합니다.
Queue, Stack (큐, 스택+덱)
큐 (Queue)
큐는 FIFO(First in First out; 선입 선출)의 특징을 가지는 자료구조이다. 먼저 들어간 데이터가 먼저 나옵니다.
자바의 경우 'Queue<Integer> q = new LinkedList<>();' 와 같이 선언해서 사용 가능합니다.
파이썬은 따로 큐를 제공하지 않는다. 애초에 파이썬은 배열도 없는 판국에 뭐..(심지어 리스트는 linked list가 아님) 파이썬에서 list는일반적으로 Vector(ArrayList)의 형식으로 동작하므로 dequeue에서 시간복잡도가 너무 높아 비효율적이다. 파이썬은 큐도 이후 설명할 deque(덱)를 사용해야 합니다.
**C++**은 STL에 만들어놨습니다.
C는 일단 LinkedList부터 기본적으로 제공되지 않으므로 전부 직접 짜야합니다.
❓ Queue는 어떨 때 쓸까?
현업에서 쓸만한 예시로는 대표적으로 스케쥴링에 쓰인다. 먼저 들어온 작업을 먼저 처리하도록 하는 것입니다.
스택 (Stack)
스택은 LIFO(Last in First out; 후입 선출)의 특징을 가지는 자료구조이다. 나중에 들어간 데이터가 먼저 나옵니다.
마찬가지로 모든 함수의 시간복잡도는 O(1)이어야 합니다.
덱 (Deque = Double-ended Queue)
Double-ended Queue라는 의미로, 양쪽으로 넣고 뺄 수 있는 큐입니다.
당연히 양쪽으로 넣고 뺄 수 있는 스택으로도 쓸 수 있고, 한쪽은 스택 한쪽은 큐로 써도 됩니다.
좀 더 유연한 스택, 큐입니다.
하지만 리스트와 다르게 중간의 데이터를 건드릴 수 없고, 양 끝단만 건드릴 수 있습니다.
Hash Table (맵)
key: value로 저장하는 데이터 구조
키를 통해 바로 데이터를 받아올 수 있어 속도가 획기적으로 빨라짐
해쉬 : 임의 값을 고정 길이로 변환하는 것
해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
해쉬 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
해쉬 값 / 해쉬 주소 : 키를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해뷔 테이블에서 해당 키에 대한 데이터 위치를 일관성 있게 찾을 수 있음
슬롯 : 한 개의 데이터를 저장할 수 있는 공간
저장할 데이터에 대해 키를 추출할 수 있는 별도 함수도 존재할 수 있음
해시(Hash)
데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
해시 함수를 구현하여 데이터 값을 해시 값으로 매핑합니다.
Lee → 해싱함수 → 5
Kim → 해싱함수 → 3
Park → 해싱함수 → 2
...
Chun → 해싱함수 → 5 // Lee와 해싱값 충돌
결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌 나는 현상이 발생함 'collision' 현상
