가로 길이 A, 세로 길이 B인 직사각형 가지수 A(0,0) B(2,0) C(0,3) D(2,3) E(4,0) F(4,3) N : 50만개 점 A : 1000 B : 1000 점 좌표 - 10^9 ~ 10^9 1. 완전탐색 NC4 해서 주어진 점 N개 중에 4개를 고를 수 있는 경우 전체 확인 6C4 = 6 * 5 / 2 * 1 50만C4 = 너무 커짐 불가능 2. 어떻게 최적화를 할 것인가? 만약에 특정 점(K)이 정해지면 K점에서 만들 수 있는 사각형은 정해져있음 (KX, KY) (KX + A, KY) (KX, KY + B) (KX + A, KY + B) (KX, KY) (KX - A, KY ) (KX , KY + B) (KX - A, KY + B) (KX, KY) (KX - A, KY) (KX - ..
전체 글
숫자의 범위는 1~ 2147483647 (2^31 - 1)입력이 최대 2만개1 2147483647 1입력이 2만개 들어오면 21억 번 * 2만번 -> 시간초과숫자를 저장하지 않고 답을 구해야된다.숫자의 범위로 계산하면 좋을듯하다. 단 하나의 숫자만 홀수개이다. 아예 홀수개인 숫자가 없을 수도 있다. 단 하나의 숫자만 홀수이기때문에, 홀수가 속한 범위의 개수의 합은 홀수가 된다. 홀수가 속하지 않은 곳의 범위의 개수의 합은 짝수가 된다. 특정 수가 홀수이다. 특정 수가 속한 범위의 개수는 홀수개다. 특정 수가 속하지 않은 범위의 개수는 짝수개이다. 특정수를 정한다. 특정수가 속한 범위의 개수를 구한다.? 지금 저게 각각의 정수 더미가 아니라 하나의 정수더미다. 하나의 정수더미라고 생각해라 1 2 2 3..
어떻게 이분탐색으로 해야할 지 감이 안왔던 문제근데 되돌아보니 수업 때 11122233345 이런식으로 예시를 보여주셨던게 생각났다... 아..! 먼저 완전탐색으로 다 보면 n*n = 10^5라서 볼 수 없다 최적화를 해야되는데 ..1에서 n*n까지 이분탐색을 한다? -> 이분탐색으로 뭘 어떻게 할건데? 만 생각났었다. 이분탐색으로 값의 범위를 줄여가면서 이분탐색으로 찾은 중간값(mid) 이하인 숫자가 몇 개 있는지 찾으면 된다. 이 때 중간값(숫자)보다 m이 더 크면 중간값은 답이 될 수 없고 무조건 중간값 + 1이어야 한다.중간값(숫자)보다 m이 작으면 답은 중간값이 될 수도 있고 그 밑에 값이 될 수도 있고 .. 그러하다. 이때 mid - 1을 해준다. 아 어렵다.
구하고자 하는 것은 상근이가 카드를 가지고 있는지의 유무이다. 이분탐색 카테고리에 있어서 이분탐색으로 풀려했으나 아이디어가 떠오르지 않았다. 오히려 완탐만 떠올랐다... 완탐방법은 다음과 같다.-천만 ~ 천만으로 이천만개 숫자만 저장하면 된다.N이 50만밖에 안되니까 50만번만 반복해서 상근이가 가지고 있는 카드를 저장한다.M이 50만이니까 50만번 반복해서 특정 숫자가 상근이가 가지고 있는 숫자인지 배열에서 확인하면 된다. 이분탐색으로는 어떻게 풀지?두 배열을 정렬해서 포인터를 두고 비교하나...?그러면 나중에 출력은 정렬 이전의 순서대로 출력해야되는데 이 부분은 어떻게 하는가..? 상근이가 가지고 있는 카드를 정렬한다.상근이가 찾는 숫자가 갖고있는지 이분탐색을 통해서 그냥 탐색하면 된다. logN이..
완전탐색을 생각해봤다. 각 세사람이 가지고 있는 수를 가지고 만들 수 있는 경우가 1000 * 1000 * 1000으로 10억이 되어서 시간 초과가 난다는 것을 발견했다. 최적화를 어떻게 해야할까?세 수가 똑같을 경우 0으로 가장 작다.두 수가 같고 1차이 나는 수가 있으면 1로 작다.세 수가 모두 다르고 가장 큰 수와 가장 작은 수가 2 차이나면 2로 작다.세 수가 모두 다르고 가장 큰 수와 가장 작은 수 가 3 차이나면 3으로 작다.... 세 사람의 각 수를 비교해야한다. 근데 이걸 반복문으로 비교할 생각밖에 안났다. 아무리봐도 그건 아닌데 어떻게 해야하지?무엇인가 비교할 때 for문에 갇혀있지 말 것 ,, for문 말고 while문을 활용해서 반복문을 쓰되 종료조건을 설정하면 된다. 세개의 배열..
-- 7월 아이스크림 총 주문량과 상반기의 아이스크림 총 주문량을 더한 값-- 큰 순서대로 상위 3개의 맛-- SELECT FLAVOR, SUM(TOTAL_ORDER)-- FROM JULY-- GROUP BY FLAVOR;-- SELECT FLAVOR, SUM(TOTAL_ORDER)-- FROM FIRST_HALF-- GROUP BY FLAVOR; SELECT FLAVOR FROM ( SELECT FLAVOR, SUM(TOT_PRICE) , RANK() OVER (ORDER BY SUM(TOT_PRICE) DESC) AS RESULT FROM ( SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOT_PRICE ..
생산일자가 5월인 식품이니까 WHERE 절에서 PRODUCE_DATE 조건 걸어주고, 식품 주문 테이블에는 식품이름이 없기때문에 조인 시켜줘야한다.조인할때는 조인 조건을 꼭 걸어주자!SELECT 문에 쓰는 비집계컬럼은 GROUP BY에 적어주기물건ID와 물건 이름이 같은데 가격이 다른 경우가 있을 수 있다.-- 생산일자가 2022년 5월인 식품-- 식품ID, 식품이름, 총매출 조회-- 총매출 내림차순, 식품ID 오름차순-- 조인할 때 왜 조인 조건을 안쓰니SELECT A.PRODUCT_ID, B.PRODUCT_NAME, SUM(A.AMOUNT) * B.PRICE AS TOTAL_SALES FROM FOOD_ORDER A, FOOD_PRODUCT B WHERE A.PRODUCT_ID = B.PRODUC..
# 구하고자 하는 것 -- 세단, SUV인 자동차들 중에서 -- 2022/11/1 ~ 2022/11/30 까지 대여가 가능하고 -- 30일간의 대여 금액이 50만원 이상, 200만원 미만인 자동차 -- 대여 금액을 기준으로 내림차순 정렬, 자동차 종류 오름차순, 자동차 ID 내림차순 # 처음 생각한 것대여기록테이블에서 세단, SUV자동차이면서 11월달에 예약이 안되어있는 차량들을 구했다.하지만 이렇게되면 CAR_ID가 중복되는 차량이 많이 나오기 때문에 안됨! 아래처럼 해서 틀렸다.세단, SUV조건도 없고, 아래처럼하면 동일한 데이터가 여러행이 나온다.SELECT HISTORY.CAR_ID CAR_ID, CAR.CAR_TYPE CAR_TYPE, CAR.DAILY_FEE * 30 * (100 - PLAN...