onaeonae1

이분 탐색 -> 값을 탐색하는 문제파라메트릭 서치 -> 어떤 파라미터로 가능하냐? 라는 결정 문제 어떤 값을 만족하는 것을 찾는 탐색 문제가 아님. 먼저 답을 정해놓고, 그게 실제로 가능하냐를 찾는 문제임 어떤 연속된 입력들에 대해 그룹으로 쪼개고, 거기서 가능한 어떤 값을 찾는 그런 문제를 만났다고 쳐보자 e. g) 전체 수 N, 분할 가능 수 M , 배열 A[1:N] 에서 그룹으로 분할했을 때, 각 그룹 내의 원소 합의 최소값 구하기 여기서 쪼개는 방법부터 생각하면 머리가 쪼개진다 임의의 어떤 답의 후보를 정해두고, 이걸 만족하는지 값을 이분 탐색으로 변경해가며 확인하면 됨근데 그룹을 쪼개는 방법을 모르는데 어케 확인함? 일단 "연속된 것"을 나눈다는 것에 집중해야 함어차피 연속되어 있고, 우리는 조..

DP[i][j] = min(DP[i][j], DP[i][k], DP[k+1][j]+@) 라는 식을 감싸는 for문을 생각해보자 일단 이렇게 보면 굉장히 헷갈린다. 변수명을 바꿔보자 for(int range = 1; range     for(int startPos=1; startPos        int endPos = startPos+range;        for(int k= startPos; k             DP[startPos][endPos] = min(DP[startPos][endPos], DP[startPos][k] + DP[k+1][endPos] + @        }   }} DP[start][end] = min(DP[start][end], DP[startPos][k] + DP[k+..

코테 준비를 하다 보면 정답이 너무 커지는 것을 막기 위해 특정 값으로 나눠서 리턴하라고 하는 경우가 있다  정답을 모듈러로 리턴하라고 하니깐 당연히 맨 마지막에 처리하면 된다고 생각했는데 그러면 시간 초과가 난다우선 for 문 수행 중에 그냥 바로 모듈러를 수행하면 시간 초과를 피할 수 있다. 그 이유를 요약하자면 다음과 같다1. 중간에 모듈러를 매번 수행하든 마지막에 수행하든 결과 자체는 동일하다.2. 중간에 모듈러를 사용하는 것이 실행 시간에 이점이 존재한다. 1. 캐시 메모리 효율성CPU 캐시 메모리는 CPU가 자주 사용하는 데이터를 저장하는 작은 공간이다. 캐시 메모리는 메인 메모리(RAM)보다 훨씬 빠르게 접근 가능하다.작은 값의 데이터는 더 작은 공간을 차지하므로, 캐시에 더 많이 저장될 수..

https://leetcode.com/problems/house-robber/solutions/156523/From-good-to-great.-How-to-approach-most-of-DP-problems./ 참조할 문제https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr

https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제를 푸는 방법은 간단하다1. 멘토 배정의 조합을 구한다 -> itertools.combinations 사용2. 해당 조합으로 heapq 를 사용하여 순회한다 -> heapq push, pop3. 조합 돌리면서 최소의 시간을 구한다 import heapqfrom itertools import combinationsdef calculate_wait_time(mentor_distribution, re..

문자열에 대한 정렬 조건이 주어질 때 그에 대한 정렬을 야무지게 해주면 되는 문제이다functools 의 cmp_to_key를 적극적으로 사용하면 된다 또한 문자열의 조건이 꽤 빡빡하므로 그에 대해 확인하면 된다-> HEAD, NUMBER, TAIL이때 HEAD에 공백이 포함될 수 있기 때문에 주의 필요 (테케 6,7,8,9 통과 안되는 이유) from functools import cmp_to_keydef parse(file:str): flag = False num_sti = -1 num_edi = -1 for idx, item in enumerate(file): if item.isdigit(): if not flag: ..