개발새발

1. 문제 파악하기모든 물건을 훔쳐야 한다.각 물건은 훔칠 때마다 a/b 두 도둑 중 하나가 흔적을 남긴다.a의 흔적 합이 n 이상이면 a가, b의 흔적이 m이상이면 b가 잡힌다.목표는 "둘 다 잡히지 않으면서" a의 흔적 합을 최소화하는 것각 물건마다 선택(a가 훔칠까, b가 훔칠까)을 해야하고,전체 선택 결과에 대해 두 변수(=a의 흔적, b의 흔적)가 제약(그 중 a의 흔적을 최소화 해야한다=> 전형적인 DP(동적 계획법) 문제 형태2. DP 상태(메모이제이션) 설계dp[k] = 지금까지 b 의 흔적 합이 정확히 k 일 때, a의 흔적 합의 최소값배열 길이는 m (b가 잡히지 않으려면 k 초기값INF = 10**9dp = [INF]*mdp[0] = 0 # b가 0 흔적일 때 a도 0 이제 물건을 하..

35. Search Insert Position[문제]정렬된 정수 배열 nums와 목표 값 target타겟이 배열에 존재하면 인덱스를 반환존재하지 않으면 정렬된 순서를 유지하면서 삽입될 위치를 반환해야 한다.[문제 조건]배열 nums는 오름차순으로 정렬되어 있다.배열의 길이는 0 배열의 원소는 -10^4 타겟 값은 -10^4 시간 복잡도는 O(log n)[코드 1]이진탐색 버전 (시간복잡도 O(log n) )def search_insert(nums, target): left, right = 0, len(nums) - 1 while left [코드 1 설명]이진 탐색 사용:left와 right로 배열의 양끝을 설정하고, 중간값 mid를 계산해가며 탐색.조건 비교:nums[mid] == targe..

28. Find the Index of the First Occurrence in a String [문제 설명]문자열 haystack에서 부분 문자열 needle이 처음 등장하는 인덱스를 반환하라.needle이 haystack에 없다면 -1을 반환한다.[문제 조건]needle이 빈 문자열이면 0을 반환한다.needle이 haystack에 없는 경우 -1 반환.[코드]public int strStr(String haystack, String needle) { if (needle.isEmpty()) return 0; int hLength = haystack.length(); int nLength = needle.length(); // haystack의 길이가 needle보다 짧으면 -1..

27. Remove Element [문제 설명]정수 배열 nums, 특정 값 val 이 주어지면, 정수 배열 내에 있는 요소들 중 val과 같은 요소를 제자리에서 삭제한다.삭제 후 남은 요소의 개수를 반환한다.[문제 조건]배열 nums에서 모든 val 값을 제자리에서(in-place) 삭제해야 한다.삭제 후에는 배열에 val과 같지 않은 요소들만 남아야 한다.정렬 순서가 바뀌어도 상관없다.배열의 첫 k개의 요소가 val과 같지 않은 값들로 채워져 있어야 한다.[코드]class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rt..

26. Remove Duplicates from Sorted Array [문제]정렬된 정수 배열 nums에서 중복을 제거하여 배열의 고유한 원소들로만 이루어진 부분을 반환해야 한다.중복을 제거한 후에도 배열의 순서는 유지되어야 하며, 중복을 제거한 후의 길이를 반환해야 한다. 배열의 첫 k개의 요소가 중복이 제거된 부분을 나타낸다. [문제 조건]정렬된 배열이 주어지기 때문에, 중복된 숫자들이 연속해서 등장한다.추가 공간을 사용하지 않고, 제자리에서(in-place) 중복을 제거해야 한다.새로운 배열이나 추가 자료구조(Set 등)를 사용하면 안 된다.반환값으로 중복이 제거된 배열의 길이(k)를 반환한다.첫 k개의 요소가 중복을 제거한 상태여야 한다.Set을 사용하면 순서가 보장되지 않아 문제 요구사항을 만..

.

투 포인터정렬된 배열이나 리스트에서 두 개의 포인터(인덱스)를 이용해 효율적으로 문제를 해결하는 알고리즘 기법💡 기본 아이디어두 개의 포인터두 개의 인덱스(p1, p2)를 사용해 배열의 요소들을 동시에 탐색한다정렬 활용배열이 오름차순(또는 내림차순)으로 정렬되어 있기 때문에,두 포인터가 가리키는 값을 비교하여어느 쪽 포인터를 이동시킬지 결정할 수 있다ℹ️  예시두 정렬된 배열에서 공통 요소 찾기 1. 초기화:배열 A, 배열 B가 있다고 가정포인터 p1은 A의 시작(인덱스 0)에서, p2는 B의 시작(인덱스 0)에서 시작2. 동작 과정:A[p1] == B[p2]두 배열 모두 해당 요소를 포함하므로 공통 요소로 기록두 포인터 모드 한 칸씩 이동A[p1] A[p1]이 더 작으므로 A에서 다음 값과 비교하기 ..

https://www.acmicpc.net/problem/1193 🧩  문제 설명무한히 큰 배열에 다음과 같은 분수들이 있을 때, x(입력값)번째 분수를 구하기1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> ... 과 같은 지그재그 순서로 1번, 2번, 3번, ... 분수라고 지칭함💡 핵심 아이디어대각선 방향으로 분수가 나열되는 규칙을 파악하는 것이 핵심각 대각선에는 분수의 개수가 대각선 번호와 같고,그 대각선에 속하는 분수들의 분자와 분모의 합은 항상 (대각선 번호 + 1)이 된다예를 들어,1번째 대각선: 1/12번째 대각선: 1/2, 2/13번째 대각선: 3/1, 2/2, 1/3여기서 규칙은 대각선의 번호에 따라 탐색 순서가 달라진다는 것✅  알고리즘 흐름1. 대각선 번호 구하기입력..

https://leetcode.com/problems/median-of-two-sorted-arrays/[문제 설명]두개의 정렬된 배열(nums1, nums2)이 주어졌을 때, 두 배열의 중앙값 찾기단, 시간 복잡도는 O(log(m+n)) * m : nums1의 길이, n : nums2의 길이 [주의사항]중앙값을 찾아야하네? -> 두 배열을 합쳐서 정렬한 뒤 중앙값을 찾자 (XXXXXXX)배열을 합치고 정렬하는 방식의 시간 복잡도는 O((m+n) log(m+n))이기 때문에 문제의 조건과 어긋남 [접근 방법]1. 병합하지 않는다 2. 짧은 배열에 대해 이진 탐색(Binary Search)을 수행한다짧은 배열에 대해 이진 탐색을 하는 이유는 탐색 범위를 줄여서시간 복잡도를 O(log(min(m,n))로 제..

슬라이딩 윈도우(Sliding Window)알고리즘 문제를 풀다 보면, 배열이나 문자열과 같이 연속된 구간에 대한 처리가 필요할 때가 있을텐데,이때 슬라이딩 윈도우 기법을 사용하면 도움이 된다.1. 슬라이딩 윈도우란?슬라이딩 윈도우 기법은 두 개의 포인터(또는 인덱스)를 사용하여배열이나 문자열의 특정 구간(윈도우)를 유지하면서 문제를 해결하는 방법이다.이 기법은 주로 다음과 같은 상황에서 유용하게 사용된다.연속된 구간의 합 구하기특정 조건을 만족하는 최대 또는 최소 길이 구하기중복이 없는 가장 긴 구간 찾기 등2. 기본 아이디어슬라이딩 윈도우는 아래의 단계를 반복하면서 문제를 해결한다.윈도우 정의시작 인덱스(left)와 끝 인덱스(right)를 두어 구간을 정의한다.윈도우 확장right 포인터를 이동시키..