Next dream Next dream

문제링크 : https://www.acmicpc.net/problem/4991 제출링크 : https://www.acmicpc.net/source/19521047 자바소스 : https://github.com/skysign/WSAPT/blob/master/BOJ/4991%EB%B2%88%20%EB%A1%9C%EB%B4%87%20%EC%B2%AD%EC%86%8C%EA%B8%B0/src/Main.java 로봇 청소기가 2차원으로 전후좌우 4가지 방향으로 이동하면서, 쓰레기를 모두 치울 때, 로봇 청소기가 이동하는 거리가 가장 짧은 거리를 찾는 문제입니다. 우선, 이동하는 경로가 아니고, 이동하는 거리를 찾는다는 것을 고려해서, 풀어야 합니다. 문제에서 로봇 청소기와 쓰레기라고 표현하고 있지만, 로봇 청소기와..

문제링크 : https://www.acmicpc.net/problem/1976 제출링크 : https://www.acmicpc.net/source/18943097 자바코드 : https://github.com/skysign/WSAPT/blob/master/BOJ/1976번 여행 가자/src/Main.java 1717번과 비슷하게 풀 수 있는 문제로, union find 를 사용해서 풀 수 있습니다. 문제의 아래 문장을 통해서, union find 로 풀 수 있다는 것을 유추할 수 있습니다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 길은 B-C..

문제링크 : 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로 나타 내는 것..

13398번 연속합 2 / BOJ 문제링크 : https://www.acmicpc.net/problem/13398 제출링크 : https://www.acmicpc.net/source/18618083 자바소스 : https://github.com/skysign/WSAPT/blob/master/BOJ/13398%EB%B2%88%20%EC%97%B0%EC%86%8D%ED%95%A9%202/src/Main.java 이 문제를 풀기 전에, 1912번 연속합 / BOJ 문제를 꼭 풀어보시고, 여기 참고하세요 → https://skysign.tistory.com/193 Dynamic Programming과 Prefix Sum을 사용해서 푸는 문제입니다. 이 문제에 대한 설명은 여기 참고하세요 → https://coo..

1912번 연속합 / BOJ 문제링크 : https://www.acmicpc.net/problem/1912 제출링크 : https://www.acmicpc.net/source/19909239 유튜브 문제풀이 : https://www.youtube.com/watch?v=dAtNiVwnTN4 자바코드 : https://bit.ly/3dWeknw 어떻게 푸는 문제인지 좀 고민하다가, 이 문제가 잘 설명된 글을 찾았습니다. 여기 참고하세요. → https://debuglog.tistory.com/79 1차원 DP로 푸는 문제입니다. $$ dt_i $$ dt_i 가 i 번째 입력 받은 값, (data를 줄여서 dt) 이라고 하고, $$ dp_i $$ i 번째 입력까지 고려했을 때, 최대 연속 부분합 코딩을 좀 쉽..

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

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