🧩 비트마스크 연산자 1. and 연산자 (&) - 둘 다 1일 때만 1, 아니라면 0이 되는 연산 2. or 연산자 (|) - 둘 중 하나라도 1이라면 1, 아니라면 0이 되는 연산 3. xor 연산자 (^) - 두 bit가 다른 값이라면 1, 같은 값이라면 0이 되는 연산 4. left shift 연산자 (> k) & 1) == 1 : 0인지 1인지로 판단 (1이면 존재, 0이면 X) - 괄호를 잘 쳐주지 않으면 에러가 난다. 2. 수 새롭게 추가 / 삭제 (^) x ^ (1
코테/알고리즘
🧩 필요한 최소 동전의 수 (은행) ⇨ i : 지금까지 선택한 동전의 합 ⇨ dp[i] : 필요한 최소 동전 수 🧩 배낭 문제 (Knapsack) dp[ i ][ j ] : 가능한 보석 가치의 최대값 • i번째 보석까지 고려했고, 지금까지 선택한 보석 무게의 합은 j ⇨ i번째 보석을 가방에 넣었는지 / 넣지 않았는지 구분해 점화식
📍 정의 및 특징 - 각 단계마다 지금 당장 가장 좋은 방법만을 선택 (현재 선택이 앞으로 남은 선택들에 어떤 영향을 미칠지 고려 X) - 그리디를 사용해 항상 최적해를 구할 수 있는 문제를 만난 경우, DP보다 훨씬 빠름 🧩 필요한 자료구조 ✔ 정렬된 배열 / 리스트 ✔ 우선순위 큐 : 가장 크거나 작은 원소 찾을 때 사용 (최소 힙 / 최대 힙 활용) ✔ 스택 / 큐 : 특정 순서로 요소 처리 시 활용 (ex ; 회의실 시간표 짤 때 시간 / 종료 시간 기준 정렬된 배열 -> 스택 / 큐로 활용 가능) ✔ 해시 맵 : 특정 값을 빠르게 찾고 업데이트 할 때 사용 ✔ 배열 / 리스트를 활용한 직접 구현 📍 실행 과정 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택 적절성 검사 : 현재 선택..
📍 정의 및 특징 브루트포스에서 가지치기 진행 - DFS의 한 종류 (재귀) - N이 최대 10으로 작을 경우, 백트래킹 가능 #가지치기 #DFS #재귀 📍 시간 복잡도 ▷ 중복 가능한 경우 ⋄ N^N ⋄ N = 8 까지 가능 ▷ 중복 불가한 경우 ⋄ N ! ⋄ N = 10 까지 가능 📍 필요 변수 ✔ 방문 여부 확인 배열 : boolean[] - 중복 확인용 ✔ 선택값 입력 배열 : int[] 📍 실행 과정 종료 조건 재귀 위한 for문 - 순열 : for문, 0부터 시작 / 조합 : for문, startIdx부터 시작 1) 결과값 추가 2) 재귀 ; 함수 호출할 때마다 매개변수 값 갱신하는 식으로 동작 public static void recur(int startIdx, int depth) { // ..
📍 정의 및 특징 완전 이진 트리의 일종 반정렬 상태 (완전 정렬 X) 중복값 허용 시간 복잡도 : O(logN) 종류 : 최대 힙 (부모 노드가 가장 큰) / 최소 힙 (부모 노드가 가장 작은) 구현 : 우선순위 큐 #완전이진트리 #우선순위큐 📍 필요 변수 ✔ 우선순위 큐 ✔ 배열 📍 실행 과정 부모 노드가 N (N ≥ 1)이면, 자식 노드는 *2, *2 + 1 자식 노드가 N이면, 부모 노드는 N/2 ➕ 예제 [백준/JAVA] 1927번: 최소 힙 🔺 문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는( bono039.tistory.com [..
📍 정의 및 특징 - 부분 배열의 길이(크기) = window가 고정적 - 포인터 하나만 있어도 됨. - 옆으로 이동하더라도, 옮기기 전과 옮기고 난 후의 겹치는 부분은 그대로 두고, 기존 부분에서 빠지는 왼쪽 칸 값은 삭제하고, 새 구간에 포함되는 오른쪽 값은 추가 ➕ 예제 [백준/JAVA] 10025번: 게으른 백곰 🔺 문제 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.ac bono039.tistory.com [백준/JAVA] 17298번: 오큰수 🔺 문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주..
📍 정의 및 특징 주어진 수열에서 증가하는 순서로 연속되는 부분 수열 중 가장 긴 길이를 구하는 문제 📍 LIS 실행 방법 1) DP 활용 → 시간 복잡도 : O(N^2) 2) 이분 탐색 활용 → 시간 복잡도 : O(N log N) 📍 필요 변수 ✔ DP / LIS 배열 🧩 1) DP를 활용한 LIS 실행 과정 : O(n^2) DP 테이블을 생성하여 각 원소를 마지막으로 하는 LIS의 길이 저장 초기값으로 모든 원소의 LIS 길이를 1로 설정 각 원소 i에 대해, 이전 원소 j(0 nums[j]인지로 판단) 만약 nums[i] > nums[j]라면, dp[i] = max(dp[i], dp[j] + 1) 수행 ⇨ i번째 원소를 마지막으로 하는 LIS의 길이 갱신 모든 i에 대해 위 과정을 반복하면, dp ..
📍 정의 및 특징 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 - DP의 일종 - 문제 유형 : 최장 공통 부분 수열 길이 구하기, 최장 공통 부분 수열 구하기 #DP 📍 필요 변수 ✔ 2차원 LCS 배열 - LCS 길이 찾기용 ✔ 2차원 result 배열 - LCS 배열 결과값 저장용 📍 실행 과정 Case 1) 최장 공통 부분 수열 "길이" 찾기 /* LCS 길이 구하기 */ if(i == 0 || j == 0) LCS[i][j] = 0; else if (ch1[i] == ch2[j]) LCS[i][j] = LCS[i - 1][j - 1] + 1; else LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]) 문자열 A와 B를 한 ..
목차 📍 정의 및 특징 단어들을 사전 형태로 생성 후, 트리의 부모-자식 노드 관계 이용해 빠르게 문자열을 검색하는 알고리즘 - N진 트리 : 문자 종류 개수에 따라 N 결정 (예 : 알파벳 - 26진 트리) - Map Interface 사용 (computeIfAbsent , getOrDefault) - 문자열 집합이 크고 다양한 검색이 필요한 경우 효율적 - 시간 복잡도 : O(N) (N : 검색하려는 문자열의 길이) 📍 활용 사례 : 검색어 자동 완성, 사전 검색, 문자열 검사 등 📍 실행 과정 : Trie에 문자열 저장 → 문자열 검색 - 루트 노드, 공백 유지 (= 빈 문자열) - 검색 노드, 공백 상태면 신규 노드 생성하고, 아니면 이동 ➕ 예제 5052번: 전화번호 목록 첫째 줄에 테스트 케이..
