전체 글

문제 링크: https://www.acmicpc.net/problem/10942 풀이 다이나믹 프로그래밍 문제였다. 부분 수열의 팰린드롬 여부를 이용하면 전체 수열의 팰린드롬 여부를 구할 수 있기 때문이다. (1) 점화식 세우기 부분 수열을 이용해 현재 수열의 팰린드롬 여부를 어떻게 확인할 수 있을까? 1. 양 끝 숫자를 제외한 부분 수열이 팰린드롬이고, 2. 양 끝 숫자가 같으면 해당 수열도 팰린드롬이다. 이를 코드로 나타내면 다음과 같다. if(dp[i+1][j-1]==1 && num[i]==num[j]) { dp[i][j] = 1; } 여기서 인덱스 에러를 방지하려면 i+1

문제 링크: https://www.acmicpc.net/problem/6086 풀이 에드몬드-카프 알고리즘을 이용하는 문제였다. 처음 보는 유형의 알고리즘이라 좀 힘들었지만, 문제를 풀고 나니 어떤 방식의 알고리즘인지 감을 잡을 수 있었다. (BFS를 통해 시작점에서 도착점까지의 경로를 구한다. (경로를 구해야 하므로, 중간에 방문하는 노드를 기록해야 한다) 도착점에 도달하면 BFS를 종료하고, 도착점에서 시작점까지의 경로를 거슬러 가며 최대 유량을 구한다. 도착점에서 시작점까지 다시 거슬러가면서 파이프의 잔여 용량을 갱신한다. (파이프의 잔여 용량 = 파이프의 기존 용량 - (2)에서 구한 최대 유량) 시작점~도착점까지의 경로가 존재하지 않을 때까지 1~3을 반복한다. 최대 유량의 누적합이 정답이 된다..

문제 링크: https://www.acmicpc.net/problem/1062 풀이 조합과 브루트포스를 이용한 문제였다. 재귀의 깊이와 주어지는 단어의 개수 N을 고려하면 브루트포스가 가능한 문제라는 걸 알 수 있다. 모든 경우의 수를 진행하며 읽을 수 있는 단어의 수를 최댓값으로 갱신해주면 된다. 입력받은 K의 값이 5보다 작으면 0을 출력하고 프로그램을 종료한다. 단어를 읽기 위해서는 a, c, i, n, t 적어도 5개의 글자를 가르쳐야 하는데 가르칠 수 있는 글자가 5보다 작으면 아무 단어도 읽을 수 없다. 접두어와 접미사는 미리 제거한다. a, c, i, n, t는 반드시 가르쳐야 하는 단어이기 때문에, 미리 가르쳤다고 가정하고 조합을 수행할 것이다. 접두어와 접미사를 replace()를 이용하..

인프런 김영한님의 스프링 핵심 원리 - 기본편 강의 내용을 바탕으로 작성한 글입니다. 이전 글에서 다형성만으로는 OCP, DIP를 지킬 수 없다는 것까지 알아보았다. 그렇다면 어떻게 OCP, DIP를 지킬 수 있을까? 바로 DI와 IoC를 이용하면 지킬 수 있다. 간단한 예시를 통해 알아보자. 여기 주문 서비스가 있다. 주문 서비스는 할인 정책을 받아서 할인 금액을 계산해야 한다. 할인 정책은 크게 2종류가 있는데, 고정금액 할인 정책(FixDiscountPolicy)과 고정비율 할인 정책(RateDiscountPolicy)이 있다. public class OrderServiceImpl { // private final DiscountPolicy discountPolicy = new FixDiscount..

인프런 김영한님의 스프링 핵심 원리-기본편 강의 내용을 바탕으로 작성한 글입니다. 이전 포스팅에서 객체 지향 설계를 실현하기 위해서는 다형성을 잘 지켜야 한다는 이야기를 했다. 하지만 객체 지향 설계에 대해 제대로 이해하려면, 다형성 외에도 앞글자를 따서 SOLID라 불리는 객체 지향 설계의 5가지 원칙에 대해 이해해야 한다. SRP: 단일 책임 원칙 (Single Responsibility Principle) 하나의 클래스는 하나의 책임만 가져야 한다. 하나의 책임이라는 말은 모호하기 때문에, 이 클래스가 책임이 하나인지 여러개인지 헷갈릴 수 있다. 이런 경우, 클래스를 변경했을 때의 파급 효과를 보면 SRP를 잘 지켰는지 확인할 수 있다. 예를 들어, 재료 기반 레시피 검색 서비스에서 재료 클래스를 ..

인프런 김영한님의 스프링 핵심 원리-기본편 강의 내용을 바탕으로 작성한 글입니다. Spring이란? 스프링은 문맥에 따라 여러 가지 의미를 갖는다. 스프링 생태계 전체를 의미하기도 하지만, 스프링 DI 컨테이너나 스프링 프레임워크를 의미하는 경우도 있다. 스프링은 여러가지 기술의 모음으로, Spring Boot, Spring Framework, Spring Data 등으로 구성되어 있다. 공식 홈페이지에 가면 아래 사진보다 더 많은 기술들을 확인할 수 있다. 많은 기술들 사이에서도 대표적인 기술이 있다면, 바로 스프링 프레임워크와 스프링 부트이다. 스프링 프레임워크는 오리지널팩에 해당하는 기술로, 스프링 DI 컨테이너, AOP, JDBC 등 다양한 기능을 지원한다. 스프링 부트는 확장팩이지만 요즘에는 필..