전체 글
-
TRAVERSAL 트리 순회 순서 변경 / ALGOSPOTALGOSPOT 2020. 3. 2. 10:52
문제링크 : https://algospot.com/judge/problem/read/TRAVERSAL 제출링크 : https://algospot.com/judge/submission/detail/659612 자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/TRAVERSAL/src/Main.java 알고스팟의 TRAVERSAL 문제를 풀어보겠습니다. 이 문제는 바이너리트리를 사용하여 푸는 문제로, pre-order, in-order로 방문한 결과를 가지고, post-order로 방문한 결과를 출력하는 문제입니다. 문제를 풀기전 떠올려야 할 내용이 바로, pre-order, in-order는 방문한 순서만 다르다는 점입니다. 따라서, pre-ord..
-
합이 0에 가장 가까운 구간 / 알고리즘 문제해결전략 2권ALGOSPOT 2020. 2. 19. 17:40
이번 포스팅은 알고리즘 문제해결전략 2권의 601페이지에 나오는 '합이 0에 가장 가까운 구간' 예제 입니다. 자바 코드 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/%ED%95%A9%EC%9D%B4%200%EC%97%90%20%EA%B0%80%EC%9E%A5%20%EA%B0%80%EA%B9%8C%EC%9A%B4%20%EA%B5%AC%EA%B0%84/src/Main.java 우선 제목에서 가장 '가까운 구간' 이라고 해서, 책의 내용이 구간을 찾는 풀이로 오해 하실 수 있습니다. 책에 있는 내용은, 0에 가장 가까운 구간합을 찾는 것입니다. 여기서는 합이 0에 가장 가까운 구간도 함께 찾아 보겠습니다. 이 문제는 구간합(..
-
PACKING 여행 짐 싸기 / ALGOSPOTALGOSPOT 2020. 2. 9. 12:00
문제링크 : https://algospot.com/judge/problem/read/PACKING 제출링크 : https://algospot.com/judge/submission/detail/656203 자바코드 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/PACKING/src/Main.java 유명한 문제인 Knapsack 문제에서, 아이템이 목록을 출력하는 부분이 추가된 문제입니다. Knapsack문제가 처음이신 분들은 atcoder.jp의 educational DP 문제 중에 D - Knapsack 1 먼저 풀어보시는 것을 추천합니다. 해당 문제의 풀이는 D - Knapsack 1 풀이 여기를 참고하세요. 참고로, D - Knapsack 1 풀..
-
TRIPATHCNT 삼각형 위의 최대 경로 수 세기 / ALGOSPOTALGOSPOT 2020. 2. 7. 14:59
문제링크 : https://algospot.com/judge/problem/read/TRIPATHCNT 제출링크 : https://algospot.com/judge/submission/detail/655903 자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/TRIPATHCNT/src/Main.java 2차원 DP를 2번 풀어야 하는 문제입니다. 첫번째 풀어야할 문제는 TRIANGLEPATH 문제에서 푼건 처럼, 누적합을 계산하고 dp_{i,j}에 저장합니다. 두번째 풀어야 할 문제가, 경로의 개수를 세는 문제입니다. (i, j)에서 경로의 개수를 세는 문제를 countPath(i, j) 라고 정의 하면, 아래 3가지 경우로, countPath(..
-
LIS Longest Increasing Sequence / ALGOSPOTALGOSPOT 2020. 2. 5. 19:10
문제링크 : https://algospot.com/judge/problem/read/LIS 제출링크 : https://algospot.com/judge/submission/detail/655189 자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/LIS/src/Main.java 이 문제는 1차원 DP 문제로, O(N^2)로 풀수 있는 문제입니다. 아래의 LIS()메서드를 참고하세요. 문제 푸는 것 보다, 책의 코드 8.12 li3()함수를 이해하는 것이 더 어려웠던 문제입니다. 보시는 분들의 이해를 돕기 위해서, lis3() 함수를 자바 버전으로 구현해 봤습니다. (코드 8.12에서 사용된 변수명과 아래 메서드에서 사용된 변수명이 같다면, 역할이..
-
TRIANGLEPATH 삼각형 위의 최대 경로 / ALGOSPOTALGOSPOT 2020. 2. 5. 18:52
문제링크 : https://algospot.com/judge/problem/read/TRIANGLEPATH 제출링크 : https://algospot.com/judge/submission/detail/655087 자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/TRIANGLEPATH/src/Main.java 아래로 내려가거나, 오른쪽 아래 2가지 방향으로 내려간다는 점에서, recurrence relation을 아래와 같이 정의 할 수 있습니다. 트라이앵글의 높이가 N 트라이앵글로 입력된 데이터를 map[][] 행렬이라고 가정 \begin{aligned} dp_{i,j} = max(dp_{i-1,j} + map_{i,j}, dp_{i-1,j-1..
-
QUADTREE 쿼드 트리 뒤집기 / ALGOSPOTALGOSPOT 2020. 2. 3. 10:10
문제링크 : https://algospot.com/judge/problem/read/QUADTREE 제출링크 : https://algospot.com/judge/submission/detail/654647 압축을 풀었다가, 압축을 다시 하는 방법으로 접근해서는 않됩니다. 시간도 너무 오래 걸리고, 사용하는 메모리 양도 너무 많습니다. 따라서, 압축을 풀지 않은 상태로 뒤집는 방법을 찾는 방향으로 접근해야 합니다. 우선 x 안에 x 가 또 있는 경우를 제외하고, 풀이를 알아 보겠습니다. xwwbb 입력을 받았다고 하고, wwbb 부분을 c1, c2, 3, c4로 바꿔써 보겠습니다. x, c1, c2, c3, c4 가 되구요, 이것을 문제에서 요구한 대로 뒤집어 보면 x, c3, c4, c1, c2 가 됩니..
-
BOGGLE 보글 게임 / ALGOSPOTALGOSPOT 2020. 2. 2. 23:43
문제링크 : https://algospot.com/judge/problem/read/BOGGLE 제출링크 : https://algospot.com/judge/submission/detail/653737 자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/BOGGLE/src/Main.java DP로 풀어야 하는 문제입니다. exhaustive search 전부다 찾으면, 시간이 너무 오래 걸림니다. 게임판이 모두 a 로 채워저 있고, 찾아야하는 단어가 aaaaab 라고 한다면, exhaustive search로 찾을 때, 모든 칸을 방문합니다. 마지막에 b 가 없어서 찾지 못하고, NO를 출력합니다. 문제 처음에 풀때, Recurrence relat..