devbelly

문제 www.acmicpc.net/problem/12012 알고리즘 Union Find, 오프라인 쿼리 풀이 헛간을 하나씩 닫아나갈 때 마다, 열린 헛간들의 연결성을 확인하는 문제입니다. 헛간을 닫을 때, 인접한 경로 또한 사라집니다. 우리가 아는 자료구조중 유니온 파인드는 조건에 따라 같은 노드들을 하나로 합치는 연산을 수행할 뿐, 합쳐진 노드들을 분리해내지는 않습니다. 연결성을 끊는 것은 쿼리를 거꾸로 보면 연결하는 것과 연관이 있습니다. 즉 쿼리를 순서대로 보지 않고 거꾸로 보며 유니온 파인드로 문제를 해결해 봅시다. 처음에 모든 헛간이 문을 닫은 상태에서 쿼리의 마지막부터 헛간을 다시 열어 나갑니다. 열려있는 헛간들의 연결성을 확인하는 것은 쿼리에 해당하는 헛간의 집합크기를 보면 됩니다. 마지막 ..

Container 이전 글에서 설명한 Assembler의 기능을 Spring이 제공을 해줍니다. 이를 위해 설정 클래스를 만들고 @Bean 어노테이션을 통해 객체를 생성합니다. package config; import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import spring.ChangePasswordService; import spring.MemberDao; import spring.MemberRegisterService; @Configuration public class AppCtx { @Bean public MemberDao memberDao()..

Dependency 한 클래스 내부에서 다른 클래스의 함수를 호출할 때 의존관계가 있다고 할 수 있습니다. 구체적으로 호출한 함수 명을 바꿀 때 다른 클래스 소스코드에서도 변경을 요구하는 관계를 의존이라 합니다. 방식1) 하나의 객체에 다른 객체를 넣는 것을 조립이라 칭하겠습니다. 조립을 할 때는 크게 두가지로 나뉩니다. 첫 번째 방식은 클래스 내부에서 직접 조립할 객체를 생성하는 방식입니다. package spring; import java.time.LocalDateTime; public class MemberRegisterService { //방식1) private MemberDao memberDao=new MemberDao(); ... 방식2) 위처럼 서비스 함수 내에 직접 Dao객체를 생성하는 것..

Maven 스프링이 사용하는 모듈과 플러그인에 대한 관리를 쉽게 해줍니다. 프로젝트의 루트폴더의 pom.xml을 통해 설정파일을 저장할 수 있습니다. 메이븐은 한개의 모듈을 아티팩트라는 단위를 통해 관리하게 되는데, 의존 모듈을 설정하는 것은 소스코드를 컴파일할 때 사용하는 클래스패스에 아티팩트를 추가하는 의미입니다. 아래 5.0.2RELEASE버전의 spring-context모듈을 클래스패스에 추가하기 위한 코드입니다. org.springframework spring-context 5.0.2.RELEASE Repository 아티팩트 파일은 로컬 리포지토리와 원격 리포지토리에서 가져와 사용하게 됩니다. 1차적으로 로컬 리포지토리에서 해당 아티팩트 파일이 있는지 확인한 후 있다면 사용합니다. 만일 없다면..

문제 www.acmicpc.net/problem/16964 알고리즘 DFS 풀이 그래프와 방문 순서가 주어질 때, 올바른지 확인하는 문제입니다. 그래프는 2차원 벡터로 표현이 가능합니다. 문제에서 입력을 받는 순서로 그래프를 만들어 방문하는 대신, 방문 순서를 기준으로 그래프를 정렬합니다. 이후 루트 노드에서 DFS를 수행하면 방문 순서가 빠른 노드부터 방문하게 되므로 해당 방문 순서가 올바른 순서인지 파악할 수 있습니다. 이를 위해 $rev$배열을 만들어 방문 순서가 빠른 노드로 그래프를 정렬하도록 했습니다. 코드 #include #define rep(i, n) for (int i = 0; i u >> v; --u, ..

문제 www.acmicpc.net/problem/11963 알고리즘 greedy 풀이 2$N$개의 카드를 나누어 가져 게임을 진행할 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $N$/2 이전 라운드는 큰 수를 내는 사람이 이기고, 이후 라운드는 작은 수를 내는 사람이 이깁니다. 큰 수 게임에서 bessie가 이길 수 있는 카드들이 있을 때, 최대한 작은 수를 내야 나중의 라운드를 준비할 때 유리합니다. 이를 위해 큰 수 게임을 진행할 때, elsie카드들 중 큰 수부터 처리해 나갑니다. 작은 수 게임도 마찬가지 이유로 elsie카드들 중 작은 수부터 처리해 나갑니다. 이 때 큰 수게임 중 카드를 낼 때, 이길 수 있는 카드들 중에서 작은 카드를 내게 되면 작은 수 게임에서 불리해질 수 도 있습니..

문제 www.acmicpc.net/problem/18874 알고리즘 segment tree 풀이 $j$보다 긴 머리카락들이 $j$가 될 때, badhair의 수를 구하는 문제입니다. 관찰이 조금 필요한 문제입니다. 우선 머리카락 길이가 변하는 것을 생각하지 않고 counting inversion을 할 때 브루트포스로 하면 $N^2$이 필요하고 문제에서 $N$제한은 10만이므로 $NlogN$에 inversion을 셀 수 있는 세그먼트 트리를 이용해야합니다. 쿼리($j$)마다 머리카락 길이를 업데이트를 하려면 아무리 빨리한다 하더라도 $O(N)$보다 빠를 순 없고 inversion을 세면 결국 시간초과입니다. 문제의 핵심은 $j$보다 긴 머리카락들이 $j$가 될 때, badhair을 발생시키는 머리카락들은 ..

문제 www.acmicpc.net/problem/3032 알고리즘 DP 풀이 선영이와 정인이가 게임을 합니다. 번갈아 숫자를 골라가며 고른 수의 인접한 수를 고를 때, 선영이가 이길 수 있는 경우를 세는 문제입니다. 인접한 수를 골라나가며 범위를 좁히는 것에서 DP를 떠올릴 수 있습니다. $solve(l,r,t)$= $l, r$부터 범위를 골라나갈 때, 선영이 차례에서 얻을 수 있는 최대 점수 ($t$가 짝수일 때 선영이 차례) 정인이의 차례($t$가 홀수일 때)에는 최악의 플레이를, 선영이의 차례에서는 최선의 플레이를 하면 선영이가 최대한 이길 수 있게 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..