영최의 개발켈로그

보호되어 있는 글입니다.

보호되어 있는 글입니다.

📌 링크: https://www.acmicpc.net/problem/2470 📌 총평: 이문제 이진탐색으로 분류되어있는데 낚시다. 투포인터 문제다. 📌 헷갈렸던 부분:✅ 이 문제는 양쪽 끝을 계속해서 비교하는 문제여서, 핵심은 양끝의 합 >0 이면 오른쪽-=1, 양끝의 합 나는 양끝의 합의 부호를 기준으로 보지 않고 바로 직접값이랑 합의 값을 비교해서 틀렸다. abs(arr[s] + arr[e-1]) 왜 절댓값 비교를 하면 안되냐하면, 값이 수렴하지 않고 진동할 수 있기 때문이다. 현재 수렴해야하는 값은 양끝의 합=0이 되는 것,즉, 0으로 값이 수렴해야하므로 0이 기준이 되어야한다. 그래서 0보다 합이 크면 합을 줄이는 쪽인 왼쪽-=1 ~ 이런식으로 왼쪽,오른쪽 값을 조절하는 거다. ✅ 절댓값을..

문제 유형에 따라 다르게 풀어야한다.1) 길이를 구해라  →  (1) dp풀이 O(N^2), (2) 이진탐색 O(NlogN)(시간 복잡도만 봤을 때는 (2) 이진탐색 풀이만 알면 될것 같지만, 최장 증가 수열 자체를 구해야할때는 (1)을 응용해야하므로,(1),(2)번 모두를 알고 있어야한다. 2) 최장 증가 수열을 구해라 → (1)dp풀이+while문  1. 최장 증가 수열의 [길이]를 구해라1️⃣ dp풀이 O(N^2) - 보통 N=1000정도 N = 전체 수열 길이arr = 주어진 배열dp[i] = i번째까지 최장 증가 수열의 길이 N =6, arr = [10, 20, 10, 30, 20, 50] 라 할때, i에 따라 아래 결과로 나오게됨i:0, dp:[1, 1, 1, 1, 1, 1]i:1, dp:[1..

📌 링크: https://school.programmers.co.kr/learn/courses/30/lessons/172927 📌 틀린이유:✅ 최적의 순서를 알 수 없다고 생각해서 완전 탐색인 permutation을 썼는데 시간초과가 났다.=> 광물들을 5개씩 묶고 피로도가 높은 순서로 정렬한 다음 다이아몬드,철,돌 순서로 곡괭이를 소모하면 되는 문제였다.✅ 광물 배열을 곡괭이로 캘수 있는 정도까지만 잘라줘야한다. => 안해줘서 피로도 순서가 꼬였고 그래서 최적이 안되게 되버렸다. 📌 알고리즘1️⃣ 광물을 전체 곡괭이 개수*5만큼으로 잘라준다.(캘 수 있는 만큼)def solution(picks, minerals): s_p = sum(picks) num = s_p * 5 if len..

📌 링크: https://school.programmers.co.kr/learn/courses/30/lessons/176962 📌 총평: 구현이 좀 까다로운 조건들이 있어서 어려웠다. 우선 gap을 이용해서 추가적으로 stack안에 있는 과제들을 진행할 수 있는지를 구현하는게 주 아이디어였다. 그리고 이후에 i,i+1을 이용해 gap을 구했기때문에 맨마지막 plans[-1]을 답에 넣어줘야했다. 마지막에 stack에 남아있는 것들을 거꾸로 꺼내서 답에 넣어야한다는 것도 바로 떠올리기 어려웠다. 📌 문제 이해:과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.과제는 시작하기로 한 시각이 되면 시작합니다. (우선적으로 과제를 시간 순 정렬 해야함)새로운 과제를 시작할 시각이 되었을..

📌 링크: https://school.programmers.co.kr/learn/courses/30/lessons/178870 📌 틀렸던 이유:✅ 초기화 부분을 start,end=0,0으로해야하는데 start(합의 조건이 무조건 두개이상의 원소는 아님)✅ sum_value를 먼저 정해주고 while을 돌려야 정확하게 조건에서 걸리는데 while문 이후에 정해줘서 로직이 꼬였음 📌 알고리즘:1️⃣  start_idx, end_idx, sum_value=0,0,0으로 초기화해준다.마지막에 가장 길이가 짧은 수열의 처음,시작 인덱스를 반환해야하므로 힙을 활용한다.from heapq import heappop,heappushdef solution(sequence, k): start_idx,end_id..

📌 투포인터 알고리즘이란?리스트에 순차적으로 접근해야할때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 📌 어떤 경우 쓰일까?ex) 특정한 합을 가지는 부분 연속 수열 찾기 (대표적) 📌 알고리즘1️⃣ 시작점(start)과 끝점(end)이 첫번째 원소 인덱스(0)를 가르키도록함2️⃣  while 현재 부분합이 M보다 작으면 end를 증가시킴 (부분합이 M보다 같거나 크기 전까지)3️⃣ 부분합이 M이랑 같으면 카운트함4️⃣ 부분합에서 시작점(start)의 원소를 제거  5️⃣ 시작점(start) 인덱스를 1증가 2️⃣~5️⃣  반복 📌 기본 코드n = 5 #데이터 개수 Nm = 5 #찾고자 하는 부분합 Mdata = [1,2,3,2,5]count = 0end = 0interval_sum = 0fo..