Next dream Next dream

이전 포스팅에서 그래프를 어떻게 코딩할 것인지? 에 대해서 알아 보았습니다. 이번에는 만든 클래스들(Vertex, DirectedEdge)을 가지고 문제를 풀어 보겠습니다. 고대어 사전 / ALGOSPOT / V2 풀이 O(N) 문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 제출링크 : https://algospot.com/judge/submission/detail/664902 문제해설 : https://skysign.tistory.com/197 import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.io.DataI..

문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 이전 포스팅에서 답은 나오지만, 너무 느린 O(N^2) 시간 복잡도를 가진 코드로 작성해서, 이번에는 시간 복잡도를 개선하는 코딩방법에 대해서 알아 보겠습니다. DICTIONARY / ALGOSPOT 문제는 Topological sort를 사용해서 푸는 문제입니다. Topological sort는 그래프에 속해있는 vertex와 edge에 따라서 정렬하는 방식임으로, 우선 그래프(graph)를 어떻게 코딩할지를 알아 보겠습니다. 그래프 코딩 방법 크게 2가지 방법이 있구요, 리스트와 2차원 배열을 이용하는 방식입니다. HashMap과 같은 container를 사용해서, vertex와 edge를 구현하는..

문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 제출링크 : https://algospot.com/judge/submission/detail/664699 자바코드 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/DICTIONARY/src/Main.java Topological sort를 사용해서 문제를 풀 수 있습니다. 우선 Topological sort 공부하실 분들은 여기를 참고하세요. 제가 검색해서 찾은 한글 자료중에는 가장 잘 설명되어 있는 블로그 입니다. 문제를 푸는 과정은 크게 3단계 입니다. 첫번째 단계가, 알파벳 2자의 우선순위를 vertex와 directed edge로 나타 내는 것..

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

이번 포스팅은 알고리즘 문제해결전략 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에 가장 가까운 구간도 함께 찾아 보겠습니다. 이 문제는 구간합(..

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