걸음마부터 달리기

감도 안잡혀서 빠르게 답 봤다.처음엔 List로 대충 구현하면 될거같은데 싶었다가 시간제한 보니 자바는 2초길래 명령어 개수가 최대 500,000개이면 O(NlogN)에서 무조건 끊어야되는데 싶었다. 그럴려면 List로 하는 순간 ArrayList는 삽입하는 순간 뒷 데이터 전부 밀어야해서 O(N), LinkedList는 찾는 과정에서 O(N)이라 이것을 각각 반복하면 O(N^2) 으로 타임아웃이 불 보듯 뻔했다. 커서고 뭐고 일단 처음 들어간게 가장 먼저 나오길래 큐인가 싶었는데 그러면 커서부분을 어떻게 해야되지? 큐  중간에 넣어야하는데? 에서 문제가 발생했다.  큐 중간에 넣어버릴수가 없으니 (스택도 마찬가지고) 커서 있는걸 기준으로 서로 다르게 쪼갰어야 했다. 쪼개기만 하면 큐로는 구현이 안되고 ..

우선순위 큐만 알면 쉽게 풀리는 문제이다.그러기에 우선순위 큐를 알아보자. 일반적인 큐는 FIFO의 구조로 오로지 들어간 순서에만 영향을 받는다. 따라서 이미 들어간 순간 내가 임의로 순서 조작을 하지는 못한다. 내가 어떤 순서로 큐로 넣었던 간에 큐 내부에서 우선순위를 정하여 다시 정렬하여 그 우선순위에 맞게 큐에서 순서대로 빼는 것을 우선순위 큐라고 한다. 따라서 해당 문제는 우선순위 큐가 없었다면 매번 뺄때마다 리스트 원소를 전부 보고 작은 순서대로 빼야되기에 이미 O(N)이 걸리고 그것을 n번 해야되기에 O(N^2)이 걸려 타임아웃이다.그러면 우선순위 큐에서 우선순위를 어떻게 지정할것이냐? 우선순위 큐에서는 우선순위가 높은 것을 차례로 poll 시킨다.Comparator 를 통해서 임의적으로 순서..

누가봐도 큐 문제니까 문제 해설은 하지 않겠다. 미친척하고 깡으로 큐 구현한건 아래와 같다.import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { static int front=1000000; static int rear=1000001; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ne..

import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { static int top=-1; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); List arr = new ArrayList(); boolean flag = false; ..

저번에 참고해서 푼거 복습할겸 다시 풀어봤다.3칸을 매 반복 안에서 모든 요소를 다시 확인하면 결국 O(SP) 복잡도가 되어서 시간초과가 날 것이다. 윈도우를 이동하면 항상 추가된 요소만 반영, 나가는 요소도 반영 즉 O(2)의 상수복잡도만 고려해도 되어서 O(N)에서 끝길 수 있다.import java.util.*;import java.lang.*;import java.io.*;//A C G T// The main method must be in a class named "Main".class Main { static int start=0; static int end=0; static int count=0; public static void main(String[] args) th..

백준 12891번 2개의 포인터로 범위의 양끝을 가르키고 그 양끝을 기준으로 문제를 해결한다. 1) 처음에는 윈도우를 잡고 그 다음부터는 for문으로 옆으로 땡기면서 관찰하면 된다.그렇게 땡기게되면 모든 배열을 윈도우로 순회할때 O(n) , 윈도우의 맨 앞 원소는 삭제되고 뒤에서부터 하나는 추가되기에 삭제되고 추가되는 총 2개의 원소들만 작업 처리해주면 된다.  2) 삭제,추가되는 원소들에 대해 구하고자 하는 기준과 비교해야되는데 현재 윈도우 안에서의 원소들에 대하여 카운트 하고 있는 배열이 있을거고 맞으면 답이 되는 기준배열이 있을것이다. 매 윈도우 이동마다 기준배열과 카운트 배열을 무식하게 하나씩 비교하면 이 또한 O(N)만큼 소요될 것이다. 하지만 슬라이딩을 원소의 추가/삭제 기준으로 본다면 추가되..

브라우저 렌더링과 Virtual DOMhttps://jeong-pro.tistory.com/210 Virtual DOM 동작 원리와 이해 (with 브라우저의 렌더링 과정)Virtual DOM? 1. Virtual DOM이란? → "DOM을 추상화한 가상의 객체" DOM을 추상화한 가상의 객체라고 표현해봤습니다. (개인이 내린 정의) 그러면 우선 저 문장을 이해하기 위해서 DOM이란 뭔지 알아야합니jeong-pro.tistory.com https://velog.io/@bebrain/%EC%9B%B9%ED%8E%98%EC%9D%B4%EC%A7%80-%EB%A1%9C%EB%94%A9-%EA%B3%BC%EC%A0%95 웹페이지 로딩 과정Chrome, Safari, Firefox, Internet Explore..

백준 11660일단 구간합 D 배열을 만든다. 이때 D 배열은 (0,0) 부터 (x2,y2) 까지 모두 더한 값을 D[x2,y2]로 정의한다.근데 우리가 구하고자하는 값은 (x1,y1)~(x2,y2) 의 사각형 부분의 합이니까  D[x2][y2]-D[x2][y1-1]-D[x1-1][y2]+D[x1-1][y1-1] 의 작전으로 짜면 된다.import java.util.*;import java.lang.*;import java.io.*;// N쪽에선 O(n^2) 가능하고 M쪽에선 O(N)// 구간합 배열 만들땐 이중 for문으로 만들고 M에서 출력// The main method must be in a class named "Main".class Main { public static void main(..