Brute force Study

#include using namespace std;int parent[10001];vector>> edges;// findint find(int x) { if (x == parent[x]) return x; else return parent[x] = find(parent[x]);}// unionvoid merge(int a, int b) { int x = find(a); int y = find(b); if (x == y) return; parent[y] = x; // y -> x}int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int v, e; long long resul..

#include #define MAX 10int parent[MAX];int GetParent(int x) { if (x == parent[x]) return x; return parent[x] = GetParent(parent[x]);}int UnionParent(int a, int b) { a = GetParent(a); b = GetParent(b); if (a  관련 문제https://www.acmicpc.net/problem/1717

빈 스코프빈 스코프란?지금까지 우리는 스프링 빈이 스프링 컨테이너의 시작과 함께 생성되어서 스프링 컨테이너가 종료될 때 까지 유지된다고 학습했다. 이것은 스프링 빈이 기본적으로 싱글톤 스코프로 생성되기 때문이다. 스코프는 번역 그대로 빈이 존재할 수 있는 범위를 뜻한다.스프링은 다음과 같은 다양한 스코프를 지원한다.싱글톤: 기본 스코프, 스프링 컨테이너의 시작과 종료까지 유지되는 가장 넓은 범위의 스코프이다.프로토타입: 스프링 컨테이너는 프로토타입 빈의 생성과 의존관계 주입까지만 관여하고 더는 관리하지 않는 매우 짧은 범위의 스코프이다.스프링이 요청을 하면 빈을 만들고 의존관계 주입도 하고 초기화까지 하고 메서드까지 불러주고 여기서 스프링의 역할이 끝난다. 더 이상 스프링 컨테이너가 관리하지 않아서 종료..

빈 생명주기 콜백빈 생명주기 : 스프링 빈이 생성되거나 소멸되기 일보 직전에 스프링이 빈 안에 있는 메서드를 호출해줄 수 있는 기능세 가지 방식이 있고, 각 방식별로 특징이 있는데 이에 대해 알아본다빈 생명주기 콜백 시작데이터베이스 커넥션 풀이나, 네트워크 소켓처럼 애플리케이션 시작 시점에 필요한 연결을 미리 해두고, 애플리케이션 종료 시점에 연결을 모두 종료하는 작업을 진행하려면, 객체의 초기화와 종료 작업이 필요하다.이번 시간에는 스프링을 통해 이러한 초기화 작업과 종료 작업을 어떻게 진행하는지 예제로 알아보자. 간단하게 외부 네트워크에 미리 연결하는 객체를 하나 생성한다고 가정해보자. 실제로 네트워크에 연결하는 것은 아니고, 단순히 문자만 출력하도록 했다. 이 NetworkClient 는 애플리케이..

의존관계 자동 주입이전 게시물에서 다뤘듯이 AppConfig와 같은 설정 정보가 없기 때문에 컴포넌트 스캔을 하는 과정에서 의존관계 자동 주입이 이뤄줘야 한다.이번 게시물에서는 의존관계 주입 방법과 관련된 내용을 다뤄보겠다.다양한 의존관계 주입 방법의존관계 주입은 크게 4가지 방법이 있다.생성자 주입수정자 주입(setter 주입)필드 주입일반 메서드 주입생성자 주입이름 그대로 생성자를 통해서 의존 관계를 주입 받는 방법이다.지금까지 우리가 진행했던 방법이 바로 생성자 주입이다.특징생성자 호출시점에 딱 1번만 호출되는 것이 보장된다.불변, 필수 의존관계에 사용이와 관련있는 키워드를 생각하면 "final" 키워드가 생각나야 한다. final 필드는 반드시 생성자에서 값(인스턴스)을 넣어줘야 한다.packag..

컴포넌트 스캔컴포넌트 스캔과 의존관계 자동 주입 시작하기지금까지 스프링 빈을 등록할 때는 자바 코드의 @Bean이나 XML의 등을 통해서 설정 정보에 직접 등록할 스프링 빈을 나열했다.예제에서는 몇 개가 안되었지만, 이렇게 등록해야 할 스프링 빈이 수십, 수백개가 되면 일일이 등록하기도 귀찮고, 설정 정보도 커지고, 누락하는 문제도 발생한다. 역시 개발자는 반복을 싫어한다.(무엇보다 귀찮다 ᅲᅲ)그래서 스프링은 설정 정보가 없어도 자동으로 스프링 빈을 등록하는 컴포넌트 스캔이라는 기능을 제공한다. 또 의존관계도 자동으로 주입하는 @Autowired 라는 기능도 제공한다.코드로 컴포넌트 스캔과 의존관계 자동 주입을 알아보자. 먼저 기존 AppConfig.java는 과거 코드와 테스트를 유지하기 위해 남겨두..

싱글톤 컨테이너웹 애플리케이션과 싱글톤스프링은 태생이 기업용 온라인 서비스 기술을 지원하기 위해 탄생했다.대부분의 스프링 애플리케이션은 웹 애플리케이션이다. 물론 웹이 아닌 애플리케이션 개발도 얼마든지 개발할 수 있다.웹 애플리케이션은 보통 여러 고객이 동시에 요청을 한다.스프링 없는 순수한 DI 컨테이너 테스트package hello.core.singleton;import hello.core.AppConfig;import hello.core.member.MemberService;import org.junit.jupiter.api.DisplayName;import org.junit.jupiter.api.Test;import org.springframework.context.ApplicationContex..

문자열과 시퀀스에 대한 동적 계획법이전 게시물에서 다룬 문제는 정수 시퀀스 계산 문제에 초점을 두었다.이번에는 동적 계획법이 많이 사용되는 분야 중의 하나인 데이터 시퀀스의 패턴 문제에 대해 알아본다.주로 문자열 검색, 비교, 문자열 재구성 등의 문제와 관련이 있다.EX) 버전 관리 시스템(VCS)Git과 같은 VCS에서 우리가 다룰 데이터 시퀀스의 패턴 문제가 적용된다VCS는 변경된 소스 코드 부분을 쉽게 찾아보기 위해 두 가지 버전의 소스 코드를 비교하여 사용자에게 차이점을 표시해주는 비교 기능을 제공한다두 버전에 공통적인 문자열 시퀀스가 연속적일 필요가 없다는 사실을 고려하여 두 소스 코드의 유사성을 판별해야 한다.문자열 일부가 제거되거나 새로운 문자열이 임의 위치에 추가될 수도 있다.이러한 작업은..

부분집합의 합 문제(브루트포스, 백트래킹, 메모이제이션, 타뷸레이션)금전등록기에 남아 있는 동전을 조합하여 필요한 거스름돈을 만들 수 있는지 확인해보자.필요한 잔돈이 73270원이고, 10000원권, 1000원권과 500원, 100원, 50원, 10원 동전들이 전체 100개가 들어있다면?가능한 모든 조합을 시도해보면서 거스름돈의 금액을 맞추는 것은 너무 복잡해지고 실제로 구현하는 것은 너무 복잡하고 비현실적이러한 문제를 부분집합의 합 문제(subset sum problem)이라고 한다"음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가?"ex) S = {13, 79, 45, 29}, x = 42 --> True원소의 ..

동적 계획법(Dynamic Programming)이란?분할 정복 패러다임 개념을 확장한 것앞서 다룬 분할정복 / 그리디 알고리즘으로 해결할 수 없는 문제 중에서 재귀적으로 표현할 수 있는 문제는 동적 계획법을 이용한 문제 해결 방법이 적합할 수 있다.ex)조합(특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기)문자열과 시퀀스(편집 거리, 최장 공통 부분 시퀀스, 최장 증가 부분 시퀀스 등)그래프(최단 경로 문제)머신 러닝(음성/얼굴 인식)Ex) 피보나치 수열 문제의 특성피보나치 수열은 F(n) = F(n - 1) + F(n - 2)의 재귀적인 관계를 가지고 있다.위 수식은 이 수열의 재귀 관계를 표현한다.이 수열의 처음 두 원소 F(0), F(1)은 기조 조건(base case)이라고 부르며,..