예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10,20, 10,30, 20,50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력 1복사
6
10 20 10 30 20 50
예제 출력 1복사
4
처음에 이문제는 그냥 중복 제거후 오름차순으로 구현했었다. 하지만 이 문제의 가장 큰 문제는 증가된 부분 수열이고 이게 이 문제의 가장 큰 힌트였다.
즉, 이 문제는
1. 리스트 내 하나의 수를 기준으로 잡고 그 뒤에 나오는 값들을 비교하면서 오름차순으로 증가되는 수열을 찾는 것이다. 그래서 만약 주어진 값이 [5,1,6,2,7,3,8] 이렇게 있으면
2. '5'을 기준으로 증가된 수열을 찾는다면 [5,6,7,8] 이 나올 것이고, '1'을 기준으로 잡는다면 [1,2,3] 나올 것이다.
3. 하지만 이렇게 구현한다면 단점이 생긴다.
만약 주어진 값이 [1,3,4,2,3,4] 일 경우 '1'을 기준으로 잡는다면 [1,3,4] 와 [1,2,3,4]가 나올 것이다.
4. 그래서 이 문제는 DP를 사용해서 풀어야 겠다고 생각을 했고 DP문제는 거의 max(), min()이 나오기 때문에 코드를 작성했다.
-> DP문제는 이전에 계산된 값을 재사용해서 해결하는 방식이고 나는 상향식 접근법을 이용해 for문으로 구현했다. 그러기 위해서는 결과를 저장하는 TABLE이 필요하다. 이걸 나는 dp라는 리스트를 만들었다.
5. 기준을 잡은 숫자와 그 이전의 숫자의 DP 배열의 값을 비교하여 문제를 풀면된다.
n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
for j in range(i):
if a[i] > a[j] and dp[i] < dp[j]:
dp[i] = dp[j]
dp[i] += 1
print(max(dp))
코드 설명
입력값 : n = 6
입력값 : a = [10, 20, 10, 30, 20, 50]
dp = 초기값 : [0, 0, 0, 0, 0, 0, 0]
for문을 다 돌고 난 뒤 : [1, 2, 1, 3, 2, 4]
1. dp 라는 이름의 리스트를 만들고 0으로 초기화를 한다. => dp = [0,0,0,0,0,0]
2. 첫번째 for문으러 값을 지정해준다 .
3. 두번째 for문으로 지정한 값을 이전값들과 비교해준다.
4. if 문에서 a[i] > a[j]는 지정한 값이 이전 값보다 커야하고 dp[i] < dp[j]는 현재 값이 이전 값보다 작으면 현재 dp리스트에 이전 dp 값을 지정한다.
5. for문이 다 돌면 dp[i]에는 0 또는 i 이전의 j 중 dp 값이 큰 dp[j]의 값이 들어 있을 것이다.
◾ 할인 정책은 모든 VIP는 1000원을 할인해주는 고정 금액 할인을 적용해달라고 하였다. 하지만 할인 정책은 변경 가능성이 높다. 회사의 기본 할인 정책을 아직 정하지 못했고, 오픈 직전까지 고민을 미루고 싶다. 최악의 경우 할인을 적용하지 않을 수 도 있다.
◾ 결국 고정할인 정책에서 정률할인 정책으로 변경을 요구하였다...!
1. 요구사항 및 설계
◾ DiscountPolicy 인터페이스가 있으니 그냥 FixDisCountPolicy -> RateDiscountPolicy만 추가로 개발하여 변경한다.
// 할인 정책 역할
public interface DiscountPolicy {
/**
* 할인 대상 금액
*/
int discount(Member member, int price);
}
2.RateDiscountPolicy추가 및 테스트
RateDiscountPolicy
// 새로운 할인 정책
@Component // 각 클래스가 컴포넌트 스캔의 대상이 되도록 에노테이션을 붙여줌
@MainDiscountPolicy
public class RateDiscountPolicy implements DiscountPolicy {
private int discountPercent= 10;
@Override
public int discount(Member member, int price) {
if (member.getGrade() == Grade.VIP) {
return price * discountPercent / 100;
}else {
return 0;
}
}
}
Ctrl + Shift + T 를 누르면 테스트 파일을 생성해준다.
RateDiscountPolicyTest
class RateDiscountPolicyTest {
RateDiscountPolicy discountPolicy = new RateDiscountPolicy();
// 할인 대상일 경우 실행될 테스트
@Test
@DisplayName("VIP는 10% 할인이 적용되어야 한다")
void vip_0() {
//given
Member member = new Member(1L, "memberVIP", Grade.VIP);
//when
int discount = discountPolicy.discount(member, 10000);
//then
assertThat(discount).isEqualTo(1000);
}
// 할인 대상이 아닐 경우 실행될 테스트
@Test
@DisplayName("VIP가 아니면 할인이 적용되지 않아야 한다")
void vip_x() {
//given
Member member = new Member(2L, "memberBASIC", Grade.BASIC);
//when
int discount = discountPolicy.discount(member, 10000);
//then
assertThat(discount).isEqualTo(0);
}
}
◾@DisplayName 은 JUnit5 부터 지원하는 기능으로 테스트 메서드의 이름을 지정해 줄 수 있다.
◾Assertions는 static import 하는게 좋음 (Alt + Enter 누르고 두번째꺼 선택)
3. 방금 추가한 새로운 할인 정책의 문제점은 무엇일까? --> 새로운 할인 정책 적용해보자
OrderServiceImpl
// orderService 구현체 Impl
@Component // 각 클래스가 컴포넌트 스캔의 대상이 되도록 에노테이션을 붙여줌
@RequiredArgsConstructor // => final이 붙은 필드에 대한 생성자를 자동 만들어 준다. >>> lombok 설치 필수 = @Autowired 사용할 필요xx
public class OrderServiceImpl implements OrderService {
private final MemberRepository memberRepository; //인터페이스에만 의존
private final DiscountPolicy discountPolicy; // 인터페이스에만 의존
// private final DiscountPolicy discountPolicy = new FixDiscountPolicy(); // 구현체에 의존, DIP 위반
// private final DiscountPolicy discountPolicy = new RateDiscountPolicy();
// 생성자(OrderServiceImpl) 에서 여러 의존관계도 한번에 주입 가능
// @MainDiscountPolicy 생성자 자동 주입
// @Autowired
// public OrderServiceImpl(MemberRepository memberRepository, @MainDiscountPolicy DiscountPolicy discountPolicy) {
// this.memberRepository = memberRepository;
// this.discountPolicy = discountPolicy;
// }
/**
* 주문 생성
*/
@Override
public Order createOrder(Long memberId, String itemName, int itemPrice) {
Member member = memberRepository.findById(memberId);
int discountPrice = discountPolicy.discount(member, itemPrice);
return new Order(memberId, itemName, itemPrice, discountPrice);
}
//테스트 용도
// public MemberRepository getMemberRepository() {return memberRepository;}
}
◾원래 있던 discountPolicy를 FixDiscountPolicy -> RateDiscountPolicy로 변경하면 된다.
◾But, 이렇게 하면 OCP, DIP를 위반한다.
➔DIP : OrderServiceImpl은 DiscountPolicy 인터페이스에 의존하며 DIP를 지킨 것 같지만 자세히 보면 구현 클래스에도 의존하고 있음. DIP 위반
➔OCP: 그래서 RateDiscountPolicy로 변경하려면 OrderServiceImpl의 소스코드도 함께 변경해야 한다. OCP 위반
4.문제점 해결
OrderServiceImpl
public class OrderServiceImpl implements OrderService{
// private final MemberRepository memberRepository = new MemoryMemberRepository();
private DiscountPolicy discountPolicy;
@Override
public Order createOrder(Long memberId, String itemName, int itemPrice) {
Member member = memberRepository.findById(memberId);
int discountPrice = discountPolicy.discount(member, itemPrice);
return new Order(memberId, itemName, itemPrice, discountPrice);
}
}
◾구체에 의존하지 않고 추상화인 인터페이스에 의존하게 코드 변경
◾But 코드를 실행하면? NullPointerException 발생 (discountPoliy를 구체화하지 않았기때문)
➔ 해결방안 : 이 문제를 해결하려면 누군가 클라이언트인 'OrderServiceImpl'에 'DiscountPolicy'의 구현 객체를 대신 생성하고 주입해주어야 함. ---> Configuration으로 해결
// Member.class
public class Member {
//클래스의 멤버변수는 private 처리를 해서 클래스 내에서만 사용 가능하도록, 하지만 getter, setter 를 사용해 외부에서 읽어올 수 있음
private long id;
private String name;
private Grade grade;
public Member(long id, String name, Grade grade) {
this.id = id;
this.name = name;
this.grade = grade;
}
public long getId() {return id;
}
public void setId(long id) {this.id = id;
}
public String getName() {return name;
}
public void setName(String name) {this.name = name;
}
public Grade getGrade() {return grade;
}
public void setGrade(Grade grade) {this.grade = grade;
}
}
회원 도메인 협력 관계
◾ 클라이언트의 역할 : 회원서비스 호출
◾회원서비스의 역할 : 회원가입 / 회원조희 총 두 가지의 기능을 함
◾회원저장소의 역할 : 세가지 저장소 중 하나를 선택하여 회원 관리
➔ 하지만 [ DB 회원 저장소(자체DB) / 외부 시스템 연동 회원 저장소 ]
이 둘 중 어떤 저장소를 사용할 지미확정이기 때문에
➔ 메모리 회원 저장소를 만들어 개발을 진행한다.(로컬 개발, 테스트 진행용)
회원 도메인 협력 관계
// MemberService.class 회원서비스 역할
public interface MemberService {
void join(Member member);
Member findMember(Long memberId);
}
// MemberServiceImpl.class 회원 서비스 구현체
@Component // 각 클래스가 컴포넌트 스캔의 대상이 되도록 에노테이션을 붙여줌
public class MemberServiceImpl implements MemberService{
private final MemberRepository memberRepository;
@Autowired // 생성자에서 여러 의존관계도 한번에 주입 가능
public MemberServiceImpl(MemberRepository memberRepository) {
this.memberRepository = memberRepository;
} //생성자
/**
* 회원가입
*/
@Override
public void join(Member member) {
memberRepository.save(member);
}
/**
* 회원조회
*/
@Override
public Member findMember(Long memberId) {
return memberRepository.findById(memberId);
}
//테스트 용도
public MemberRepository getMemberRepository() {
return memberRepository;
}
}
// MemberRepository.class 회원 저장소 역할
public interface MemberRepository {
void save(Member member) ;
Member findById(Long memberId);
}
: 저장소는 나중에 교체하기위해 Interface로 추상화 하는건 이해가 가나 Service는 교체 가능성이 없는데 추상화를 하는 이유는? 이 궁금했는데 누군가가 인프런에 질문을 했고, 김영한님이 답변한게 있어서 참조
객체 지향 설계와 스프링 마지막에서 김영한님이 말씀했던 * 이상적으로는 모든 설계에 인터페이스를 부여하자 라는 개념으로 인해 서비스에도 추상화를 사용한 것이다.
실무 고민 * 하지만 인터페이스를 도입하면 추상화라는 비용이 발생한다. * 기능을 확장할 가능성이 없다면, 구체 클래스를 직접 사용하고,
향후 꼭 필요할 때 리팩터링해서 인터페이스를 도입하는 것도 방법이다.
강의에서는 이상적으로 역할과 구현을 분리하는 것에 초점을 맞추어서 이런 부분들도 분리했다.
회원 객체 다이어그램
◾ 객체 다이어 그램 : 실제 서버에 올라왔을 때 객체들의 메모리 참조를 그린 것
◾ 결과적으로 우리가 만들어야 하는 그림
2. 회원 도메인 개발
MemoryMemberRepository - 회원 저장소의 구현체
// MemoryMemberRepository.class 회원 저장소의 구현체
@Component // 각 클래스가 컴포넌트 스캔의 대상이 되도록 에노테이션을 붙여줌
public class MemoryMemberRepository implements MemberRepository {
private static Map<Long, Member> store = new HashMap<>();
@Override
public void save(Member member) {
store.put(member.getId(), member);
}
@Override
public Member findById(Long memberId) {
return store.get(memberId);
}
}
💡 궁금증 1
: store를 만들 때 static을 사용한 이유는?
➔ static 을 사용하면 객체를 생성하지 않고 클래스 이름으로 직접 접근할 수 있으며, 오로지단 한 번만 생성되기 때문에 모든 객체에서동일한 값으로 사용할 수 있다.
➔ 따라서다른 객체 간에 값을 전달하거나 공유하는데 용이하다.
➔ 이러한 static의 특징을 이용하여단 하나의 Map을 사용하기 위해static으로 Map을 생성한 것.
➔ 만약 static을 제거한다면 new MemberRepository(); 를 작성할 때 마다 새로운 Map이 생성되어 객체마다 다른 값의 Map을 가지게 된다.
💡 궁금증 2
: store를 HashMap으로 생성했는데 일반적으로 동시성 이슈를 방지하기 위해 ConcurrentHashMap으로 생성하는게 좋다고 하셨다. 예제를 단순하게 하기 위해 HashMap으로 생성했는데 둘의 차이점은?
➔ HashMap과ConcurrentHashMap은 둘다 'key-value' 형태의 데이터를 저장하는 자료구조이다.
HashMap
- 데이터의 삽입, 삭제, 검색등의 연산이 빠르다
- null 값을 저장할 수 있다
- 싱글스레드 환경에서 안전하게 사용할 수 있다
ConcurrentHashMap
- 내부적으로 데이터를 분할하여 처리하기 때문에 멀티스레드 환경해서 HashMap보다 더 빠른 속도로 동작한다.
- null 값을 저장할 수 없다
- 멀티스레트 환경에서 안전하게 사용할 수 있으며 여러 스레드에서 동시에 접근해도 일관성을 유지한다.
MemberServiceImpl
public class MemberServiceImpl implements MemberService{
private final MemberRepository memberRepository = new MemoryMemberRepository();
@Override
public void join(Member member) {
memberRepository.save(member);
}
@Override
public Member findMember(Long memberId) {
return null;
}
}
💡 궁금증 1
: memberRepository를 만들 때 final로 선언한 이유?
◾ 불변성(Immutability): final 필드는한 번 초기화되면 값을 변경할 수 없다. 이것은 필드에 대한 안정성을 제공하며, 필드 값을 보호한다. memberRepository가 한 번 설정되면 다른 객체로 변경되지 않도록 보장한다.
◾ 스레드 안정성(Thread Safety): final 필드는 다중 스레드 환경에서 안전하게 사용된다. 여러 스레드가 동시에 memberRepository를 수정하려고 시도하는 것을 방지하며, 동시 접근에 대한 문제를 방지한다.
◾ 가독성과 유지보수성: final 키워드를 사용하면 코드의 의도가 명확해진다. memberRepository가 한 번 설정되고 변경되지 않는다는 사실은 코드를 읽는 사람에게 중요한 정보를 전달한다.
◾ 오류 방지: final로 선언된 필드는 컴파일 시간에 한 번 초기화되며, 런타임 중에 다시 설정되는 오류를 방지한다.
3. 테스트 코드 작성
위치 중요
◾ 나중에 빌드하면 테스트 코드는 빠진다고 함
MemberServiceTest
public class MemberServiceTest {
MemberService memberService;
// 테스트가 실행하기 전에 무조건 실행
@BeforeEach
public void beforeEach() {
AppConfig appConfig = new AppConfig();
memberService = appConfig.memberService();
}
@Test
void join() {
//given
Member member = new Member(1l, "memberA", Grade.VIP);
//when
memberService.join(member);
Member findMember = memberService.findMember(1L);
//then
Assertions.assertThat(member).isEqualTo(findMember);
}
}
◾ Assertions Import할 때 "import org.assertj.core.api.Assertions;"
💡 궁금증 1
:Assertions의 기능과 assertThat의 기능 종류
➔ Assertions은 테스트 코드에서 사용되며특정 조건이 참이어야 테스트가 계속 진행되도록 하는 기능이며
➔ assertThat은 다양한 비교 및 검증작업을 수행할 때 사용한다.
➔ assertThat 메서드 종류
String ex1 = "hello wolrd";
String ex2 = "hello wolrd";
◾assertThat(ex1).isEqualTo(ex2); /isNotEqualTo(ex1);: 두 값이 같은지 / 다른지 비교
◾assertThat(ex1).isNull(); / isNotNull(); : 값이 null인지 / null이 아닌지 확인
◾assertThat(ex1).istrue(); / isfalse(); : 값이 true인지 / false인지 확인
◾assertThat(ex1).startWith("hello") / endsWith("wolrd") : 문자열의 시작, 끝 확인
◾assertThat(ex1).contains("hello") : 문자열 특정부분에 포함되는지 확인
등등 많으니까 찾아보기
4. 설계의 문제점
◾ 이 코드는 의존관계가 인터페이스 뿐만 아니라 구현체까지 모두 의존하는 문제점이 있음
private final MemberRepository memberRepository = new MemoryMemberRepository();
➔ 여기서 MemberRepository는 인터페이스에 의존하지만 실제 할당하는 부분은 구현체를 의존하고 있음
def solution(s):
stack = []
for i in s:
if i == '(':
stack.append(i)
else:
if stack == []:
return False
else:
stack.pop()
if stack != []:
return False
return True
Stack을 이용하여서 “좌측 괄호” 일 경우 Stack에 넣어두고 “우측 괄호”가 나오면 Stack에 저장되어 있는 좌측 괄호 값을 빼는 형태로 짝을 찾아가는 형태로 구성
