우서오십쇼

https://school.programmers.co.kr/learn/courses/30/lessons/389480 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr dfs 완전탐색으로 풀면 시간초과가 난다.dp로 풀어야 하는 문제였다.  2차원 dp배열을 만드는데,,,[i번째보물까지훔쳤을 때][b의 누적흔적] = a의 최소누적흔적;으로 두고 for문을 반복해준다.이 때 min을 구하는것이므로 배열요소는 INT_MAX로 초기화해준다.  i == 0 : 초기값 넣기info[0]을 훔쳤을 때 dp값은 미리 넣어줘야 한다. dp[0][0] = info[0][0]; // a만훔침 (b의 누적흔적이 0)dp[0][..

코테준비/하루한개도전~ 2025. 2. 24. 16:33

https://www.acmicpc.net/problem/10830 ★ 주의할점 : 행렬곱이 나오면 시간초과를 주의하자!! 방법1 : 냅다 행렬곱 구현해서 b번 반복하기 -> 시간초과 행렬곱 자체가 n^3 시간복잡도가 나오는데 이걸 b번 반복하면,,,,,,,,,,,,,,,,,,,,,, 너무 계산량이 많다!  방법2 : A^4 = A^2 * A^2 이용하기 행렬의 거듭제곱은 이렇게 쪼갤수가 있다.그러니까,,, A^b을 A^2, A^4, A^8 .... 여러개로 쪼개서 곱해준다고 생각해보면,,,,약간 이진트리처럼 logn 이렇게 줄어드는 효과가 생기지 않을까 싶다!!ㅎㅎ b를 2로 나눠가면서 곱하기 곱하기를 해도 비슷할것같은데어케 구현해야 할지 감이 안잡혀서 걍 2거듭제곱 여러개로 해결해봤당ㅎㅎ #inclu..

코테준비/하루한개도전~ 2025. 2. 21. 10:33

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr softeer의 출퇴근길과 비슷한 느낌을 받았다!!https://softeer.ai/practice/6248 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai A, B의 퇴근루틴을 생각해보면 1. 시작점 -> 나눠타는 지점2. 나눠타는 지점 -> A의 집3. 나눠타는 지점 -> B의 집각각의 cost를 다 더해주면된다. 이걸 그대로 하나하나 구해보면, 전체탐색밖에 답이 안보인다!!!! softeer때처럼 반대로 생각해보자 1..

코테준비/하루한개도전~ 2025. 2. 14. 17:13

https://www.acmicpc.net/problem/3197  풀이방법 : 얼음을 녹일 때, 백조가 이동할 때 매번 전체탐색을 돌리지 말자!! [메모리 초과]풀이방향이 잘못되어 map을 여러개 저장하거나, queue에 들어가는 node에 불필요한 정보가 같이 포함되었다. 특히 visited, map을 선언할 때 int로 여러개를 만들었는데,, 이걸 bool로 바꾸어주니 메모리초과는 해결되었다.[시간초과] 문제 설명 그대로,,while문으로 하루씩 매번 반복을 돌렸고매 반복마다 bfs를 이용해 백조가 만나는지 확인 + map 전체탐색으로 얼음을 녹여 map 업데이트 를 진행하였다. 이런상황에서 문제는,,,1. 좌우양옆이 물인 공간, 좌우양옆이 얼음인 공간의 탐색은 불필요한데 매 반복마다 진행된다는점2..

코테준비/하루한개도전~ 2025. 2. 14. 16:15

query optimization의 전체 동작이 어떻게 이루어지는지 살펴본다plan spacecost extimationsearch algorithmPlan SpaceQuery를 블락단위로 쪼갠다 (중첩쿼리면, sub쿼리를 빼서 2개의 블럭으로 만드는등등)그리고 각 연산자들의 제한사항을 확인할 필요가 있다.-> 데이터들은 물리적으로 "아무것도 아님" "sort order" "hash grouping" 상태를 가진다.결과로 나오는 테이블이 특정 형태를 띄는것Index scan : 결과가 sortSort : 결과가 sortHash : 결과가 hash groupinginput으로 특정 형태의 테이블이 필요한것Sort Merge Join : input으로 sort된 데이터가 들어오는걸 가정함input으로 들어온..

학교/데이터베이스시스템응용 2024. 12. 19. 20:42

예제를 가지고, 각 query plan의 cost를 생각해보자!Reserves (sid: integer, bid: integer, day: date, rname: text)each tuple : 40 bytes한 페이지에 100 tuples1000 pagesboat는 100가지 종류Sailors (sid: integer, sname: text, rating: integer, age: real)each tuple : 50 bytes한 페이지에 80 tuples500 pagesrating은 10종류join을 위해 5page 사용가능SELECT S.sname FROM Reserves R, Sailors SWHERE R.sid=S.sid AND R.bid=100 AND S.rating>5;P..

학교/데이터베이스시스템응용 2024. 12. 19. 19:51

쿼리 최적화에 대해 배운다. System R (Selinger)Cascades두가지 옵티마이저를 주로 사용한다고 한다. 강의에서 배울건 System R 옵티마이저라고 한다.  SQL문이 들어오면Query Parser가 abstract syntax tree로 만들어줌쿼리가 올바른지, 사용자가 테이블 접근권한지 있는지 확인Query rewriter가 쿼리를 표준형식으로 변환 (AST를 변경하는것) -> 옵티마이저에게 전달함-> 뷰를 가져와서, 조인으로 변환하거나, 서브쿼리를 더 적은 쿼리블록으로 변환함view를 가져와 쿼리에 통합해준다받은 변환된 AST를 가지고 효율적인 계획 (plan)으로 변환함비용추정을 할 때 데이터베이스 카탈로그를 통해 다양한 통계값들을 받아오는것계획생성, 비용추정을 한다 (비용이 저..

학교/데이터베이스시스템응용 2024. 12. 19. 18:40

equi join, natural join에만 적용할 수 있다. 총 2단계로 진행되는데sort : key를 기준으로 정렬한다. 즉 같은 joinkey를 가진애들끼리 모아두는것만약 입력이 이미 정렬되어 있다면, 옵티마이저가 알아서 이 단계를 pass해준다join :정렬된 두 테이블을 읽어와서 조건에 맞는 튜플을 반환해줌 수도코드이미 정렬은 했다고 가정한다. do { if (!mark) { while (r s) { advance s } // mark start of “block” of S mark = s } if (r == s) { result = advance s return result } else { reset s to mark ..

학교/데이터베이스시스템응용 2024. 12. 19. 17:10