230929. 알고리즘 문제풀이[10] - 세그먼트 트리, DP

1. 알고리즘 문제풀이 [10]

문제 번호	제 목	유 형
1725	히스토그램	세그먼트 트리
1517	버블 소트	세그먼트 트리
10999	구간 합 구하기 2	세그먼트 트리
14428	수열과 쿼리 16	세그먼트 트리
16975	수열과 쿼리 21	세그먼트 트리
2293	동전 1	동적 계획법
2294	동전 2	동적 계획법
11055	가장 큰 증가하는 부분 수열	동적 계획법
11722	가장 긴 감소하는 부분 수열	동적 계획법
2517	달리기	세그먼트 트리

세그먼트 트리 위주로 문제 풀이를 진행하였다.

지난번 삼성 SW 역량테스트 B형 검정 이후, 세그먼트 트리 공부 필요성을 느끼고
메서드 만들고 기본적인 세그먼트 트리 구조 만드는 방법들을 연습했었다.

그 연장선으로 오늘은 트리를 어떤 값들로 초기화 시켜줘야 할지 생각해보고 결정해야 하는 등 어느정도
응용을 필요로 하는 문제 풀이들을 진행해보았다.

개념을 알고 기본적인 세그먼트 트리 구성은 할 수 있었으나, 이를 응용하여 트리에 어떤 값들을 담아야 할지 등
응용적인 부분에서 사고력이 모자랐기 때문에 일부 문제들은 다시 한 번 풀이를 해봐야 할 것 같다.

특히 버블 소트 문제 같은 경우는 세그먼트 트리로 풀이를 했으나, 병합 정렬로 푸는 방법도 많이 보였다.
요것도 한 번 익혀보는 걸로,,

동적 계획법은 아직 단순한 문제들이 아니고선 스스로 점화식 만드는게 너무 어렵다.
수학 머리가 없어서 그런건지,, 아직 많이 안풀어봐서 그런건지 모르겠는데
하다보면 요것도 익숙해지지 않을까,,, 하는 바램

그래도 부분 수열 DP 문제들은 조금 익숙해 진 것 같다

내일도 화이팅,,