google

#implementation 

진짜 구현하면 되는 문제입니다.

A번 문제를 처음 보자마자 이 풀기싫다는 현타가 어마어마하게 오고, 런할까 생각했는데 계산기 템플릿을 복붙해서  만들어 주면 됩니다.

http://boj.kr/7f7717777d2544658b6696660e7056f4

upsolving..

참가를 시작하고 20분뒤인가 이때부터 했는데, 아무도 안풀려있길래 skip 했었다.

#backtracking

백트래킹하여 그래프의 각 node에 대해 인접한 node와 색이 겹치지 않도록 3가지 색 중 하나를 할당 할 수 있는지 check를 계속 해주면 된다.

3가지 색을 체크해야하기 때문에 O(3^k) 안에 코드가 돌아 갈 수 있다.

http://boj.kr/622438ca50134eacaf4a7cf3f34f2fe0

문제를 잘 읽어보면 dijkstra문제인건 쉽게 알아낼 수 있다. 

그리고 dijkstra의 node가 dictonary으로 관리하는 문제인 것도 쉽게 확인 할 수 있다.

예전에 골랜디할 때 풀었던 #14548문제가 생각나서 코드를 복붙해지만 WA받고, weight의 제한이 저 문제랑은 달라서 INF를 더 큰수로 주어서 AC받았다.

입력부분만 dictionary으로 node 번호만 잘 관리해주면 쉽게 풀리는 문제 

http://boj.kr/01ff34478d6b414bad0a051099e511f7

#greedy #sweeping

각 요일별로 예약된 시간 구간을 병합하여 겹치는 부분을 제거하고, 해당 요일의 총 시간에서 예약된 시간을 제외한 사용 가능한 시간 구간을 계산하면 된다.

모든 요일에서 구한 사용 가능한 시간 구간들을 하나의 리스트로 모아서 시작 시간 순으로 정렬하고, 겹치는 부분을 다시 병합해보자.

시간 구간들을 시작 시간 기준으로 정렬하고, 겹치는 구간들을 병합하는 과정에서 스위핑 해주면 된다.

http://boj.kr/fcfcbe6dd3b843c8b34652733acd263a

upsolving...

문제를 잘못 접근한거 같은데,

초기에 접근한 방식은 초기에 점이 정렬되어 있다 보니 각 점 기준 양옆에 점을 대칭하게 정렬하는 최소 cost를 구했는데, 이 방법이 아닌거 같다.

#geometry #physics

어캐 맞췄는지 가장 이해가 안되는 문제

적분 기호 보자마자 이거 뭐 푼다기 보단 공식을 검색해보았고 본인은 이 사이트의 공식을 참고하여 코드로 구현하였더니 맞았다...

https://en.wikipedia.org/wiki/List_of_moments_of_inertia

영재고는 이런거 배우나?

http://boj.kr/b258bb67d5f14626a4dd1d1e18185625

upsolving...

이때 부터는 손을 놨었는데, 문제만 봤을때 바로 든 생각은 query가 보이길래 offline query 관련 최적화 인가 싶었는데, 태그를 보아하니 위상정렬로 풀리는듯 해보입니다..

#ad_hoc

AKARAKA에다가 RAKA를 계속 더하면된다. 관찰해서 찍어맞추면 되는 문제긴한데, 먼가 증명하려고하면 아무래도 palindrom인 성질과, suffix와 prefix가 같아 그런 거일 것이다. 

http://boj.kr/4aceafa38f8d40adb8e83179ef4c3178

#implementation

개빡구현문제다.....

우선 전체 프로세스는 상어를 잡는다 -> 상어 이동 -> 상어끼리 먹는다 이다.

각 프로세스 별 구현해주면 된다. 

상어의 움직임을 수식화하여 매 이동을 하지 않고, 시간을 개선할 수 있을 것 같긴한데, 일단 통과했으니 넘어가자. 개선점이 있어 보인다.

http://boj.kr/01fceb5c23db4d0d842a2efc688f5df2

#ad_hoc, #geomatry

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

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

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

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

http://boj.kr/95ed248e1fb54851843fdd0087b24816

#deque_trick

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

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

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

http://boj.kr/383006e102234141b3d2edea51db0548

#topological_sort

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

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

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

http://boj.kr/ab0f18962ce34d4ba1667061e620c74c

#2-SAT

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

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

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

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

http://boj.kr/358a6bcb05014cc48d3a666051723baa

#2-SAT, #Bruteforce

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

#trie

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

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

trie 기본 구현문제

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

http://boj.kr/5c728072cea94e258235aa02cb8be233