알고리즘 문제풀이 리뷰3

음 원래는 꾸준히 쓸려고 만들었는데 임팩트 있는 문제들만 정리 하려고만해도 글 쓰는걸 깜빡하게 되네요.

최근에 프로그래밍 대회 나가서 죽쓰고 와서 열심히 작성하려고합니다.

 

거의 한달전에 푼 문제들 리뷰

 

https://www.acmicpc.net/problem/1014

컨닝 P4

분류 : dp, 비트마스킹

 

dp[i][j]를 n번째 줄에 어떤 형태로 앉아있느냐로 정의 

이때 j 는 비트마스킹으로 표현한다.

앉는것 같은경우에 해당위치의 좌 좌상단 우상단을 확인하면 앉을수 있는지 없는지 체크가 가능하다.

 

이를 백트래킹 처럼 끝까지 진행해주면서 경우의수를 count한다.

 

이 문제의 hard는 이분매칭으로만 풀린다고 하니 이분매칭 공부 이후 다시 풀어볼 예정

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj1000-1999/boj1014.cpp

 

https://www.acmicpc.net/problem/1280

나무심기 P4

분류 : 세그트리

 

세그트리 공부하면서 공부하게 된 문제

 

두개의 세그먼트트리를 쓰면서 나무들의 거리합을 좌 우 기준으로 세주는 방식이 신기하다.

나중에 다시 봐야될문제

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj1000-1999/boj1280.cpp

 

https://www.acmicpc.net/problem/9345

DVDs P3

분류 : 세그트리

 

쿼리를 모든 트리마다 주는것이 아니라 핵심은 최댓값과 최솟값을 이용한 세그트리

최소가 A 최대가 B라면 A~B로 채워져있는게 확실하기 때문

 

발상의 전환이 필요해서 좋은 문제인 것 같다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj9000-9999/boj9345.cpp

 

https://www.acmicpc.net/problem/11868

님게임2 P4

분류 : 스프라그그런디

 

스프라그 그런디를 공부하고 돌게임들을 풀어본뒤 처음 풀어본 문제

당연히 접근하는데 어려움을 겪었고 여러개의 게임을 동시에 진행할때는 어떻게 처리해야되는지 이해하게된 문제

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj11000-11999/boj11868.cpp