개발새발

1단계: 이진트리가 뭔지부터 이해하기이진트리를 일상에 비유해보면,가계도: 한 사람(부모)이 최대 2명의 자녀를 가질 수 있는 구조토너먼트 대진표: 각 경기에서 2팀이 만나서 1팀이 올라가는 구조 코드로 표현하기(javascript)class TreeNode { constructor(val) { this.val = val; // 노드의 값 this.left = null; // 왼쪽 자식 this.right = null; // 오른쪽 자식 }} 실제로 트리 만들어보기// 간단한 트리 만들기// 1// / \// 2 3// /// 4const root = new TreeNode(1);root.left = new TreeN..

1단계: 기본 개념 이해하기이진트리의 기본 구조각 노드는 최대 2개의 자식 (left, right) 을 가짐루트 노드부터 시작해서 계층적 구조리프 노드는 자식이 없는 노드 기본 용어높이(height): 루트에서 가장 깊은 노드까지의 거리깊이(depth): 루트에서 특정 노드까지의 거리완전 이진트리, 포화 이진트리 등의 특수한 형태 2단계: 기본 순회 방법 마스터하기이진트리 문제의 90%는 순회가 핵심전위 순회(Preorder): 루트 -> 왼쪽 -> 오른쪽중위 순회(Inorder): 왼쪽 -> 루트 -> 오른쪽후위 순회(Postorder): 왼쪽 -> 오른쪽 -> 루트레벨 순회(Level-order): BFS 방식으로 레벨별로 순회각 순회를 재귀와 반복문 두 가지 방식으로 모두 구현할 수 있어야 함3단계..

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. 대각선 번호 구하기입력..