https://www.acmicpc.net/problem/13308 DP를 쓸 생각을 못함..진짜 1시간30분~2시간 정도 고민해서 겨우 구현 아이디어 떠올렸는데 반례가 있네 ㅠㅠ1번 노드에서 다익스트라 쫙 돌려서 임의의 K번 노드까지 가는 비용 구한 다음에K번노드에서 마지막 노드까지 가는 비용 구해서최단거리 구하는 방식으로 했음.(K번 노드까지 "손해를 보면서(위험을 감수하고)" 도달한 다음 싼 값에 기름 쫙 충전에서 도착지까지 가는 방법) 그런데 이렇게하면 위험을 감수하고 도달하는 노드가 하나일 경우까지만 작동함..!1번노드에서 2번노드가서 기름채우고2번노드에서 1번노드 돌아와서 3번노드가서 기름 다시 채우고3번노드에서 1번노드간 다음에 4번노드로 가는 케이스에는 틀리는 코드임..!! 이 경우 DP를..

https://www.acmicpc.net/problem/5719 다익스트라 응용 문제.역추적 아이디어가 필요. 내가 실수한 부분은 여러가지임1. arraylist remove되는지 안되는지를 몰랐는데 -> 해보니까 안됨.    그래서 remove확인 하는법 확인하려고 답지를 봤는데 답지에서도 remove안씀. flag를 씀..     반성해야함 remove안되면 다른 방법 모색했어야했는데 무조건 remove된다고 생각했음.     실전스럽지 못했음.2. 방문한 최단경로를 [V][V]에 저장했는데 이렇게하니까 메모리초과뜸.     [E]에 저장하는게 25배 메모리 덜 소요.3. DP적 사고도 해줘야함. 이미 방문한 노드에 대해서는 쓸데없는 계산하지 않도록..!! 얻어 갈 것이 굉장히 많은 문제로 보임!!..

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { static int V, E, S, dist[], INF=987654321; static ArrayList> e; // 시작노드 하나에 여러 도착노드(간선)이 있을 수 있으므로 리스트 2개 + int배열(도착노드, 비용)으로 선언 static PriorityQueue pq; // 도착노드, 비용을 담을 pq를 선언. pq에서 가장 저렴..

https://www.acmicpc.net/problem/2243  인덱스트리의 알고리즘의 query방식을 left right말고 cnt로 변형해서 풀면 풀리는 문제.문제 아이디어는 떠올렸는데 이를 코드로 구현할 수 있을지에 대한 확신이 없어 해당 아이디어가 작동할지에 대한 확신을 못함.그래서 잠깐 강사님 답 봤는데 내가 생각했던 아이디어가 구현된 것을 tree[node*2]로 돼있는 것을 보고 아! 구현하면 되겠다 해서 구현해서 정답 맞춤. 인덱스 트리에서는 tree[node*2], tree[node*2+1]로 자식 노드값 구하기가 되게 쉬운 점을 알고 있었으면 확신할 수 있었을 것임.무작정 암기보다는 이제는 그 원리도 함께 파악해놓자.  아 그리고 이것도 구간 압축해야하나 고민했는데사탕 맛 개수가 1..

https://www.acmicpc.net/problem/1517  2517 달리기 문제와 푸는 방법이 동일함.값 자체를 쫙 펼쳐서 인덱스 트리의 리프노드로 설정한다는 idea가 필요Collection sort를 이용해 구간압축을 하고, 인덱스트리로 노드값을 ++해주면 됨. 달리기 문제를 6시간 전에 공부했어 어렵지 않게 풀어냄! long을 int로 하는 실수만 제발 주의하자!이 실수 계속함..!! import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.lang.reflect.Array;import java.util.ArrayList;import java.util.Collecti..

https://www.acmicpc.net/problem/2042  인덱스트리만 암기하고 있으면 바로 풀리는 문제자료형(long)과 diff가 아니라 변화할 값이 입력으로 주어지는 것에만 주의하면 된다. 인덱스 트리 알고리즘은 잘 작성했는데 코드가 잘 작동하지않아 당황했다. 자료형과 diif가 아니라 변화할값이 입력으로 주어지는 것에 주의하지 못했다. 약간 신경론적으로 인덱스트리 알고리즘을 잘 작성했는지에 신경을 집중하다 보니 위 간단한 포인트들을 놓치게 된 것 같다. 인덱스 트리 알고리즘 작성에 확신을 가질 정도로 암기해 익숙해져야 할 듯 하다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReade..

https://www.acmicpc.net/problem/7453  투포인터로 풀어야 시간복잡도가 가장 줄어드는 문제^2의 조합을 계싼해야할 때 투포인터를 사용하면 시간복잡도를 선형으로 줄일 수 있음..!! import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int N, A[], B[], C[], D[]; static int first[], second[]; public static void main(String[] args) thr..

https://www.acmicpc.net/problem/3020 이분탐색임을 알고 있었고, 종유석, 석순 각각의 높이를 강의에서 따로 저장했던 기억이 있었음.+ 직전에 이분탐색, lowerBound, upperBound 알고리즘을 이해 및 암기하였음 이를 바탕으로 문제 아이디어, 구현까지 전부 해냄.다만, 종유석의 lowerBound구할 때 target으로 어떤 값을 넣어야할 지에 대해 한 번 틀려서 노트에 필기하면서 오류 찾아냄.배열의 인덱스에 대해 안햇갈리게 지정하는 방법을 모색해야할 듯. 전반적으로 잘 풀었음!! GOOD 나중에 lowerBound, upperBound 코드 까먹지 않게 복습해야함. 이분탐색은 해당 값 or target값 위치 아무 곳 반환lowerBound는 target 이상의 ..