전체 글
BOJ 2515 - 전시장
www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1> N >> S; for (int i = 1; i > arr[i].first >> arr[i].second; sort(arr + 1, arr + N + 1); for (int i = 1; i
BOJ 3197 - 백조의 호수
www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 이 문제는 두가지 방식으로 풀 수 있다. 하나는 BFS 를 두 번 사용해서 푸는 방법과 또 다른 하나는 Disjoint-Set 과 BFS 를 섞어서 푸는 방식이 있다. 나는 BFS 를 두번쓰는 방식으로 처리하였다. 먼저 입력 받을때, 백조의 좌표를 따로 저장하고 (vector swan), 물의 좌표를 저장한다 (queue water_queue) 물의 좌표를 저장하는 이유는 하루씩 지..
BOJ 1450 - 냅색문제
www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 meat in the middle 이라는 알고리즘을 써서 풀어야 하는 문제이다 (참조) meat in the middle blog.naver.com/PostView.nhn?blogId=kks227&logNo=221382873753&proxyReferer=https:%2F%2Fwww.google.com%2F 밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25) 안녕하세..
BOJ 1826 - 연료 채우기
www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 이 문제는 그리디 방식으로 풀어야 하는문제다 왜냐면, 가지고 있는 연료의 양이 제한적이고, 주유소를 최소한으로 방문해야 하기 때문이다. 정렬의 기준은 현 위치에서 주유소 까지의 거리가 가까운 순서대로 정렬한다 그리고 목적지 까지의 거리(L) 와 현재 보유하고 있는 연료량(P) 을 비교했을때, P 가 더 적은 경우 주유소를 방문해서 충전을 해야만한다. 그리고 우선순위 큐(최대..
BOJ 1202 - 보석 도둑
www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제는 백준 1781 컵라면 (www.acmicpc.net/problem/1781) 문제와 코드 구조가 거의 비슷하다. 그리디와 우선순위 큐를 이용해서 풀어야 하는 문제 유형이다. 이 문제를 보고, 보석 가격이 비싼 순서대로 정렬하고, 가방이 무게 제한이 낮은 순으로 정렬해서 하나하나 비교해도 되지 않나라고 생각할 수 있지만, N 과 K 의 최대값..
Spring Framework - AOP Overview
참조한 강의 : Spring & Hibernate For Beginners (www.udemy.com/course/spring-hibernate-tutorial/) - AOP (Aspect-Oriented Programming) : AOP 는 Aspect-Oriented Programming 의 약자이다. 객체 지향 프로그램 개발시에, 서로 다른 클래스라 할지라도, 비슷한 기능을 하는 부분이 존재할 수 있다. 반복해서 서로 다른 클래스에 나타나는 이런 코드나 메소드들을 각 클래스에 따로 따로 작성하기 보다는 하나의 모듈로 묶어서 처리한뒤, 개별 클래스에 위임(Delegation) 하는 방식이 더 유지보수가 쉬울것이다. 이런 공통되는 기능을 Cross-cutting Concern 이라 부른다. AOP 는 ..
Spring Framework - Layered Architecture
참조한 강의 : www.boostcourse.org/web326/lecture/58982/ - Layered Architecture : 큰 규모의 기업용 소프트웨어를 개발할때는, 단순히 개인의 토이프로젝트 처럼 아무런 구조 없이 막 짜내는게 아니라, 일정한 구조를 가지고 설계되어야 한다. 그래서 소프트웨어 개발이전에 설계 단계를 거치고, 이때 자주 사용되는 아키텍처들을 패턴화해서 묶어놓은 것을 아키텍처 패턴이라 부른다. 레이어드 아키텍처는 이 아키텍처 패턴 중 하나로, N-Tier Architecture 라고도 불리며, 이름에서 알 수 있듯, 여러개의 레이어를 나눠놓고 각 레이어마다 서로 다른 기능을 담당하도록 분리해 놓은 것을 말한다. 각 레이어가 서로 독립적이며, 아래 그림에서 보듯이, 위에서 아래로..
BOJ 5557 - 1학년
www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 이 문제는 DP 를 써야 풀 수 있다. 이 문제에 대한 점화식은 다음과 같다 dp[i][j] = k : i 번째 위치에 있는 숫자로 j 가 있을때 (j 의 범위는 0 ~ 20) 가능한 경우의 수 k 문제에서 제시한 예제입력1 을 예로 들면 11 8 3 2 4 8 7 2 4 0 8 8 의 경우, 첫번째 수 8에 대해서는 dp[1][8] = 1 이 성립한다 (첫번째 위치에 들어가는 숫자 8은 경우의 수가 딱..