본문 바로가기
728x90
반응형

전체 글99

[자료구조] 해시테이블(Hash Table), Dictionary 해시테이블 -Hash는 키 값을 Hash Function으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다. -키 값이 많아지면 매우 많은 배열 공간이 필요한데, 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용한다. -해시 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다. Hashtable 클래스 -.NET에 Hashtable 클래스는 Non-Generic 클래스다. -Hashtable은 key값과 value값 모두 object 타입을 받아들여 박싱/언박싱이 일어난다. -Hashtable은 Double Hashing 방식을 사용하여 Collision Resolution을 하게 된다. -즉 해시 함수를 사용하여 key가 collision(충돌)이 발생하면, 다른 .. 2023. 6. 22.
[자료구조] 연결 리스트(Linked List) Linked List 란? -데이터를 포함하는 노드들을 연결하여 컬렉션을 만든 자료 구조 -각 노드는 데이터와 다음/이전 링크 포인터를 갖게 된다. -단일 연결 리스트(Singly Linked List)는 노드를 다음 링크로만 연결한 리스트 -이중 연결 리스트는 각 노드를 다음 링크와 이전 링크 모두 연결한 리스트 -Circular Linked List(순환 연결 리스트)는 마지막 노드의 다음 링크가 맨 처음 노드를 가리키게 연결한 리스트 LinkedList 클래스 -.NET에서 LinkedList 클래스는 이중 링크드 리스트로 구현되어 있다. -LinkedListNode 클래스는 리스트 노드를 표현한다. -AddFirst, AddLast, AddBefore, AddAfter등으로 링크스 리스트 맨 앞,.. 2023. 6. 22.
[자료구조] 시간 복잡도 정리 자료 구조 삽입 검색 삭제 인덱스 접근 T[] O(n) O(n) O(n) O(1) List O(1) O(n) O(n) O(1) LinkedList O(1) O(n) O(n) O(n) Dictionary O(1) O(1) O(1) - SortedDictionary O(log n) O(log n) O(log n) - HashSet O(1) O(1) O(1) - SortedSet O(log n) O(log n) O(log n) - Stack O(1) - O(1) - Queue O(1) - O(1) - 2023. 6. 21.
[자료구조] 동적 배열(Dynamic Array) 동적 배열의 필요성 -배열은 고정된 크기의 연속된 배열 요소들의 집합이므로 배열을 초기화 시 미리 배열의 크기를 정해야 한다. -그러나 때론 미리 이 크기를 정할수 없는 경우가 있고, 중간에 배열을 확장해야 하는 경우가 있다. -이런 상황에 사용하는 것이 동적 배열이며 .NET에는 ArrayList와 List가 있다. 동적 배열의 시간 복잡도 -배열(정적 배열)과 같이 인덱스를 통해 한 요소에 접근시 O(1) -배열의 요소 개수 n개에 대하여 특정 값을 탐색하는 시간 O(n) ArrayList 클래스 -모든 배열 요소가 object 타입인 Non-Generic 동적 배열 클래스다. -.Net의 Non-Generic클래스들은 System.Collections namespace 안에 있다. -박싱(value.. 2023. 6. 21.
SOLID 원칙 SOLID 란 -로버트 마틴이 2000년대 초반 명명한 객체 지향 프로그래밍 및 설계의 기본 원칙을 이야기한 것 (wikipedia) SOLID 소개 -위키 백과 내용을 기반으로 제가 경험하면서 받아들인 언어로 조금씩 붙여서 작성했습니다. S (SRP) 단일 책임 원칙 (Single Responsibility Principle) 한 클래스는 하나의 책임(기능)만 가져야 한다. O (OCP) 개방-폐쇄 원칙 (Open/Closed Principle) 소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어야 한다. -> 즉 기존의 코드를 변경하지 않고 기능을 수정하거나 추가할 수 있도록 설계해야 한다. L (LSP) 리스코프 치환 원칙 (Liskov Substitution Principle) 상위 타입 .. 2023. 6. 20.
[자료구조] 배열(Array) 배열 -연속적인 메모리상에 동일한 타입(or 그의 파생타입)의 요소를 일렬로 저장하는 자료구조 -인덱스를 사용하여 직접적으로 엑세스 가능 -고정된 크기를 갖는다 -> 초기화시 해당 크기 그대로 유지 (중간에 새로 사이즈를 바꾸지 않는다면) 배열의 시간 복잡도 -배열의 사이즈와 상관없이 한 요소에 접근하는 시간은 인덱스 사용시 O(1) -특정 요소를 찾기 위해선 배열의 크기 n에 대하여 O(n) 배열 최적화 -정렬된 배열에서 값을 찾는 경우, Binary Search를 이용하여 O(long n) 가능 배열 사용법 -ex) 1부터 10까지 합을 출력하는 프로그램 class Program { static void Main(string[] args) { int[] numArray = new int[10]; in.. 2023. 6. 20.
728x90
반응형

티스토리툴바