-
[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거리를 저장합니다. (연산횟수를 줄이기 위함입니다. ..
-
[SWEA] 2891. 분수 스도쿠 - DFS & 가지치기Problem_Solving/Graph 2019. 2. 11. 21:34
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do 이 문제를 보고 먼저 든 생각은, 임의의 빈칸에 대해 넣을 수 있는 숫자의 목록을 반환하는 함수를 만들어야겠다 였습니다. 그러기 위해서 그 칸이 포함된 행, 열, 3x2 격자칸을 확인해보고, 분수 칸이라면 다른 쪽(분모라면 분자, 분자라면 분모)에 있는 숫자를 확인해서 1~9 중의 수에서 넣을 수 있는 수를 반환합니다. 그래서 각 빈칸마다 넣을 수 있는 수의 목록을 반환 받아서 하나씩 넣어보면서 막힌다면 다시 되돌아와서 다른 수를 넣어보는 식으로 하면 되겠죠. 그런데 이 문제의 제한 시간은 1초입니다. 만약 이 문제..
-
[SWEA] 1265 달란트2 -OthersProblem_Solving/Others 2019. 2. 7. 20:46
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18R8FKIvoCFAZN&categoryId=AV18R8FKIvoCFAZN&categoryType=CODE 음... 예시로 주어진 문제들을 풀다보면 중간값에 가까운 값들로 곱하면 최대값을 구할 수 있는 것을 알 수 있게 됩니다. 우선 한 묶음 당 n을 p로 나눈 개수만큼 달란트를 넣고, 남은 달란트들을 한개씩 묶음들에 넣어주면 이 문제에서 요구하는 최대값을 구할 수 있습니다. 수학적으로 증명하고 싶었지만... 어떻게 증명 해야할지 잘 모르겠네요... ㅠㅠㅠ 혹시 알려주실 수 있으신 분이..
-
[SWEA] 1248. [S/W 문제해결 응용] 3일차 - 공통조상 -GraphProblem_Solving/Graph 2019. 2. 6. 23:14
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD 이 문제는 크게 두 부분으로 나눠집니다. 1. 트리에서 공통 조상 찾기 2. 부분 트리안에 있는 노드 수 구하기. 먼저 트리를 어떻게 표현할건지 고민했는데 구조체/클래스로 표현하기보다는 이 문제의 경우에는 부모-자식 관계를 배열로 저장하면 좋을것 같았습니다. 이렇게요 ㅎㅎ child의 개수는 0이상 2 이하일수 있으니 2차원 벡터로 설정했습니다. 이렇게 하면 자손 노드의 개수를 쉽게 파악할 수 있겠죠. http://colorscripter.com/s/QNYFdth
-
[SWEA] 1245. [S/W 문제해결 응용] 2일차 - 균형점 - Binary SearchProblem_Solving/Binary Search 2019. 2. 6. 16:48
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD&categoryId=AV15MeBKAOgCFAYD&categoryType=CODE&&& 우선, 가능한 균형점의 위치가 정수가 아닌 실수이기 때문에, 가능한 범위를 모두 탐색해보는건 불가능합니다. 무한히 많은 후보가 존재하기 때문이죠. 이 문제를 읽으면서 제가 괜히 궁금해 졌던건 n-1개의 균형점이 꼭 자성체들 사이의 n-1개의 구간들에 하나씩만 배치 되는가, 즉 두개의 자성체 사이에 두 개 이상의 균형점이 존재할 수 있는가 였습니다. 문제를 읽다보면 자연스럽게 ..