Next dream Next dream

문제링크 : 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 풀..

문제링크 : 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(..

문제링크 : 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에서 사용된 변수명과 아래 메서드에서 사용된 변수명이 같다면, 역할이..

문제링크 : 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..

문제링크 : 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 가 됩니..

문제링크 : 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..

문제링크 : https://leetcode.com/problems/maximal-square/ Submission : https://leetcode.com/submissions/detail/298397463/ Java Source : https://github.com/skysign/WSAPT/blob/master/LeetCode/221.%20Maximal%20Square/src/Main.java 정사각형의 면적을 구하는 문제입니다. 코딩은 Recursive call을 사용해서, 사각형의 면적을 계산하는 방식을 사용해서 풀었습니다. 이중루프를 사용해서, 모든 위치를 방문해서, '1' 인 위치를 찾습니다. Recursive call을 사용해서, 사각형의 면적을 테두리 부분만 1인지 확인합니다. 이중 루프를 ..

문제링크 : https://algospot.com/judge/problem/read/AMUSEMENTPARK 제출링크 : CPP 코드로 제출한 링크 https://algospot.com/judge/submission/detail/653294 CPP 소스 : https://github.com/skysign/WSAPT/blob/master/algospot.com/AMUSEMENTPARK_cpp/AMUSEMENTPARK/AMUSEMENTPARK.cpp 자바 소스 : https://github.com/skysign/WSAPT/blob/master/algospot.com/AMUSEMENTPARK_java/src/Main.java 정확한 이유는 잘 모르겠지만, 자바코드로 작성해서 올리면, '시간초과'..