11월 2째주 PS 정리

32525 Duality S1

#ad_hoc, #geomatry

 

초기에 sweeping 하여 xy를 정렬하여 작은 순서대로 상하좌우 길이1의 직선을 긋는 방법으로 생각하였다.

94%에서 WA를 받았고, edge cases에 대해서 많이 생각을 해보았는데 맞왜틀의 연속

 

입력으로 들어오는 좌표랑 출력해야하는 좌표의 범위가 서로 다른데, 이걸 바탕으로 기울기가 모두 같은 직선을 작성하면 되는 문제 이다.

초기에 너무 많은 case를 맞추어 접근을 잘못하였지만, 새로운 접근법을 찾는 것 보다 edge case를 찾는데 집중한문제

 

http://boj.kr/95ed248e1fb54851843fdd0087b24816

1306 달려라 홍준 P5

#deque_trick

 

덱트릭을 활용해 size 내 구간 별 최대 값을 구하는 문제이다.

새로운 원소가 추가 될 때 마다 현재 처리 중인 원소 li[i]가 덱의 뒤쪽에 있는 원소들보다 크거나 같으면, 그 뒤의 원소들은 더 이상 최대값이 될 수 없으므로 덱의 뒤에서부터 해당 원소들을 모두 제거한다  그 후, 현재 원소의 인덱스 i를 덱의 뒤에 추가한다. 이 과정을 매번 반복해주며, 구간 내 최대값을 출력해주자.

 

세그트리로 구간 별 최대값을 구하는 코드도 가능 할 듯 해 보인다.

http://boj.kr/383006e102234141b3d2edea51db0548

 

14757 Dueling Philosophers G3

#topological_sort

 

문제에서 언급하는 출처와 출처를 인용하는건 그래프의 edge로 똑같이 생각해볼 수 있다.

위상정렬을 한 다음, 위상정렬 한 결과를 DFS했을 때, 한개의 그래프로 구성되어 있다면 1을 출력, 아니다면 2를 출력 하면 된다.

topological sort을 했을 때, cycle이 생긴다면, 0을 출력해주면 된다 

 

http://boj.kr/ab0f18962ce34d4ba1667061e620c74c

11281 2-SAT-4 P3

#2-SAT

 

일반적인 2-SAT을 적용하고 역추적을 어떻게 해야하는가를 물어보는 문제

Tarjan 알고리즘으로 SCC를 구성하였다면, 역순으로 위상정렬된 SCC 그룹에 해를 적당히 부여해주어야 한다.

부여하는 방법을 greedy하게 생각하여 SCC 번호가 큰 순서대로 변수를 할당해보자.

dfs를 수행할 때 깊이가 깊은 것부터 scc 번호가 매겨졌으므로, scc 그룹의 번호가 큰 것이 위상적으로 앞에 위치하기 때문이다. 따라서 scc 번호를 기준으로 내림차순 정렬을 한 뒤, 앞에서부터 false를 매겨주면 된다.

 

http://boj.kr/358a6bcb05014cc48d3a666051723baa

11278 2-SAT-2 S1

#2-SAT, #Bruteforce

 

위 11281 코드를 복붙했지만, 이 문제같은 경우, n이 작기 때문에 2^n 비트배열을 활용하여 bruteforce로 순회가 가능한 것으로 보인다.

14725 개미굴 G3

#trie

 

trie class를 선언해 trie 안에 trie를 넣고.. 이런 방식으로 trie를 구성해주면 된다.

반대로 출력은 trie를 sort해 dfs하여 내림차순으로 출력해주도록 하자

trie 기본 구현문제

굳이 trie 몰라도 다진 트리로 구현가능해 보인다.

 

http://boj.kr/5c728072cea94e258235aa02cb8be233