Life and IT

MVC 패턴이란? Model, View, Controller 즉 MVC는 소프트웨어 공학에서 사용되는 소프트웨어 디자인 패턴이다. 이 패턴은 사용자 인터페이스로부터 비즈니스 로직을 분리하여, 애플리케이션의 시각적 요소나 그 이면에서 실행되는 비즈니스 로직을 서로 영향 없이 쉽게 고칠 수 있는 애플리케이션을 만들 수 있다. 비즈니스 로직이란? 회원 가입을 예로 들어보자. 아이디 중복 검사를 해야 할 때 크게 두 영역으로 나눌 수 있다. 하나는 중복 아이디가 있는지 없는지를 검사하기 위한 일련의 과정 또 다른 하나는 유저에게 단순히 텍스트나 다이얼로그로 알려주는 것이 있다. 두 번째 영역은 View 영역 또는 Presentation 영역이라고 불리는데, 가공된 데이터를 단순히 표시만 해주는 것이다. 데이터 ..

요소 접근 (탐색 및 조회) array는 random access를 지원한다. - random access란? : O(1)의 시간에 인덱스를 통해 모든 배열 요소에 액세스 할 수 있는 것을 의미한다. 따라서 배열은 특정 배열 요소에 접근하는 시간 복잡도이 O(1)이다. linked list는 sequential access를 지원한다. - 어떤 요소에 접근할 때, 처음부터 순차적으로 접근하며 찾아야 한다. - 특정 요소에 접근할 때의 시간 복잡도는 O(n)이 된다. 저장 방식 array에서 요소들은, 인접한 memory의 위치에 저장된다. linked list에서 새로운 요소들은, 각각 memory 어딘가에 저장된다. 새로운 요소의 memory 위치 주소는 linked list의 이전 node에 저장된다..

Graph node와 edge로 구성된 한정된 자료구조이다. node는 정점이며 edge는 정점 간의 간선이다. 그래프는 방향성이 있을 수도, 없을 수도 있다. 인접 리스트 인접 리스트로 그래프를 표현하는 것이 가장 일반적인 방법이라고 한다. 인접 리스트는 그래프 내에 적은 숫자의 간선만을 가지는 경우에 용이하다고 한다. 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다. 배열이나 연결 리스트 등을 이용해서 구현이 가능하다. 특징으로는 연결된 간선의 정보만을 저장하여 공간 효율성은 우수하지만 각 정점들의 연결 여부 확인을 위해 O(n)의 시간 복잡도를 가진다. 인접 행렬 인접 행렬은 정점들을 2차원 배열로 나타낸 것이다. 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프의 경우에 용이하다. 단점..

먼저 해시 함수가 가져야 할 특징 3가지가 있다. 충돌이 적어야 한다. 해시 테이블에 고르게 분포시킬 수 있는 주소의 연산 값이 나와야 한다. 이는 곧 1번을 충족할 수 있다. 계산이 빨라야 한다. 위 3가지를 고루 갖추지 못한다면 100개의 버킷 중에 하나의 버킷만 나와서 오버플로우가 발생하는 참사가 일어날 수 있다. 위의 특징을 고루 갖춘 함수 중 하나로 제산 함수라는 것이 있다. 제산 함수 레코드(키) 값을 소수로 나누어 나머지 값을 주소로 지정하는 해시 함수. ex) h(k) = k % 7 만약 위 특징을 갖춘 해시 함수를 만들었는데도 오버플로우가 발생한다면? 내가 아는 선에서 두 가지의 방법이 있다. 선형 탐사법 (Linear Probing) 분리 연결법 (Separate Chaining) 1...

해시 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값 *매핑 : 하나의 값을 다른 값으로 대응시키는 것 탐색 하나 이상의 필드로 구성된 레코드의 집합에서 원하는 레코드를 찾는 것 *탐색을 위하여 사용되는 자료 구조 : 배열, 연결 리스트, 트리, 그래프 또한 레코드들의 집합을 테이블(Table)이라고 부른다. 테이블에서 레코드들을 어떻게 구분할까? 레코드마다 서로 구별되는 키를 가지고 있는데 이것을 탐색키라고 부른다. 의미 있는 단위를 이끌어 내기 위해서 하나의 필드를 가진 레코드만으로는 부족하다. 따라서 맵이라는 개념을 끌어온다. 맵 탐색키 그리고 탐색키와 관련된 값의 쌍을 말한다. 즉, 두 가지 필드를 가진 키를 가진 레코드 또는 엔트리로 이루어진다. 이 두 가지 값은 key, v..

연결 리스트의 변형된 형태인 이중 연결 리스트는 다음 노드의 포인터만 가지고 있는 단일 연결 리스트와 달리 다음 노드, 2개의 연결 포인터를 가지고 있다. 따라서 양방향으로 리스트 순회가 가능하여 어떤 노드라도 그의 이전, 이후 노드를 찾아갈 수 있다. 이중 연결 리스트의 삭제 시 프로세스는 다음과 같다. 단일 연결 리스트와 비슷하나 previous 속성을 가진다는 차이가 있다.

해시 테이블이란? 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 리턴 값을 인덱스에 저장하는 자료구조이다. 그렇다면 왜 해시 테이블을 사용할까? 직접 주소 테이블 (Direct Address Table) 해시 테이블은 직접 주소 테이블이라는 자료구조에서부터 출발한다. 직접 주소 테이블은 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다. 내가 소수 찾기 알고리즘을 풀 때 소수만 남기기 위해서 0~n까지의 배열을 만들었는데 바로 그 방식인 것이다. index 0 1 2 3 4 5 6 7 8 value 0 1 2 3 4 5 6 7 8 찾고자 하는 값과 테이블의 인덱스가 동일하므로 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간 복잡도는 O(1)이다. 마찬가지로 테이블에..

Binary Search Tree (BST) 이진 검색 트리는 정렬된 트리 데이터 구조이다. 모든 부모 노드에는 최대 두 개의 자식 노드가 있으며, 부모 노드의 왼쪽 자식 노드는 항상 부모 노드보다 작고 오른쪽 자식 노드는 항상 부모 노드보다 크다. 모든 트리 자료구조와 같이 이진 검색 트리는 Root가 있고(최상단 노드), 부모 노드에는 최대 두 개의 자식 노드들이 있으며 이것을 Siblings라고 한다. 노드 사이의 연결을 edge라고 하고, 자식이 없는 노드를 leaf라고 한다. 이진 검색 트리는 순차적으로 정렬된 자료구조로서, 데이터 삽입 시 노드가 순서대로 배치된다. 따라서 이러한 정렬된 순서는 검색을 빠르게 만든다. 배열과 달리 데이터는 참조 형식으로 저장된다. 자료구조에 저장할 때, 우리는 ..

소개 Linked List는 Array List와 다르게 엘리먼트와 엘리먼트 간의 연결(Link)을 이용해서 리스트를 구현한 것을 의미한다. 그렇다면 연결은 무엇이고 연결이 아닌 것은 무엇인지 생각해볼 필요가 있다. 메모리의 구조 일단 메모리의 구조에 대해서 먼저 알아보겠다. Array List와 Linked List라는 두 회사가 건물의 일부를 임대해서 사용한다고 생각해보자. Array List 회사 이 회사는 모든 직원이 한 곳에 모여있어야 한다는 철학이 있기 때문에 사무실이 모여있다. 만약 회사가 성장해서 사무실이 좁아지면 더 이상 새로운 직원을 뽑을 수 없다. 또한 만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아 전체가 이사를 해야 한다. Array List는 위의 비..