⚡문제 유형 배열, 정렬 📝문제 연속된 두 요소의 차이가 동일한 경우 일련의 숫자를 산술 진행 이라고 합니다. 숫자 배열이 주어지면 배열이 산술 진행 을 형성하도록 재배열될 수 있으면 true 를 반환 하고 그렇지 않으면 false를 반환 합니다. 📘예시 Input: arr = [3,5,1] Output: true Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements. Input: arr = [1,2,4] Output: false Explanation: There is no way to reorder the elem..
⚡문제 유형 배열, 수학 📝문제 입력값인 배열의 요소를 다 곱했을 때 음수면 -1, 0이면 0, 양수면 1을 반환해라 📘예시 Input: nums = [-1,-2,-3,-4,3,2,1] Output: 1 Explanation: The product of all values in the array is 144, and signFunc(144) = 1 Input: nums = [1,5,0,2,-3] Output: 0 Explanation: The product of all values in the array is 0, and signFunc(0) = 0 Input: nums = [-1,1,-1,1,-1] Output: -1 Explanation: The product of all values in the a..
⚡문제 유형 배열 📝문제 입력값으로 현재 좌표 위치인 X, Y와 좌표에 찍힌 점의 정보인 points가 온다. 사용자 위치와 동일한 x 좌표 또는 동일한 y 좌표를 공유하는 경우 유효한 point이다. 현재 위치에서 맨해튼 거리 가 가장 작은 유효한 지점 의 points를 반환하는 문제이다. 정답이 여러개면 인덱스 번호가 가장 작은 것을 반환하고 유효한 포인트가 없으면 -1를 반환한다. 두 점 사이의 맨해튼 거리는 (x1, y1)(x2, y2)abs(x1 - x2) + abs(y1 - y2)이다. 📘예시 Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]] Output: 2 Explanation: Of all the points, only [3,1..
⚡문제 유형 비트 📝문제 입력값에서 1의 개수를 구해라 📘예시 Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. Input: n = 11111111111111111111111111111101 Output: 31 E..
⚡문제 유형 비트 📝문제 n이 2의 거듭제곱 수이면 true, 아니면 false 📘예시 Input: n = 1 Output: true Explanation: 20 = 1 Input: n = 16 Output: true Explanation: 24 = 16 Input: n = 3 //3은 2의 제곱수가 아님 Output: false 📗풀이 & 연산자를 사용합니다. & 연산자는 AND 비트 연산자로 두 개의 피연산자의 각 자리마다 대응하는 비트가 모두 1일 경우 1을 반환합니다. 예시로 8이 2의 거듭제곱인지 확인 해보겠습니다. 먼저 8과 7을 2진수로 변환합니다. 8과 7을 & 연산자로 계산하면 0000이 나오게 됩니다. 이때 모두 0 이나오면 2의 거듭제곱이고 0이 아닌 수가 나오게 되면 2의 거듭제곱 ..
⚡정의 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조 📚활용 방식 검색과 정렬 : 이진 탐색 트리와 이진 힙 구현에 활용 허프만 코딩 : 연관 분기 구조 위한 데이터 표현에 활용 📚이진 트리의 종류 포화 이진 트리 (Perfect binary tree) 완전 이진 트리 (Complete binary tree) 정 이진 트리 (Full binary tree) 편향 이진 트리 (Skewed binary tree) 균형 이진 트리 (Balanced binary tree) 📎포화 이진 트리 (Perfect binary tree) 모든 레벨의 노드가 가득 채워져 있는 트리 특징 Leaf 노드를 제외한 모든 자식은 2개의 노드를 보유 노드의 개수 : n = 2^h -1 트리 형태 📎완전 이진 트리(C..
⚡문제 유형 DP 📝문제 주어진 triangle을 위에서 아래로의 최소 경로 합계를 반환합니다 . 각 단계에 대해 아래 행의 인접한 번호로 이동할 수 있습니다. 즉, 현재 행의 인덱스 i에 있는 경우 다음 행의 인덱스 i 또는 인덱스 i + 1로 이동할 수 있습니다. -> 피라미드 구조로 내려오면서 i 또는 i+1로 이동해서 최솟값 구하는 문제 📘예시 Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2// 2 3 4// 최솟값을 만들기 위해 2에서 갈 수 있는 다음 행 (3,4) -> 3 6 5 7// 최솟값을 만들기 위해 3에서 갈 수 있는 다음 행 (6,5) -> 5 4 1 8..
⚡정의 그래프의 일종으로 두 노드 사이의 하나의 간선만 연결되어 있는, 최소 연결과 계층 형태의 비선형 자료구조 📚트리 구조 및 용어 노드 : 하나 이상의 값을 갖는 객체 단위 간선 : 두 노드를 연결하는 선 루트 노드 : 부모가 없는 최상위 노드 단말 노드 : 자식이 없는 노드 부모 노드 : 특정 Sub-Tree 내에서의 상위 노드 자식 노드 : 특정 Sub-Tree 내에서의 하위 노드 📚트리 특징 노드 크기(size) : 자신을 포함한 모든 자손의 노드 개수 노드 깊이(depth) : 루트에서 특정 노드에 도달하기 위한 간선의 개수 노드 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 노드 차수(degree) : 노드가 지닌 가지의 수 트리 차수(tree degree) : 트리의 최대 차..
개념 이미 정렬된 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀서 가며 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘 특징 및 설명 오름차순으로 정렬된 배열이 필요하고 왼쪽의 끝 인덱스(left), 오른쪽 끝 인덱스(right), 중간 값(mid)이 필요함 -> 보통(start, end 사용) target 값과 중간값 비교 1. target 값 == 중간 값이랑 같다 -> 끝! 2. target 값 left = mid + 1 3. target 값 > 중간 값 -> right= mid - 1 복잡도 O(log(N)) 매번 절반의 탐색할 데이터를 제외시킨다 라고 간단하게 생각하면 된다. 예시 배열 nums의 target 값은 9이고 배열의 중간 값(pivot)은..