[필기,면접] 배열, 문자열 인코딩

이번에는 배열과 문자열 인코딩에 관한 내용을 잠깐 살펴볼 것이다. 필기시험이나 면접에서 질문받은적은 거이 없지만 기본내용이고 책에서 소개하고 있기에 간단하게 정리하였다. 책 내용을 바탕으로 또 알아야 할 부분에 대해 잠깐 살펴보자

배열 : 어떤 메모리 블록에 연속적으로 나열된 같은 유형의 변수모음

연결리스트와 마찬가지로 선형적 저장, 특징은 다르다

탐색 연산은 O(1) - 인덱스만 알면 바로 찾음, 삭제ㅡ삽입이 느림 O(n), 

*포인터 상수 :  char *const ptr  -> 다른 위치를 가리키는걸 바꿀 수 없다, 포인터가 가리키는 메모리 내용(char) 변경가능

 상수 포인터 :  const char* ptr  -> 다른 위치를 가리키는걸 바꿀 수 있지만, 그 메모리의 내용을 변결할 순 없다.

문자열 : C/C++ char : 1byte   JAVA, C# char : 2byte

인코딩

ASCII : 7bit구성, 128개(2^7)개의 문자표현 ->(확장) ANSI : 8bit, 언어별로 code값 줌 code page를 통해 다른언어 사용가능'

EUC-KR : 완성형 코드, 완성된 문자 하나하나마다 코드번호 부여 --> (확장) CP949(MS949) : 한글지원을 위한 윈도우즈 계열 확장 완성형 코드조합 

UTF-8 : 유니코드를 위한 가변길이 문자 인코딩(멀티바이트) 방식, 멀티 바이트개념으로 하나의 Charator set에 모든 문자 넣음

        최대 4개까지 8bit char로 모든 유니코드 인코딩

        네트워크를 통해 전송되는 텍스트나 파일에 저장된 테스트 용도

*멀티바이트*

표현해야하는 문자에 따라 글자 크기를 가변으로 변경하여 사용, UTF-8은 1~4byte로 변함, 한글언어는 3byte이상을 사용

UTF-16 : JAVA, C#에서 사용, 16bit를 기반으로 저장하는 UTF-8 변형

UTF-32 : 모든 문자를 4byte로 인코딩, 비효율적으로 메모리 사용

*UTF-8, UTF-16 모두 유니코드를 지원하기 위한 인코딩 방식

유니코드 : 전 세계 모든 문자를 컴퓨터에서 일관되게 표현하도록 만들어진 코드조합

위 내용이 책에서 언급한 내용들이다. 자료구조 파트에서 배열에 대해 설명하였는데 작년에 많이 봤던 문항은 Vector와 List의 차이를 많이 물었다. 그 내용을 찾아보면 

출처 : Stack Overflow 번역본 및 기타정리

Vector : 연속적인 메모리, 즉, iterator 뿐 아니라 position index(operator [])로도 접근이 가능하다는 것이다. 

•            개별 원소들을 position index로 접근이 가능하다 (상수 복잡도)
•            원소를 컨테이너의 끝에 삽입/제거 하는 것이 빠르다 (상수-아모타이즈드 복잡도) -> 다른 위치는 O(n)
•            어떠한 순서로도 원소들을 순회할 수 있다. 즉, Random access iterating이 가능함. (로그 복잡도)
•            동적으로 컨테이너의 크기가 확장/축소되는 것이 편하기는 하나, 확장시의 reallocation은 비용이 꽤 크다.
•             capacity를 확장 시켜줄 수 있는 적절한 크기의 reserve로 인한 메모리 확보가 중요.

List : list는 doubly linked list로 구현되어 있다. (비연속적인 메모리) 

       메모리 선할당을 하지 않는다. 메모리 그 자신을 위한 메모리 오버헤드는 상수다.

       원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용된다.
       추가와 제거에 비용이 싸고, 리스트 어디서든 일어날 수 있다. 

        요소를 추가할 때, 전체 리스트의 메모리를 재할당할 필요가 없다.

        컨테이너 내 원소 순회는 forward / reverse 순회만 가능하며, 느리다. (선형 복잡도)

결론 : 순차적인 컨테이너 타입을 사용할지 신경쓰지 않을 땐 벡터를 사용해라, 그러나 컨테이너의 끝 이외의 곳에 추가와 제거가 많이 일어난다면 리스트를 사용하길 원할 것이다. 혹은 네가 랜덤 접근이 필요하다면, 벡터를 원할것이고 이외의 경우는 리스트이다.

만약 요소를 추가하는 게 빈번하지 않는다면, 벡터가 더 효율적일 것이다. 벡터는 리스트 보다 더 좋은 CPU 캐시 지역화를 가진다. 다르게 말하자면, 한 요소에 접근하는 것은 캐시 안에 다음 요소가 존재하고 다음 캐시가 느린 RAM을 읽을 필요 없이 검색 될 수 있을 가능성이 높게 만든다.

다만, 자료구조의 성능을 비교할 때는 원소의 크기, 지역성에 의한 캐시 미스를 잊지 말자, 또한 어떤 상황이고 원하는 작업이 무엇인지 등을 파악하여 생각해야 한다.

그 외, 다른 자료구조의 내용이 필요하다면 링크를 남겨놓겠다.

자료구조 내용 링크 : https://geekhub.tistory.com/61?category=722520