본문 바로가기

Algorithm(코딩테스트)46

[프로그래머스] 기능개발 (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 배열에 아래와 같이 저장했다고 하자.temperatures = [73,74,75,71,.. 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.
[SQL] 재귀 쿼리 (WITH RECURSIVE) 이해하기 SQL 계의 반복문 WITH RECURSIVE란?재귀적(반복적)으로 어떤 쿼리를 실행하기 위해 만든 임시 테이블이다.with RECURSIVE hour_tbl as( SELECT 0 as HOUR -- 초기 구문 UNION ALL -- 반복해서 실행할 구문 SELECT HOUR+1 FROM hour_tbl WHERE HOUR  문법 형태는 위와 같다.SELECT 0 as HOUR 구문을 초기 구문으로 하고 UNION ALL 이후 구문을 반복해서 실행할 구문으로 두면 된다. 실행하면 아래와 같다. 이 구문의 원리를 쉽게 이해해보자.SELECT 0 as HOUR 는 마치 int HOUR = 0; 과 같은 초기 선언과 같다.UNION ALL 구문은 두 SQL문의 결과를 합치는 것이다.S.. 2025. 3. 20.

티스토리툴바