폐관코딩

신장트리 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 한다. 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 싸이클이 없는 무방향 그래프 최소 비용 신장 트리 최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있으며, 이 알고리즘들은 최소 비용 신장 트리가 간선의 가중치의 합이 최소이어야 하고, 반드시 (n-1)개의 간선만 사용해야 하며, 사이클이 포함되어서는 안 된다는 조..

이진검색트리란? 이진트리이면서 각 노드에 하나의 키(데이터)를 가지고있으며 임의의 노드v에 대하여 왼쪽 부트리에 있는 키들은 key[v] 보다 작고 오른쪽부트리에 있는 값은 크거나 같다. dynamic set 을 효과적으로 지원하기위한 자료구조(search, insert, delete) 예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 𝑂(log𝑛)O(log⁡n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 𝑂(1)로 효율적이지만 탐색하는 데에는 𝑂(𝑛)의 계산복잡성이 발생. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적. 이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 씁니다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회..

힙이란? 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는 느슨한 정렬상태. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 중복값을 허용한다.(이진 탐색트리와는 다름.) 우선순위 큐, 허프만정렬, 힙정렬 등에서 사용 힙의 종류 1. 최대힙(Max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 2. 최소힙(Min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완..

트리(Tree)의 개념 트리는 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성 트리는 하나의 루트 노드를 갖고, 루트노드는 0개 이상의 자식 노드를 갖고 있다. 트리에는 사이클(cycle)이 존재할 수 없는 단방향이다. 노드들은 특정 순서로 나열될 수 있다. 트리 관련 용어 루트 노드(root node): 부모가 없는 최상단 노드. 내부(internal) 노드: 부모, 자식이 있는 노드. 단말 노드(leaf node): 자식이 없는 노드. 형제노드(sibling): 같은 부모를 가지는 노드. 간선(edge): 노드를 연결하는 선 (branch 라고도 부름). 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 ..

LinkedList란? 연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우..

ArrayList란? ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트이다. 일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리한다는점이 유사하지만 한번 생성되면 크기가 변하지 않는 배열과는 달리 ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다. ArrayList에서 특정 인덱스의 객체를 제거하게 되면, 제거한 객체의 인덱스부터 마지막 인덱스까지 모두 앞으로 1칸씩 앞으로 이동한다. 객체를 추가하게 되면 1칸씩 뒤로 이동하게 된다. 인덱스 값을 유지하기 위해서 추가/삭제 시 전체 객체가 위치가 이동한다. 따라서 잦은 원소의 이동, 삭제가 발생할 경우 Ar..

쓰레드 애플리케이션 코드를 하나하나 순차적으로 실행하는 것은 쓰레드 자바 메인 메서드를 처음 실행하면 main이라는 이름의 쓰레드가 실행 쓰레드가 없다면 자바 애플리케이션 실행이 불가능 쓰레드는 한번에 하나의 코드 라인만 수행 동시 처리가 필요하면 쓰레드를 추가로 생성 요청 마다 쓰레드 생성 장단점 장점 동시 요청을 처리할 수 있다. 리소스(CPU, 메모리)가 허용할 때 까지 처리가능 하나의 쓰레드가 지연 되어도, 나머지 쓰레드는 정상 동작한다. 단점 쓰레드는 생성 비용은 매우 비싸다. 고객의 요청이 올 때 마다 쓰레드를 생성하면, 응답 속도가 늦어진다. 쓰레드는 컨텍스트 스위칭 비용이 발생한다. 쓰레드 생성에 제한이 없다. 고객 요청이 너무 많이 오면, CPU, 메모리 임계점을 넘어서 서버가 죽을 수 ..

Servlet의 개념 웹 환경에서 HTTP를 통한 통신을 할 때 서버에서 처리되는 내용은 다음과 같다. 여기서 의미있는 비즈니스 로직은 초록박스의 단 두줄. 하지만 통신을 위한 프로토콜연결 부터 내용파싱 응답메시지 생성 등 부수적인 일이 많다. 서블릿을 지원하는 WAS 핵심 비즈니스로직을 제외한 다른 것들을 자동으로 해주는 기능을 한다. 서블릿이란? Java Thread를 이용하여 동작한다. MVC 패턴에서 Controller로 이용된다. 클라이언트의 요청에 대해 동적으로 작동하는 웹 어플리케이션 컴포넌트 HTML 변경 시 Servlet을 재컴파일해야 하는 단점이 있다. 서블릿 사용시 HTTP 요청, 응답의 흐름 WAS는 Request, Response 객체를 새로 만들어서 서블릿 객체 호출 개발자는 R..

웹 서버(Web Server) HTTP 기반으로 동작 정적 리소스 제공, 기타 부가기능 정적(파일) HTML, CSS, JS, 이미지, 영상 예) NGINX, APACHE 웹 애플리케이션 서버(WAS - Web Application Server) HTTP 기반으로 동작 웹 서버 기능 포함+ (정적 리소스 제공 가능) 프로그램 코드를 실행해서 애플리케이션 로직 수행 - 동적 HTML, HTTP API(JSON) - 서블릿, JSP, 스프링 MVC 예) 톰캣(Tomcat) Jetty, Undertow 차이점 웹 서버는 정적 리소스(파일), WAS는 애플리케이션 로직 자바는 서블릿 컨테이너 기능을 제공하면 WAS 웹 시스템의 구성 WAS는 정적 리소스, 애플리케이션 로직 모두 제공 가능해서 WAS, DB 만으..

알고리즘 풀며 정리하는 형변환 문자열에서 문자의 비교시 int 를 스트링 또는 char로 변환할 경우가 있다. Java에서int를char로 변환하는 메소드는(char),Character.forDigit()및toString() 가 있다. 1. (char) 타입 캐스팅을 사용하여 ASCII 값을 가져 와서int의char를 얻는다. int value_int =1; //이렇게하면 안됨. char value_char1 = (char)(value_int); //이렇게 해줘야함. char value_char2 = (char)(value_int +'0'); 위에 value_char1 처럼 하면 ascii 값 1 (인쇄 할 수없는 머리글 시작 문자)로 문자를 인쇄하게되어 잘못된 값이 나온다. 숫자 (0-9)를 변환하려면..