Problem_Solving
-
[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개의 구간들에 하나씩만 배치 되는가, 즉 두개의 자성체 사이에 두 개 이상의 균형점이 존재할 수 있는가 였습니다. 문제를 읽다보면 자연스럽게 ..
-
[SWEA] 1247. 최적 경로 -DPProblem_Solving/DP 2019. 2. 3. 19:38
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE 문제를 읽고 짧은 시간 안에 해결해야 하는 문제인줄 알고 겁부터 먹었지만 모든 가능한 경로를 살펴서 해를 찾아도 좋다기에 신나는 마음으로 완전 탐색을 적용할 생각을 했습니다. ㅎㅎ 문제 형태를 보아하니 주로 쓸 함수를 이렇게 정의하면 좋을것 같더라고요. ㅎㅎ visited에는 현재까지 방문한 고객들을 비트마스크를 이용해서 표현하고, last는 마지막으로 방문한 고객의 index를 ..