728x90 PS91 [누적합] 출석체크 문제링크 https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 1. 핵심 학생의 분류 출석 코드 받고 졸지 않은 학생 → 자신의 배수 번호에 전파 가능 출석 코드를 받고 졸은 학생 → 전파 불가 / 코드 받을 수 없음 출석 코드를 받지 않고 졸지 않은 학생 학생 → 전파 불가 / 코드는 받을 수 있음 출석 코드를 받지 않고 졸은은 학생 → 전파 불가 / 코드 받을 수 없음 코드 해설 코드를 받은 학생들 중.. 2024. 4. 1. [그리디] 전구와 스위치(Python) 문제링크 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1. 핵심 좌우 상태 반전 그리디 유형 같은 곳을 2번 선택하면 선택하지 않는 것과 동일하므로 같은 곳을 2번 선택하지는 않는다. 순차적으로 진행하면서 눌러야하는 위치 판단하는게 유리 첫번째 위치가 선택되는지 안되는지 경우를 나누어서 생각 순차적으로 파악한 후에 마지막 원소가 동일한지 동일하지 않은지 판단한다. 마지막 원소가 같다면 잘 변경된 것이고 마지막 원.. 2024. 2. 18. [DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 고대 보물 지도의 비밀 문제링크 https://www.codetree.ai/missions/2/problems/secret-of-ancient-treasure-map?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 동일한 상황에 대해서 생각 특정한 위치(행)까지의 합(값)과 마이너스의 개수(열)가 동일한 경우 같은 상황이다. 이 문제의 포인트는 '연속'이다. 그러므로 dp의 i번째를 볼 때는 반드시 dp의 i - 1번째를 봐야하고 또 주의해야할 점은 연속을 끊어내고 내 스스로 연속의 시작점이 될 .. 2024. 2. 17. [SQL] 오랜 기간 보호한 동물(2) 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/59411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 핵심 LIMIT ROW_NUMBER() OVER (PARTITION BY ~ ORDER BY ~) TIMESTAMPDIFF(단위, START, END) 대여기간은 +1 잊지말기! 2. 코드(MySQL) # 입양을 간 동물 중 # 보호기간이 가장 길었던 동물 두마리의 아이디, 이름 # 보호기간 긴 순으로 내림차순 # 보호기간 = 입양일 - 보호시작일 with temp as ( sele.. 2024. 2. 17. [DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 올바른 등식 만들기 문제링크 https://www.codetree.ai/missions/2/problems/right-equality?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 DP의 정의 DP[i][j] 는 i번째 숫자를 반드시 선택했을 때 i번 숫자로 ± 하여 j를 만드는 경우의 수라고 하겠다. 따라서, 점화식은 DP[i][j] = DP[i - 1][j - nums[i]] + DP[i -1][j + nums[j]] M이 -20 부터 20이다. 그런데 '음수'는 인덱스로 접근이 어렵다... 2024. 2. 16. [그리디] Greedy Algorithm / 자연수 M/2개의 쌍 문제링크 https://www.codetree.ai/missions/8/problems/m2-pairs-of-natural-numbers?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 합들 중 최댓값이 최소가 되도록 하려면 가장 작은 수와 가장 큰 수를 순서대로 매칭하면 된다. 방법1(메모리초과 + 시간초과) 각 값들을 max_heap, min_heap에 넣어서 m // 2만큼 max_q + min_q의 조합하고 조합한 것 중 최대값을 고른다. 문제는 m이 10억이므로 최.. 2024. 2. 16. 이전 1 2 3 4 5 6 ··· 16 다음 728x90 반응형