ps
-
[SWEA] 3135. 홍준이의 사전놀이Problem_Solving/Graph 2020. 1. 5. 23:49
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS 시간 복잡도를 어림잡아 계산해보니 특별한 알고리즘을 사용하지 않아도 시간 안에 실행될것 같았지만, 문제의 힌트에 Trie라는 개념을 사용하면 된다는 말에, 구글링을 해서 Trie를 익히고 적용하여 풀게 되었습니다. https://twpower.github.io/187-trie-concept-and-basic-problem [Algorithm] 트라이(Trie) 개념과 기본 문제 Practice makes perfect! twpower.github.io 이 분 글..
-
[SWEA] 9092. 마라톤Problem_Solving/DP 2020. 1. 3. 17:00
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Opy-KWPoDFAWY& DP와 찰떡궁합인 문제. DP를 적용하면 너무나 예쁘게 풀립니다. http://colorscripter.com/s/SqvPRIB https://github.com/rundun159/PS/blob/master/Problem_Solving/9092.cpp (제가 구현한 코드입니다.) 제 코드에서 핵심이 되는 matrix는 graph와 cache입니다. 먼저, graph라는 2D array에 각 지점들 사이의 L1거리를 저장합니다. (연산횟수를 줄이기 위함입니다. ..