tistory에서 옮겨왔습니다
후기
오늘 셋은 다시 내가 만들었다.
기초를 알고 있다면 적어도 1문제는 얻어갈 수 있도록 구성해 놓았다. 1문제 정도는 무조건 풀 수 있게 되어있다.
그리고, 플레는 다들 꺼리기 때문에 알고리즘을 이용하는 어려운 문제가 아닌 자료구조를 이용한 실수를 할 수 있는 문제로 골랐다. 덕분에 푸신 분이 있었다.😆
결론적으로 나는 상당히 만족스러웠다. (애드 혹 꺼져)
흠흠... 풀이를 여럿이 써서 그렇기도 하고,
저 자체도...
뭔가 말투가 정해지질 않아서 중간중간 바뀌네요...ㅋㅋㅋ
Ⓐ 합 (1132)
by mc_progw12
그리디 문제입니다. 각 알파벳의 계수의 총 합을 따져서 큰 것부터 가능한 한 큰 수를 넣을 수 있도록 합니다.
Ⓑ 검열 (3111)
by mc_progw12
스택 두 개, 또는 덱 두 개로 앞 뒤로 받는 스택, 또는 덱으로 가능하다고 합니다.
Ⓒ 그대, 그머가 되어 (14496)
by hgmhc
가중치가 없는 그래프를 다익스트라로 풀겠다는 것은 소 잡는 칼로 닭 잡는 격입니다.
그래서 BFS로 풀어야 합니다. (간선 수=길이)
정말로 BFS 구현에서 1도 벗어나지 않습니다.
정말정말 전형적인 BFS 코드입니다.
Ⓓ 덱 (10866)
by hgmhc
못 푸셨으면 STL에 서툰 것으로 보입니다. 레퍼런스 페이지 등을 통해 공부하시기를 추천드려요.
Ⓔ 1학년 (5557)
by hgmhc
일단, 쉽게 관찰할 수 있는 것이 있습니다.
완전 탐색 (Brute-Force) 을 이용한다면 의 미친 시간 복잡도가 나와버립니다.
따라서 시간을 획기적으로 줄여줄 만한 솔루션을 고민해 보아야 합니다.
그럼 뭘로 풀어낼 수 있을까요..?
일단 매 단계마다 가능한 값의 경우가 21개,
느낌으로 어떠한 작업을 해주는 것이라면, 괜찮을 것 같다는 느낌이 듭니다.
그리고 생각해보니, 매 단계마다 나올 수 있는 값들을 메모하는 방식으로 나아간다면 결국 재귀적인 구조를 띌 것만 같습니다.
그래서 DP를 이용하도록 합시다.
DP인데, 이면 넉넉하고, 20개 정도의 높이를 해줘도 칸, 넉넉하니 이 정도 메모리는 과감하게 내어줍시다.
-끄읕-
