공부 흔적남기기

이 문제를 처음 봤을떄 각 지점에서 하나씩 좌우로 탐색하면서 찾아야하나? 라는 고민이 들었는데 그럼 먼가 지저분해질 것 같은 기분이 들었다. 그래서 더 좋은 방법을 고민해보았는데 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인것 구간의 길이가..

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

최단 거리 문제이다. 최단 거리 문제는 보통 BFS를 통해서 구할 수 있는데 BFS를 이용하면 DFS보다 그래프의level 단위로 검사하기 때문에 일반적으로 더 빠르고 안정적으로 최단거리를 구할 수 있다. 이떄 가중치가 존재한다면 다익스트라, 벨만포드, 플로이드중 하나를 사용해야하는데 이 문제는 시작점이 3개로 고정이고, 음수 사이클이 존재하지 않기 때문에 다익스트라를 통해서 구현하면 된다. 문제 설명 1에서 N까지 움직이는데 경유점 c1, c2를 반드시 거쳐서 도달해야한다그럼 총 2가지 경우의 수가 나올 것이다 1 -> c1 -> c2 -> N1 -> c2 -> c1 -> N 1에서 시작하는 최단거리 c1에서 시작하는 최단거리 c2 에서 시작하는 최단 거리를 구한후 2가지 경우에 대해 MAX 값을 처리..

위상정렬이란 정해진 순서가 있고 해당 순서대로 정렬한 것을 의미한다.정해진 순서란 작업들 간의 관계이다. 즉 의존하고 있는 작업이 반드시 의존 되고 있는 작업보다 뒤에와야 한다.예를들어 A가 B를 의존하고 있다고 가정하면 B A 순서여야한다. 1학년 때 알고리즘 기초를 수강해야 2학년때 알고리즘 심화를 들을 수 있는 것과 같다. 위상정렬은 인접행렬과 인접리스트로 구현할 수 있는데 이때 인접행렬은 시간복잡도가 O(V^2) 이고 공간 복잡도도 마찬가지이다 하지만 인접리스트는 시간복잡도가 O(V+E) 이며 공간 복잡도는 O(V+E)이다 인접 행렬을 사용하여 메모리가 초과가 난 코드 32000 * 32000 *4 거의 4000MB를 사용하게 되어 메모리 초과가 발생한다.시간 복잡도도 1초를 넘길 수 있다.imp..

해당 문제는 상호배타적 집합의 아주 좋은 예시이다DFS BFS 등 그래프 탐색으로도 풀 수 있지만 하나의 정적 배열을 통해 같은 노드들 끼리 연결하면 더 쉽게 해결할 수 있다. import java.io.*;import java.util.HashSet;public class 연결요소의개수11724 { static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWr..

문제의 요점은 n이 커지면서 팩토리얼의 값을 변수에 저장할 수 없다는 것이다.그럼 고민해봐야할게 어떨 때 숫자가 0으로 끝나는지 고민해봐야한다. 차근 차근 10부터 50, 100, 150, 1500, 10000, 0으로 끝나는 숫자들을 확인해보면 1*10, 5*10, 15*10, 15*10*10, 10*10*10*10 인것을 알 수 있다. 즉 문제의 답은 해당 숫자에 10이 얼마나 들어가 있는지 확인해보면 된다, 그럼 각 반복문을 돌면서 10으로 나눠 떨어진다면 10으로 계속 나눠주고 count를 해주면 될까? 안된다. 왜냐하면 10은 2 * 5의 구성으로도 가능하기 때문이고 팩토리얼은 연속된 숫자들의 곱으로 이전 값에 영향을 받는다, 따라서 해당 숫자가 10으로 나눠 떨어질때까지 반복하고 5로 나눠질때..

문제는 간단하다 내가 소유하고 있는 카드들과 존재여부를 확인하고 싶은 카드들을 입력받는다. 범위를 보면 -10000000~10000000 로 int로도 처리 된다. 나는 처음에 생각한게 먼저 단순히 target을 python의 in연산자로 찾으면 O(N)의 시간 복잡도로 찾아지게 되므로 시간초과가 뜰 것같았다. 그래서 리스트에서 값을 찾을 때 O(logN)의 속도로 찾을 수 있는 이분탐색을 사용해서 찾을려고 했다. 근데 멍청하게 O(logN)에서 찾은 애들은 remove를 시켜주겠다는 생각을 했다. list에서 remove를 해주는 것이 더빠르다고 생각해서 remove를 해주었다. 하지만 일반 적인 생각말고 시간복잡되 관점에서 remove는 찾는 것과 마찬가지로 O(N) 시간복잡도를 가진다. 그래서 O(..