공부 흔적남기기

이 문제를 처음 봤을떄 각 지점에서 하나씩 좌우로 탐색하면서 찾아야하나? 라는 고민이 들었는데 그럼 먼가 지저분해질 것 같은 기분이 들었다. 그래서 더 좋은 방법을 고민해보았는데 n,m 이 50으로 상대적으로 숫자가 굉장히 낮기때문에모든 정사각형을 탐색하는 것이 더 좋다는 생각이 들었다.  import java.util.*;import java.io.*;class Main { static class XY{ int x; int y; XY(int x, int y){ this.x =x; this.y = y; } } public static void main(Str..

가장 큰 정사각형을 구하기 위해서는 BFS를 통해서 찾을 수도 있겠지만 n,m이 최대 1000이기때문에시간내에 가장 큰 BFS를 찾는 것은 불가능할 것이다.따라서 다이나믹 프로그래밍을 사용해야한다.해당 2차원배열에서 가장큰 정사각형을 찾을때dp[y][x] x는 정사각형 오른쪽 아래에 값으로 현재 정사각형의 최대 크기를 나타낸다. dy[y-1][x-1], dy[y-1][x], dy[y][x-1] 에서 가장 작은것에 +1 한것이 dy[y][x]임을 알 수 있다.  // Online Java Compiler// Use this editor to write, compile and run your Java code onlineimport java.util.*;import java.io.*;class Main { ..

각 집하장들이 있고 하나의 집하장에서 또다른 집하장까지의 최소 거리를 구하되 해당 집하장으로 가기위해서 처음 들려야하는 집하장을 구하는 문제이다.즉 집하장 1에서 집하장 5로 가기위해서는 5라는 비용이 들고 해당 위치로 가기 위해서는 집하장 2를 먼저 가야한다. 먼저 해당 거리까지의 최소 비용을 구한 후  이동할 때 map라는 공간에 어디서 출발했는지를 저장해 놓고 뒤로 돌면서 찾는 방식으로 해결하였다. // Online Java Compiler// Use this editor to write, compile and run your Java code onlineimport java.util.*;import java.io.*;class Main { static class Node{ int..

DP 개념이 2개나 들어간 쉽지 않은 문제다.. 분할의 개수의 최솟값을 구하기 위해서는 모든 구간을 다 탐색하면서 펠린드롬인지 아닌지를 확인해야한다.pal[i][j[는 i~j 구간이 펠린드롬인지 여부를 저장하는 배열이다. pal[i[j]를 구할때 DP 없이 그냥 풀면 O(n^3)이 나온다 이렇게 해도 운이 좋았는지 Pass는 되었다.모든 구간을 탐색하는 코드이다.for(int i =0; i 이를 개선하기 위해 DP를 사용하는데모든 길이가 1인 문자는 펠린드롬, 뒤와 같은 값을 가진 구간은 펠린드롬일 것이고구간 i~j가 만약 펠린드롬이라면 i-1의 문자열과 j+1의 문자열이 같다면 i-1~j+1도 펠린드롬일 것이다.이 개념을 통해 DP를 구현한다.for(int i=0; i구간의 길이가 3인것 구간의 길이가..

일반적으로 우리가 만드는 시스템은 아마도 RDB만 써도 충분히 잘 동작할 것이다.하지만 특정 시점에는 RDB에서 더 나은 성능을 가진 DB(NOSQL)로 넘어갈 필요가 있다. 구조적 현상으로는1. 테이블이 점점 비정규화가 되어가고 Column수가 늘어나며 Table과 관련도가 떨어진 Column이 점점 추가될떄.2. 하나의 Column에 JSON, yml, xml 등 구조화된 데이터를 점점 넣기 시작할떄3. 데이터를 가져오기 위해 많은 조인을 해야하며 재귀적 커리가 늘어날때4. 스키마의 변경이 잦을 때 성능적 현상으로는1. 쓰기 용량이 벅찰 때2. 데이터 셋이 너무 커서 하나의 DB에 저장하지 못할 떄3. 배치 작업이나 분석 쿼리가 트랜잭션의 작업에 부하를 줄때  Non-Relational Datbase..

문제는 각 지점에서 X까지의 최단거리 + X에서 각 지점까지의 최단거리이다. 최단거리 문제를 해결하기 위해서 다익스트라, 벨만, 플로이드 워셜을 고려해볼 수 있는데일단 음수 사이클이 존재하지 않으므로 다익스트라와, 플로이드 워셜을 고민해보았고, 처음에는 모든 정점에서의 거리가 필요할 것 같아서 플로이드 워셜인가 싶었지만,플로이드워셜의 시간복잡도 O(V^3) 1000^3 이라 10억 불가..다익스트라로 해결할 경우 V(logV)E 100 * 8 * 10000 800만 -> 시간복잡도상 더 빠를 것 같고 다익스트라가 손에 더 익숙하기 떄문에 다익스트라로 결정 문제로 넘어와서 dist[][]를 만들고 각점들마다 최단거리를 다 구하고 dist[i][x] + dist[x][i]의 최대값을 구하면 끝나는 문제 im..