개발새발

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 포인터를 이동시키..

레벨2 > 2025년 프로그래머스 코드챌린지 2차 예선 > 서버 증설 횟수사용 언어 : Java 문제 요약이용자가 m명 늘어날 때마다 서버 1대가 추가로 필요이용자가 m명 미만이면 서버가 필요하지 않음이용자가 n×m명 이상 (n+1)×m명 미만이면 n대의 서버가 필요서버는 증설한 후 k시간 동안만 운영모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수를 찾아야 함변수players : 0시에서 23시까지의 시간대별 게임 이용자의 수를 나타내는 1차원 정수 배열m : 서버 한 대로 감당할 수 있는 최대 이용자의 수k : 서버 한 대가 운영 가능한 시간을 나타내는 정수제한 사항players 길이 : 240 players[i] : i 시 ~ (i + 1) 시 사이의 이용자 수1 1 문제 접근 방향각 시간대별..