개발새발

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 이제 물건을 하..

알고리즘 문제 사이트마다 입력과 출력 방식이 조금씩 다른데,프로그래머스는 로직만 작성하고 백준에서는 문제에 나와있는대로 입력과 출력까지 작성해야 한다.다양한 문제 풀이 환경에 대비해서 입력과 출력 방법을 알아두면 좋을 것 같다1. 입력 받기입력 값이 큰 경우를 대비해서input() 대신 sys.stdin.readline() 을 사용하는 것이 유리하다📌 기본 입력 처리import sysinput_func = sys.stdin.readlinen = int(input_func()) # 정수 하나 입력 받기arr = list(map(int, input_func().split())) # 한 줄에 여러 정수 입력 받기 sys.stdin.readline()은 개행 문자 (\n)도 같이 입력받기 때문에,strip()..

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..

알고리즘을 파이썬으로 준비하려는 개발자들에게 도움이 될 만한 필수 개념을 정리해보려고 합니다.저처럼 주 언어는 Java이지만 코딩 테스트는 Python으로 준비하는 개발자들에게 조금이나마 도움이 되고자중간에 Java 개념과 비슷하거나 다른게 있으면 적어놨으니 같이 참고해주세요만약 자바 개발자가 아니라면 해당 부분은 가볍게 넘어가주시면 됩니다.알고리즘을 풀기 전에 한 번 훑어보면서 개념을 정리하고 같이 코딩 테스트를 준비해봐요 !! 파이팅 !! 1.  기본 문법변수 선언x = 10 # 타입 지정 없음name = "Dengju"파이썬은 변수 선언 시 타입을 명시하지 않아도 된다자바처럼 int, String 등을 사용하지 않는다조건문if x > 5: print("x is greater than 5")elif ..

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에서 다음 값과 비교하기 ..