안드로이드 개발자 이직 공부 #01
자료구조 [Android]
1. 이직 공부
- 자료구조
프로그래밍에서 데이터를 구조적으로 표현하는 방식과
이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론, 혹은 과목.
컴퓨터 과학/공학에서 알고리즘과 함께 가장 중요한 기초이론이다.
제일 싫어했던 과목이에요.
재수강까지 했지만 B+를 넘지 못한...ㅠ
우선 자료구조가 뭔지 찾아봅니다.
구현에 따라
배열 - 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료 값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조이다.
연결 리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
환형 연결 리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
해시 테이블 - 개체가 해시값에 따라 인덱싱 된다.
형태에 따라
- 선형 구조
스택 - 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어넣었다가 꺼내면 역순으로 바뀐다.
큐 - 스택과 반대로 큐 자료 구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
환형 큐 - 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.
덱 - 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.
- 비선형 구조
그래프 - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.
트리 - 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다. 무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.*
이진트리 - 자식이 최대 두 개인 트리.
힙 - 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.
오늘 정리하면서 찾아보니 참 많네요.
저거 몰라도 다 개발하는데..
그래도 면접 때 물어보니 공부해야죠...
온라인 코딩 테스트나 사전과제에 알고리즘 문제를 풀거나 기술면접에서 직접 구현하는 손 코딩을 시키는 경우도 많아요.
연결 리스트를 직접 손 코딩해보세요.
이중 연결 리스트도 해보세요.
개념도 알아야 하지만 직접 구현까지 해야 하다 보니 완벽한 이해가 필요하네요.
저는 동영상 강의를 많이 봤어요.
특히 권오흠 교수님의 강의가 큰 도움이 되었어요.
1. 연결 리스트
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조.
- 단순 연결 리스트 (Singly Linked List)
각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킴.
알고 보면 쉬운 개념입니다.
Node를 만들고 그 안에 Data와 다음 Node 주소를 가지는 구조죠.
그래서 손 코딩도 많이 시키는데요.
문법에 맞는지 보다는 개념을 알고 있나 보는 거 같더라고요.
저는 Java를 이용해서 손 코딩을 했었고요.
아래 블로그처럼 간단하게 구현했어요.
1. 별도의 class나 Inner class로 Node class 구현. (int data, Node nextNode);
2. First(Head) Node를 변수로 가지는 LinkedList class 정의.
3. add(Node newNode), add(Node newNode, int location), remove(int location),
get(int location)
4. Main 함수
보통 1~3번까지 작성하고 설명하면 넘어가더라고요.
- 이중 연결 리스트 (Doubly Linked List)
포인터 공간이 두개가 있고 각 포인터는 앞 뒤 노드를 가리킴.
링크드 리스트는 Node가 단순히 NextNode 자리를 알고 있다면,
더블 링크드 리스트는 PreNode까지 알고 있는 구조입니다.
1. 별도의 class나 Inner class로 Node class 구현. (int data, Node nextNode, Node preNode);
2. First(Head) Node를 변수로 가지는 LinkedList class 정의.
3. add(Node newNode), add(Node newNode, int location), remove(int location),
get(int location)
** add, remove시 preNode도 설정.
4. Main 함수
- 원형 연결 리스트 (Circular linked list)
처음과 마지막 노드를 연결시켜 원형으로 만든 구조.
더블 링크드 리스트에서 처음(Head)과 끝(Tail)이 이어진 구조네요.
여기까지 손 코딩을 시킨 적은 없지만 알아둡시다.
2. 스택
스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있다. 자료를 넣는 것을 '밀어 넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
개인적으로 링크드 리스트보다 쉽네요.
Data를 한 곳으로 Push, Pop 하는 구조입니다.
Android에도 Task라는 stack 형태로 구성된 개념이 있어요.
Last In First Out
3. 큐
큐(queue)는 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.
한쪽 끝에서만 삽입, 삭제는 반대쪽으로만 가능한, 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.
큐도 손 코딩해보세요....
한번 시켰었네요.
First In First Out
4. 트리
트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.
그간 트리를 손 코딩하라는 면접은 없었어요.
링크드 리스트, 스택, 큐와는 달리 좀 더 복잡하거든요.
만약 Heap 정렬을 구현하거나 이진 탐색 트리를 구현해야 한다면 직접 손 코딩하겠지만 그럴 일이 없겠죠?
가끔 트리의 종류를 물어보기도 한데요. (제 친구 경험)
- AVL 트리 : 균형 잡힌(balanced) 이진 탐색 트리이다. 왼쪽과 오른쪽 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다.
- Red-Black 트리 : 레드-블랙 트리는 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한 레드-블랙 트리가 된다
1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드는 블랙이다.
4. 레드 노드의 자식 노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
- B 트리 : 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
- B+ 트리 : B트리와 대조적으로 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. (높이가 2)
5. 그래프
그래프는 GG
그래프까지 손 코딩시키는 건 너무하지 않나요??
그래프 질문이 나오면 모른다 하려고요...
6. 해시
HashMap, HashTable 같은 클래스를 쓰면서도 정작 Hash의 정확한 의미는 잘 몰랐네요.
색인(Index)에 Hash Value를 사용하는, 빠른 검색, 빠른 삽입이
특징인 자료구조이다.
Hash는 HashTable을 이용하여 데이터를 저장한다.
이때 특별한 알고리즘(Hash method)을 이용하여 데이터의 고유한 숫자 값(Hash value)을 만들어 인덱스로 사용한다.
Hash를 쓰는 이유는 데이터 탐색, 삽입, 삭제 시 단순히 Hash method를 통해 Hash value만 구하면 한 번에 할 수 있기 때문이에요.
* 평균 시간 복잡도 : O(1)
* 최악의 경우 : O(N)
해시 알고리즘까지는 검색이나 보안 관련 면접이 아니면 굳이 알 필요 없겠죠?
중복된 해시 코드로 인한 충돌이나 해결법들은 아래 링크를 통해 한 번 알아보세요.
자료구조만 공부할 땐 몰랐는데 알고리즘부터 결국 안드로이드 개발까지 돌이켜보니 다 필요한 개념이네요.
단순한 코더가 아닌 개발자가 되기 위에 기본부터 제대로 공부합시다!
