분류 전체보기 (79) 썸네일형 리스트형 경우의 수(합의 법칙, 곱의 법칙) 순열에 대한 강의는 아래와 같은 순서로 읽으시면 됩니다. 목차 경우의 수(합의 법칙, 곱의 법칙) B 2가지 경로 x B->D 3가지 경로를 곱한다 : 3 x 2 = 6 A->C->D 로 가는 것은 동시에 일어나니 A->C 3가지 경로 x B->D 2가지 경로를 곱한다 : 4 x 2 = 8 근데 A->B->D 와 A->C->D 로 가는 경로는 동시에 일어날수 없으므로 6 + 8 = 14가 됩니다. 곱의 법칙, 합의법칙 기본개념 끝. 레퍼런스 수학중독- 경우의 수-합의 법칙, 곱의 법칙 균형 이진탐색트리(Balanced Binary Search Tree) 트리에서는 기본적인 트리 자료구조에 대해서 알아 보았고 이어서 자식이 2개 이하로만 구성되어 있는 이진트리(Binary Tree) 그리고 이진트리 중 검색을 매우 빠르게 할 수 있는 자료구조인 이진탐색트리(Binary Search Tree) 까지 하나씩 살펴보았다. 여기서 부모의 노드보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 추가하면서 서브트리가 계속 구성되어지는 이진탐색트리는 치명적인 단점이 있다는것인데 자료가 많아질수록 트리의 높이(height)가 커지기 때문에 검색에 불리해지고 최악의 경우 (worst case) 노드는 탐색하는데 log(n) 이 소요될수도 있다. 예를들어 지금까지 배운 방식대로 1 , 2, 3, 4 를 이진트리에 추가한다면 그림1 처럼 된다. 그림1 에서 4를 찾는다면 4번의 탐.. 비트셋(BitSet) 배열(Array)다음에 링크드리스트(LinkedList)를 이어서 설명하려 하였으나 비트셋이 배열 다음으로 어울릴것 같아서 비트셋(Bitset)부터 먼저 설명하려고한다. 우리가 SW를 만들(또는 구현)때 가장 많이 고려해야 할 것들은 무엇일까? 개인마다 차이는 있겠지만 아래의 것들을 고려해야 해야 한다는 것에 어느정도 공감할 것이다. 1. 퍼포먼스가 좋고. 즉, 속도가 빠르고 2. 메모리(=리소스)를 적게 사용하고 3. 버그는 없으며 4. 코드는 간결하고 5. 유지보수는 쉽고 확작성은 열려있게 설계해야 하고 6. 가독성(Readability)도 좋고 7. 오픈소스로 제공하면 좋고 ... 공짜면 더 좋고 ^^ .. 등등 ... 그런데 보통 SW작성시 1번과 2번은 대부분 대립각을 세운다. 즉, 퍼포먼스(속.. 배열(Array) 배열은 프로그래밍시 가장 자주 사용되는 자료구조다. 자바에서 배열을 선언은 아래처럼 한다. 1 2 // 선언과 동시에 초기화. int []elements = { 15, 7, 11, 44, 93, 20}; 배열의 특성을 알기 위해서 위와 같이 선언시 컴퓨터 메모리에 어떻게 저장되는지 이해할 필요가 있어 아래 그림 기준으로 설명한다. 우선 컴퓨터 내부적으로는 6개의 정수를 저장할 메모리 공간을 할당한다. 자바에서 integer는 4bytes 이므로 총 6x4 = 24bytes를 할당하게 될 것이다. 핵심은 이렇게 할당된 메모리 공간은 연속되어 있다는 것이다. 즉, 위 그림은 보면 메모리 주소가 address = 1100 에서 4bytes씩 address=1120까지 연속(4bytes씩 증가하면서 끊기지 않고.. 링크드리스트(LinkedList) 배열(Array)에서 설명한것 처럼 뱌열은 랜덤엑세스 속도( O(c)) 에 유리하지만 중간에 삽입하거나 삭제하는경우 또는 맨 뒤에 추가할때 저장 할 사이즈가 부족하면 메모리를 재 할당하고 (메모리 할당과 해제는 cost 가 있음) 배열의 인덱스를 다시 얼라인(or reposition)해야 하는 오퍼레이션(operation)들이 필요하다. 그럼 중간이던 끝이던 앞이던 삭제하고 추가하는데 유리한 자료구조는 없을까 ? 링크드리스트(LinkedList)는 배열의 장점을 포기하고 단점을 보완할수 있는 자료구조를 가지고 있다. 링크드리스트의 종류는 여러가지가 있는데 그 중 가장 심플한 단일 링크드리스트부터 설명하겠다. 단일 연결 리스트(Single LinkedList) 더블 연결 리스트(Doubly LinkedLi.. 해시테이블(Hash Table) 해시테이블은 특정 키(key)에 값(value)을 매칭(matching)해 저장해 놓는 자료구조로 키값에 매칭된 값을 검색 할 때 매우 빠른 속도 O(c) 를 보장한다. 실무에서도 매우 자주 사용되는 자료구조로 해시맵(hashmap) 또는 연관배열 (associative array) , 맵(map), 딕션너리(dictionary) 등으로 불리기도 한다. 해시테이블 자료구조에서 매우 중요한 핵심은 해시함수(hash function)이다. 해시테이블에서는 자료를 배열(해시테이블에서는 이 배열을 보통 버킷(bucket) or 슬롯(slot)이라 부른다.) 에 저장하는데 키가 버킷(배열)의 몇 번째 index에 해당하는지 확인하기위해 해시함수를 사용하기 때문이다. 구현을 통해서 자세히 알아보자. 키값이 inte.. 셋(Set) 셋(Set)은 해시테이블(HashTable)을 통해 구현되어지기 때문에 추가, 삭제, 검색에 대한 성능도 해시테이블과 동일 ( 평균적으로 O(c) )하다. 문제는 면접때 셋이 뭐할때 쓴느건가요? 라고 물어보면 십중팔구는 특정 키가 있는지 없는지 검사할때 사용한다고 대답한다. 이렇게 대답하는 사람들은 대부분 셋을 실무에서 키가 있는지 없는지 유무를 검사하는 경우만 했을 가능성이 크다. 사실 맞는 말이기도 하고 실무에서 셋을 키 우뮤를 판단하는데 많이 사용하기 때문에 자연스럽게 나오는 대답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.HashSet; import java.util.Set; public class Main { publ.. 덱(Deque) 덱(Deque 이전 1 ··· 6 7 8 9 10 다음
