최소신장트리 (Minimum Spanning Tree) 신장트리 : 모든 정점들은 포함하고 간선은 (정점수-1) 개만 포함하는 트리, 사이클 없음 신장 트리 중에서 간선 가중치의 합이 최소인 신장 트리 ★Kruskal : Union-Find(Disjoint Set) 사용 O(|E|log|V|) Prim : 우선순위큐 사용 O(|E|log|V|) 간선을 기준으로 LinkedList에 담아 정렬 후 Union-Find Union Find by Rank 트리의 높이가 높을 수록 Find Set 수행시간 증가 Union 시 두 집합의 Root 중 Rank 값이 작은 Root를 큰 Root로 변경 Rank 값이 같을 경우에만 랭크 값 증가 public static void unionSet(int a, int b)..
시작점에서 가까운 정점부터 순서대로 방문 Queue O(|V|+|E|) 최단 경로 문제 해결 가중치가 없는 그래프 //V : 정점 집합, E : 간선 집합, Q : 큐 //visit[v] : 방분정보 저장 //Adj[v] : 정점 v의 인점 정접들 집합 //D[] : 시작점부터 각 정점까지 거리 //P[] : 최단 경로 트리 저장 bfs(s) { for (v : V) { D[v] = Max; P[v] = null; } D[s] = 0; P[s] = s; visit[s] = true; Q.offer(s); while(!Q.isEmpty()) { v = Q.poll(); for (인접 정점 u : Adj[v]) { if (visit[u] == false) { D[u] = D[v] + 1; P[u] = v; ..
인접한 간선 모두 방문 더 이상 갈 곳이 없으면 Back Tracking 재귀호출, Stack 그래프의 전체 구조를 파악 O(|V|²) 두 정점이 서로 연결되어 있는가 연결된 부분집합의 개수 세기 위상정렬 사이클 존재여부 //V : 정점 집합, E : 간선 집합 //visit[v] : 방문정보 저장 //Adj[v] : 정점 v의 인접 정점 집합 dfs(v) { visit[v] = true;//방문 처리 for (인접 정점 u : Adj[v]) { if (visit[u] == false)//인접 정점이 방문하지 않았다면 탐색 dfs(u); } }
Java Reflection 구체적인 클래스 타입을 알지 못해도, 그 클래스의 메소드, 타입, 변수들을 접근할 수 있도록 해주는 Java API Java Reflection은 Java 프로그램에서 클래스의 메타데이터를 동적으로 검사하고 조작하는 기능을 제공합니다. Reflection을 사용하면 실행 중에 클래스의 필드, 메서드, 생성자 등을 검사하고 호출할 수 있으며, 새로운 객체 인스턴스를 생성하거나 필드 값을 읽고 쓸 수도 있습니다. 클래스 정보 검사: Reflection을 사용하여 클래스의 이름, 패키지, 상위 클래스, 인터페이스, 필드 및 메서드 등의 정보를 검사할 수 있습니다. 동적 객체 생성: Reflection을 사용하여 클래스의 생성자를 호출하여 새로운 객체 인스턴스를 생성할 수 있습니다...
데코레이터 패턴(Decorator Pattern)
데코레이터 패턴 객체에 추가적인 요건을 동적으로 첨가한다. (구성과 위임을 통해) 데코레이터는 서브클래스를 만드는 것을 통해서 기능을 유연하게 확장할 수 있는 방법을 제공한다. 데코레이터 패턴에서는 구상 구성요소를 감싸주는 데코레이터들을 사용한다. 데코레이터 클래스의 형식은 그 클래스가 감싸고 있는 클래스의 형식을 반영한다. (상속, 인터페이스 구현을 통해 자신이 감쌀 클래스와 같은 형식을 가지게 된다.) 데코레이터에서는 자기가 감싸고 있는 구성요소의 메소드를 호출한 결과에 새로운 기능을 더함으로써 행동을 확장한다. 구성요소의 클라이언트 입장에서는 데코레이터의 존재를 알 수 없다. 데코레이터 패턴을 사용하면 자잘한 객체들이 매우 많이 추가될 수 있고, 코드가 복잡해질 수 있다. public abstrac..
X-Forwarded-For (XFF) 헤더는 HTTP 프록시나 로드 밸런서를 통해 웹 서버에 접속하는 클라이언트의 원 IP 주소를 식별하는 사실상의 표준 헤더다. 클라이언트와 서버 중간에서 트래픽이 프록시나 로드 밸런서를 거치면, 서버 접근 로그에는 프록시나 로드 밸런서의 IP 주소만을 담고 있다. 클라이언트의 원 IP 주소를 보기위해 X-Forwarded-For 요청 헤더가 사용된다. 이 헤더는 디버깅, 통계, 그리고 위치 종속적인 컨텐츠를 위해 사용되고, 클라이언트의 IP 주소 등과 같은 민감한 개인정보를 노출시킨다. 그러므로 이 헤더를 사용할 때에는 사용자의 프라이버시를 주의해야 한다. https://developer.mozilla.org/ko/docs/Web/HTTP/Headers/X-Forwa..
멀티스레드 환경에서 여러 스레드가 동시에 공유 자원을 점유하려고 할 때 발생. 해결 방법 : AtomicType, volatile, synchronized 사용 http://egloos.zum.com/ryukato/v/1179260 안전하게 생성자 작성하기 (Multi-threads 대비) 안전하게 생성자 작성하기 (Multi-threads 대비) (원문: Java theory and practice: Safe construction techniques)[ht egloos.zum.com
* 옵저버 패턴 한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다 의존성을 정의 * Java 내장 옵저버 패턴 작동 방식 Observer 객체 : java.util.Observer 구현 Subject 객체 : java.util.Obervable 상속 * java.util.Observable 단점 . 클래스이기 때문에 상속해서 사용해야한다. 그래서 재사용성에 제약. . 인터페이스가 없기 때문에 Observer API와 잘 맞는 클래스를 직접 구현 불가. . Observable 클래스의 핵심 메소를 외부에서 호출 불가. 서브클래스를 인스턴스 변수로 사용 불가. -> 직접 API 구현해서 사용 * 디자인 원칙 1. 애플리케이션에서 달라지는 부분을..
[Design Patterns] 전략 패턴 (Strategy Pattern)
소프트웨어 개발에 있어서 바뀌지 않는 것 : 변화 나중에 어떻게 바뀔 것인지 생각해라 디자인패턴 소프트웨어 디자인 과정에서 자주 발생하는 문제들에 대한 전형적인 해결책 훌륭한 객체지향 디자인 품질을 갖추고 있는 시스템을 개발하는 방법을 제공 구상 (Concreate) 클래스란? 추상 (Abstract) 클래스와 대조적으로 모든 메서드를 구현한 클래스 구성(Composition) : A has B (캡슐화, 느슨한 결합) 상속(Inheritance) : A is B 전략 패턴 알고리즘을 캡슐화하고 이를 교환하여 사용하는 패턴 전략 패턴은 코드의 유연성과 재사용성을 높여주며, 알고리즘의 변경이나 추가에 용이 비슷한 작업을 수행하지만 다양한 알고리즘을 적용해야 하는 경우에 전략 패턴을 사용하여 코드를 구현 C..