Brute force Study

스프링 컨테이너와 빈스프링 컨테이너 생성스프링 컨테이너가 생성되는 과정을 알아보자.//스프링 컨테이너 생성ApplicationContext applicationContext = new AnnotationConfigApplicationContext(AppConfig.class);ApplicationContext 를 스프링 컨테이너라 한다.ApplicationContext 는 인터페이스이다.스프링 컨테이너는 XML을 기반으로 만들 수 있고, 애노테이션 기반의 자바 설정 클래스로 만들 수 있다.직전에 AppConfig 를 사용했던 방식이 애노테이션 기반의 자바 설정 클래스로 스프링 컨테이너를 만든 것이다.자바 설정 클래스를 기반으로 스프링 컨테이너( ApplicationContext )를 만들어보..

IoC, DI, 그리고 컨테이너, 스프링으로 전환제어의 역전 IoC(Inversion of Control)보통 개발자가 직접 원하는대로 객체를 생성하고 호출하고 그 안에서 생성, 호출… 다 컨트롤 하고 제어하는 스타일로 개발을 하는데제어의 역전이라는 개념은 내가 뭔가 호출하는게 아니라 프레임워크 같은게 내 코드를 대신 호출해준다. 제어권이 뒤바뀐다고 해서 제어의 역전이라고 한다기존 프로그램은 클라이언트 구현 객체가 스스로 필요한 서버 구현 객체를 생성하고, 연결하고, 실행했다. 한마디로 구현 객체가 프로그램의 제어 흐름을 스스로 조종했다. 개발자 입장에서는 자연스러운 흐름이다.반면에 AppConfig가 등장한 이후에 구현 객체는 자신의 로직을 실행하는 역할만 담당한다. 프로그램의 제어 흐름은 이제 App..

스프링 핵심 원리 이해2 - 객체 지향 원리 적용새로운 할인 정책 개발새로운 할인 정책을 확장해보자.주문한 금액의 %를 할인해주는 새로운 정률 할인 정책을 추가하자.RateDiscountPolicy 코드package hello.core.discount;import hello.core.member.Grade;import hello.core.member.Member;public class RateDiscountPolicy implements DiscountPolicy { private int discountPercent = 10; @Override public int discount(Member member, int price) { if (member.getGrade() == G..

문제https://www.acmicpc.net/problem/11724   무방향 그래프에서 연결 요소를 찾는 문제틀렸던 부분N개의 노드가 있고, 1개의 간선이 있다고 하자. 그러면 연결 요소는 1개가 아니라 N-2개여야 한다. 즉, 연결되어있지 않은 노드들을 고려하지 않아서 2트한 문제이다. 코드#include using namespace std;bool vis[1002];unordered_set sub;vector adj[1002];void DFS(int start) { vis[start] = 1; sub.erase(start); for (int i = 0; i > n >> m; for (int i = 0; i > s >> e; adj[s].push_back(e); ..

강한 연결 요소동영상 서비스 사이트에서 다양한 채널 구독자 간의 공통점에 대한 통계를 작성하여, 서로 연관이 있는 구독 정보 그룹으로 나누려고 한다. 이 때 방향 그래프에서 나타나는 공통적인 특징을 이용하여 이러한 복잡한 문제를 해결할 수 있다. 방향 그래프에서 에지는 명시적인 "방향" 정보를 가진다. 방향 그래프에서 에지는 한쪽 방향으로만 이동할 수 있기 때문에 그래프의 특정 정점에 도달할 수 있는지 여부는 탐색을 어느 정점에서 시작했는지에 따라 다르게 결정된다.주어진 그래프를 여러 개의 구역으로 나누되 같은 구역 안의 정점끼리는 서로 이동 가능한 경로를 갖도록 나눌 경우, 각 구역은 해당 그래프의 강한 연결 요소를 나타낸다. 방향 그래프와 무방향 그래프에서 연결성무방향 그래프에서 연결 요소(conne..

벨만 포드 알고리즘그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾는다 (V는 정점의 개수)음수 가중치가 있는 그래프를 다룰 때 벨만 포드 그래프를 사용할 수 있다.다익스트라 알고리즘에 비해 높은 점근적 시간 복잡도를 가지지만, 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공한다. 벨만-포드 알고리즘 구현각 정점의 최단 거리 값 배열을 반환하는 함수struct Edge{ int src; int dst; int weight;};const int UNKNOWN = INT_MAX;vector BellmanFord(vector edges, int V, int start){ vector distance(V, UNKNOWN..

단일 시작 최단 경로 문제"주어진 그래프에서 시작 정점과 목적 정점이 주어질 때 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하는 문제" 다익스트라 알고리즘이란?음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변형한 형태이다.프림 알고리즘과 다익스트라 알고리즘의 차이점프림 알고리즘 : 경계로부터 최소 거리의 정점의 거리 값으로 설정. 모든 정점을 방문해야 종료다익스트라 알고리즘 : 시작 정점으로부터 각 정점까지의 전체 거리를 사용. 목적 정점이 나타나면 종료 다익스트라 알고리즘의 동작모든 정점의 거리 값을 무한대로 초기화한다. 시작 정점에서 자기 자신까지의 거리는 0이므로 시작 정점의 거리 값은 0으로 설정한다. 그리고 모든 거리 값을 최소 ..

크루스칼 알고리즘그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구현한다.시간 복잡도 : O(E log V)주로 적은 수의 에지로 구성된 희소 그래프(sparse graph)에서 사용된다 프림 알고리즘그래프의 아무 정점부터 시작하여 MST를 구성한다가장 널리 알려진 시간 복잡도는 O(E + V log V)이다.주로 많은 수의 에지로 구성된 밀집 그래프(dense graph)에서 사용된다

MST 문제란?정점 집합 V와 가중치를 갖는 에지 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제 Cf) 크루스칼 알고리즘그래프의 모든 에지를 최소 힙에 추가하고 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성한다 프림 알고리즘은?BFS의 동작 방식과 유사하다.먼저 시작 정점을 이용하여 경계를 구성한다경계는 이전에 방문했던 정점들에 의해 구성된다현재 경계에 인접한 정점을 반복적으로 탐색한다이 때 경계를 관통하는 에지 중에서 가장 가중치가 적은 에지를 선택하고, 이 에지이 연결된 정점을 방문한다'프림 알고리즘을 구현하려면 그래프의 각 정점에 경계로부터의 거리(distance)정보를 기록해야 한다. 프림 알고리즘..

이분 그래프란?정점을 두 개의 집합으로 나눌 수 있는 그래프그래프의 모든 에지는 서로 다른 집합에 속한 정점끼리 연결되어야 한다.ex) 학생 목록과 수업 목록을 모델링하는 경우ex) 스트리핑 플랫폼에서 영화 목록과 시청자 사이의 관계를 모델링하는 경우최대 매칭 또는 최소 정점 커버 문제와 같은 NP-완전 문제들이 이분 그래프에서는 다항시간으로 풀 수 있다.따라서 주어진 그래프가 이분 그래프인지 아닌지 판별하는 것은 매우 중요하다 이분 그래프의 구현DFS를 변형하여 만들 수 있다.1번 정점부터 DFS를 시작한다고 가정한다(1번 정점을 스택에 추가한다)스택에 방문하지 않은 정점이 남아있다면 스택에서 정점을 하나 꺼내고 이를 현재 정점으로 설정한다이전 정점에 할당된 색상이 검은색이면 현재 정점에 빨간색을 할당..