CS
-
자료구조 - 이진검색트리(ALV, RED-BLACK)CS/자료구조 2021. 2. 21. 20:10
Balanced Binary Search Tree AVL트리란? 균형잡힌 이진검색 트리이다. 오른쪽 서브트리와 왼쪽 서브트리의 높이 차를 1까지만 허용한다. 1보다 큰 경우 tree modification연산을 진행해여 재배열 한다. 트리의 높이는 항상 logn으로 연산에 대한 시간복잡도도 O(logn)이 된다. Red-Black Tree란? 균형잡힌 이진검색 트리이다. 트리의 모든 노드에 블랙 또는 레드 색을 칠하되 레드블랙 특성을 만족해야한다. 특성은 다음과 같다. 루트는 블랙이다. 모든 리프는 블랙이다. 레드 노드는 연속으로 올 수 없다. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 여기서 리프 노드는 일반적인 의미의 리프노드와 다르다. 모든 NIL포인터가..
-
WEB - WASCS/WEB 2021. 2. 20. 21:42
WAS(Web Application Server) 웹 서버(web server) 정적 컨텐츠(html, png, css 등)를 제공하는 서버이다. 클라이언트에서 요청이 올 때 가장 앞에서 요청을 처리한다. ex) Apache, nginx WAS 동적 컨텐츠(jsp, php 등)를 제공하는 서버이다. DB조회등 애플리케이션에 대한 로직을 실행하여 웹 서버로 다시 반환해 준다. 웹 서버와 DBMS사이에서 동작하는 미들웨어로서 jsp, servlet을 실행시킬 수 있는 컨테이너 기반으로 동작한다. ex) Tomcat, JBoss, Jeus 웹 서버와 WAS를 나눠 사용하는 이유 WAS는 정적, 동적 처리 둘다 가능하다. 그러므로 웹 서버를 사용하지 않더라도 웹 서비스를 할 수 있지만 웹 서버와 WAS를 나눠 ..
-
자료구조 - 이진검색트리CS/자료구조 2021. 2. 20. 20:09
Binary Search Tree 이진검색트리 이진트리 이면서 각 노드에 하나의 키를 저장하고, 루트 노드에 대해 왼쪽 서브트리에 있는 키들은 루트의 키 보다 작거나 같고, 오른쪽 서브트리에 있는 키들은 루트의 키 보다 크거나 같다. 트리의 높이는 평균 logn으로 연산에 대한 시간 복잡도도 평균 O(logn)이다. 이진검색트리의 연산 Search: 키를 탐색한다. 시간복잡도는 O(h). h는 트리의 높이를 의미한다. Succesor: 노드 x의 Succesor란 x의 키보다 크면서 가장 작은키를 가진 노드를 탐색한다. 이때 모든 키들이 서로 다르다고 가정한다. 시간복잡도는 O(h). Predecessor: 노드 x의 Predecessor란 x의 키보다 작으면서 가장 큰 키를 가진 노드를 탐색한다. 이때..
-
OS - 은행원 알고리즘CS/OS 2021. 2. 20. 19:37
은행원 알고리즘 은행원 알고리즘 이란? 교착상태 회피 알고리즘이다. OS는 안전상태를 유지할 수 있는 요구만을 수락하고 불안정한 상태를 초래할 사용자의 요구는 나중에 수락할 수 있는 상태가 될때까지 계속 거절한다. 동작 과정이 은행에 돈을 빌리러 온 고객들과 돈을 빌려줄 은행의 관계와 유사하다. 안전상태 안전상태: 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태이다. 불안전상태: 교착상태이기 위한 조건중에 하나로 불안전 상태에서만 교착상태가 발생한다. 그러나 불안전 상태라고 해서 무조건 교착상태가 발생하는 것은 아니다. 시스템이 항상 안전상태를 유지할 수 있게 하는 것이 바로 은행원 알고리즘이다. 은행원 알고리즘 필요 요건 Max: 각 고..
-
JAVA - 객체 직렬화CS/Java 2021. 2. 19. 22:30
객체 직렬화(Serialization) 직렬화 내부에서 사용되는 객체 또는 데이터를 외부의 시스템에서도 사용할 수 있도록 다른 형태(바이트, JSON등)로 변환하는 기술이다. 자바에서는 Serializable 인터페이스를 통해서 직렬화를 구현한다. 역직렬화 직렬화와 반대된다. 즉, 직렬화된 데이터를 역으로 직렬화 하여 객체로 재구성 하는 것을 의미한다. 객체 직렬화 객체 직렬화: 객체의 내용을 자바 I/O가 자동적으로 바이트 단위로 변환하는 기능을 제공한다. 자바의 I/O처리는 정수, 문자열, 바이트 단위의 처리만 지원하므로 복잡한 객체의 내용을 저장/복원 하거나 네트워크로 전송하기 위해선 객체의 멤버변수의 각 내용을 일정한 형식(패킷)으로 만들어 전송해야 한다. 자바에서 자동으로 처리해 주기 때문에 O..
-
JAVA - finalCS/Java 2021. 2. 19. 22:02
final final 오직 한 번만 할당할 수 있는 entity를 정의할 때 사용한다. final 변수가 객체를 참조한다면 그 객체의 상태가 바뀌어도 final변수는 매번 동일한 내용을 참조한다. 즉, 한 번 값을 지정하면 절대 바뀌지 않는다. final 클래스 final 클래스는 더이상 상속할 수 없다. final 메소드 final 메소드는 상속받은 하위 클래스에서 변경할 수 없다. final 변수와 static final변수는 한 번 값을 할당하면 수정할 수 없다. static 변수: 정적 변수로 메모리에 고정적으로 할당되어 프로그램이 종료될 때 해제되는 변수이다. 클래스의 모든 인스턴스가 공유한다. final변수는 static과 함께 쓰면 메모리 효율이 높아진다. reference coding-fa..
-
자료구조 - 이진트리CS/자료구조 2021. 2. 18. 23:03
이진트리 트리 노드가 N개인 트리는 N - 1개의 링크를 가진다. 트리의 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의 두 노드간의 경로도 유일하다. 이진트리 각 노드는 최대 2개의 자식노드를 가진다. 종류 perfect binary tree 이진 트리의 모든 노드가 꽉 차있는 트리이다. 높이가 h인 perfect binary tree는 2^h - 1개의 노드를 가진다. full binary tree 이진 트리의 모든 노드가 0개 또는 2개의 자식을 갖는 트리이다. complete binary tree 이진 트리에서 노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리이다. 각 노드는 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식의 주소를 저장한다. 노드가 N개인 full, complete b..