전체 글117 5. Map & Dictionary Map이란? Map은 key-value 형태로 데이터를 저장하는 자료구조이며, key 값을 통해서 데이터를 검색, 저장, 삭제한다. 이 때, map은 중복된 key 값은 허용되지 않는다. 예를 들어, 전화번호부의 경우 같은 전화번호에 여러 이름은 저장되지 않는다. 따라서 전화번호를 key 값으로, 이름을 value로 map에 저장하면 된다. Dictionary란? Dictionary는 기본적으로 map과 같이 key-value 형태로 데이터를 저장하지만, map과 달리 중복된 key 값이 허용된다. 예를 들어 단어 사전의 경우 하나의 단어에 여러 가지 뜻이 있을 수 있다. 따라서 단어를 key 값으로, 단어의 뜻을 value로 dictionary에 저장하면 된다. 그렇다면 List를 기반으로 Map을 구.. 2020. 5. 22. 4. Priority Queue & Heap Priority Queue란? Queue의 경우 먼저 들어간 데이터가 먼저 나오게 된다. Priority Queue는 이와 다르게 들어간 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다. 그렇다면 Priority Queue를 어떻게 구현해야 할까? 첫번째, 배열로 구현하여 삽입 시마다 우선순위에 맞게 정렬한다. 이 방법은 항상 정렬된 형태를 유지하기 때문에 데이터를 꺼낼 때 용이하지만, 삽입 시 O(n)의 시간이 필요하다. 두번째, 리스트로 구현하여 데이터를 불러올 때 우선순위가 높은 데이터를 찾는다. 이 방법은 삽입 시 상수 시간이 걸려 용이하지만, 데이터를 꺼낼 때마다 O(n)의 시간이 필요하다. 이처럼 배열과 리스트로 Priority Queue를 구현하면 이와 같이 데이터 삽입이나 요청.. 2020. 5. 22. 3-2. Tree Traversal Tree의 노드들을 탐색하는 데에는 여러 가지 방법이 있다. 기본적으로 노드를 방문하는 순서에 따라 preorder, postorder, inorder traversal이 있고, 이 외에도 level-order traversal, Euler tour traversal 등 여러 가지 순회 방식이 있다. 하나씩 순회 과정을 살펴보자. Preorder Traversal (전위 순회) 전위 순회는 현재 노드를 먼저 탐색하기 때문에 붙여진 이름이다. 따라서 1.현재 노드 2. 왼쪽 child 노드부터 차례대로 순으로 방문하게 된다. 실제 위 트리를 예시로 전위 순회를 실행해보자. 먼저 root 노드인 0번 노드를 방문하고, 그 다음으로 left child인 1번 노드를 방문하게 된다. 1번 노드를 방문했다면, 다.. 2020. 5. 21. 3-1. Binary Tree Binary Tree Binary Tree(이진 트리)는 각각의 노드가 최대 2개의 child 노드를 갖는 tree를 말한다. 이진 트리는 노드들이 어떻게 구성되어 있는지에 따라 다음과 같이 부르기도 한다. Full Binary Tree (정 이진 트리) 모든 노드가 0 또는 2개의 child를 갖는 binary tree. Perfect Binary Tree (포화 이진 트리) 모든 internal 노드가 2개의 child를 갖는 binary tree. 모든 leaf 노드가 같은 level에 있다. (Proper Binary Tree라고도 함) Degenerate Tree (변질 트리) 모든 parent 노드가 하나의 child만 갖고 있는 tree. (Pathological Tree라고도 함) Comp.. 2020. 5. 21. 3. Tree Tree Tree의 기본적인 정의는 Circuit이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 Graph를 말한다. 따라서 Tree는 Graph의 종류 중 하나이며 다음과 같은 특징을 갖는다. Parent, Child 연결 리스트의 경우 다음 노드 하나를 가리키지만 Tree의 경우 여러 개의 노드를 가리킬 수 있다. 이렇게 가리켜진 노드들을 child 노드라고 하며 가리킨 노드를 parent 노드라고 한다. 예를 들어 4번, 5번 노드는 2번의 child이고, 2번 노드는 4번, 5번 노드의 parent이다. 동시에 5번 노드는 8번 노드의 parent이고, 2번 노드는 0번 노드의 child이다. 이처럼 parent, child 노드는 상대적인 개념이다. 이에 더해 ancestor는 해당 노드의 .. 2020. 5. 18. 2. Queue & Stack Queue Queue는 한글로 번역하면 줄이라는 뜻인데 줄을 서는 원리와 똑같이 동작하기 때문이다. 먼저 들어간 element가 먼저 나오는, First In First Out (FIFO) 형태를 갖는 자료구조이다. 따라서 index에 따라 넣고 빼는 것이 아닌 맨 뒤에 넣거나(enqueue), 맨 앞에서 빼는(dequeue) 것만 가능하다. Enqueue 위와 같이 리스트 형태로 구현된 queue가 있을 때, enqueue를 통해 노드를 추가하고 싶다면 추가할 새 노드를 만들어 준 뒤 맨 뒤 노드의 포인터를 새 노드로 지정해주면 된다. 이 때 마지막 노드의 포인터(tail)를 따로 저장해두지 않으면 처음부터 끝까지 탐색해야 하므로 미리 저장해두어야 한다. 따라서 언제나 위와 같이 상수 시간이 걸리므로 .. 2020. 5. 12. 1. Array & Linked List Array A ordered sequence of elements of the same type 배열이란 같은 형태의 요소들로 이루어진 자료구조를 말하며 다음과 같은 특징이 있다. - 각각의 element들은 index를 통해 참조한다. - 특정 순서에 따라 저장하기에 편리하다. - 미리 크기를 설정해주어야 한다. Search 배열은 i 번째 element를 찾을 때 시작 주소 + ( i × 자료형의 크기 ) 계산만 하면 위치를 찾을 수 있다. 따라서 탐색에 걸리는 시간이 상수이므로 시간복잡도는 O(1)이 된다. Insertion 위와 같은 배열에서 2와 6 사이에 4를 넣고 싶다면 뒤의 모든 element들을 한칸씩 뒤로 옮겨주어야 한다. 따라서 삽입에 element 갯수 n에 비례한 시간이 소모되므로.. 2020. 5. 12. OptionMenu의 item에 actionLayout 지정 시 onOptionsItemSelected() 미작동 문제점 OptionMenu를 구현할 때 item을 icon이 아닌 actionLayout 옵션을 통해 layout을 지정하면, onOptionsItemSelected()가 호출되지 않아 클릭 시 이벤트를 처리할 수 없음. 해결 방법 @Override public boolean onCreateOptionsMenu(Menu menu) { getMenuInflater().inflate(R.menu.menu_sort, menu); for(int i=0; i 2020. 5. 8. Splash 화면 구현하기 Splash 화면이란? 앱을 실행하면 앱의 아이콘이나 간단한 이미지가 들어간 화면이 잠깐 뜨는 경우가 있다. 이 화면을 Splash 화면이라 하며, 어떤 앱인지를 나타내거나 앱을 실행하기 위한 준비를 하기 위해 사용하기도 한다. 구현 방법 일반적으로 Splash 화면을 액티비티로 만들어 일정 시간 후 MainActivity를 띄워주는 방법을 많이 사용한다. 이를 위해 app 우클릭 후 new - Activity - Empty Activity 를 눌러 새 Empty Activity를 생성하자. 그리고 원하는 화면으로 layout을 꾸며보자. 이제 manifest로 가서 intent-filter 내용들을 MainActivity에서 SplashActivity로 옮겨 시작 액티비티를 바꿔주자. SplashAct.. 2020. 5. 8. 이전 1 2 3 4 5 6 7 8 ··· 13 다음
