본문 바로가기

Algorithm(코딩테스트)47

슬라이딩 윈도우 알고리즘 그림 한 장 Summary 슬라이딩 윈도우 알고리즘을 사용하는 경우1차원 배열에서 부분적으로 특정 합이나 값을 구해야 하는 경우 왜 슬라이딩 윈도우 알고리즘을 사용하는가?위 사용 예시에서 특정 K개의 합을 구하는데 O(N), 그것을 배열의 개수 N 개만큼 구해야 하므로 O(N)이 든다.이 것을 동시에 시행하므로 O(N^2)이 걸린다. 하지만 배열이 200,000과 같이 큰 경우 일일이 계산해주면 시간 초과가 난다. (20만 * 20만 = 400억) 그래서 슬라이딩 윈도우를 통해 이 문제를 O(N)으로 해결할 수 있다. 백준 2559번 문제로 예를 들면,psum 배열에 합계를 누적하여 저장하고그 다음 두 번째 for문 안에서는 연속된 k일 간의 온도합이 가장 큰 값을 계속 갱신시킨다. 위와 같이 2~3번째.. 2025. 5. 20.
[프로그래머스] 기능개발 (Java) 문제 정보  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 교훈점1. [5, 10, 1, 1, 20, 1] 에서 모든 배열의 원소값을 [0] 인덱스의 값 만큼 빼서 [0, 5, -4, -4, 15, -4] 로 만들고 싶을 때 아래와 같이 코드를 작성하면 안된다.for(int i=0; i왜냐하면 deploy[0]의 값이 0으로 바뀌어서 i가 1부터는 deploy[1] -= 0; 의 꼴이 되어버린다. 이런 경우 아래 코드와 같이 deploy[0] 을 다른 변수에 저장해두고 사용해야 한다.int minus = deploy[0];for(int i=0; i  1. 배열로 풀이 O(n^2)1. 배포까지의 걸리는 .. 2025. 3. 22.
[Stack 응용] Monotonic Stack 두 줄 요약각 element를 오름 차순, 내림 차순으로 유지하는 알고리즘 기법 특정 기점에서 최초로 커지거나/작아지는 시점을 구하고 싶을 때 사용 배열에서 다음보다(순서 중요) 큰 element나 작은 element를 찾는 문제를 O(n) 이라는 시간에 효율적으로 해결할 수 있다. 즉,1) 배열의 순서가 중요하고 (그 순서를 기점으로 계산해야 하기 때문에)2) 어떤 기점에서 크거나 작은 요소를 찾아야 하는 문제3) O(n^2)으로 해결할 수 없고, O(n)으로 해결해야 하는 경우 1) && 2) && 3) 의 해당하는 경우 Monotonic Stack을 사용하면 된다.온도 문제로 생각해보는 Monotonic Stack의 필요성각 일마다 온도를 순서대로 나타내어 temperatures 배열에 아래와 같이.. 2025. 3. 22.
[JAVA] 🌟프로그래머스 - 달리기 경주 교훈점해시 테이블의 필요성을 알 수 있는 문제 (탐색하는데 n의 개수가 클 때) 배열로 순회하여 풀이 추월한 선수의 index 값을 알아내서 그 앞에 있는 선수와 swap 하면 간단하게 해결할 수 있다.즉, callings 배열을 순회하면서 동시에 players 배열들을 순회해야 한다.그러나, 제한 사항이 callings 배열의 길이가 최악의 경우 100만, players의 배열의 길이가 최악의 경우 5만이다.따라서 최악의 경우 500억의 연산이 일어나므로 시간 초과가 난다.  -> 순회를 할 때 시간을 줄여야 한다.Hash Table 사용배열은 어떤 원소를 찾기 위해 순회할 경우 시간 복잡도가 O(n)이다.Hash Table은 어떤 원소를 찾으려면 O(1)으로 해결이 가능하다.(이름, 순위) 를 담는 .. 2025. 3. 21.

티스토리툴바