초코chip의 코딩 생활

개념 언제 사용?: 데이터 업데이트가 가능한 상황에서 구간 합를 구해야할 경우에 정의: 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있는 자료구조 특정 숫자 K의 비트 중 0이 아닌 마지막 비트 찾는 방법: K & - K 구현 방법 BIT 구조 만들기 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수 예: k = 16의 마지막 비트는 16 > 1~16까지의 구간합을 저장한다는 의미 k = 7의 마지막 비트는 1 > 자기 자신의 값만 저장한다는 의미 코드 // 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k) private static int n, m, k; // 전체 데이터의 개수는 최대 1,000,000개 private static long[] arr = n..

구간 합 정의: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수 목적 알고리즘 코딩 테스트에서 사용 빈도가 높음 합 배열 개념 정의: 기존 배열 누적 합을 저장하는 배열 S[i] = A[0] + A[1] + ... A[i] 목적: 구간 합에 대한 시간 복잡도를 줄이기 위해 기존: for문을 이용해 구간 합 구함 -> O(N) 해당 기술: 공식을 통해 한번에 구함 -> O(1) 합 배열 생성 S[i] = S[i-1] + A[i] 공식 활용 i-1을 사용하기에 배열 첫 시작 인덱스는 1로 설정 즉, 배열의 크기를 n+1로 선언 int[] S = new int[N+1] //배열 크기 +1 처리 //1번째 인덱스 부터 시작 for(int i=1; i

개념 정의 정의: 투 포인터로 범위를 지정한 다음 범위(window)를 유지한채로 이동(sliding)하며 문제를 해결하는 방법 중요 전체 크기(N)와 윈도우 크기(M)이 있을때, 핵심은 시간 복잡도를 O(NM)이 아닌 O(N)으로 진행하는 것 즉, 교집합의 정보를 공유하고, 차이가 발생하는 양쪽 끝 원소만을 갱신하는 방법 언제 사용? 특정 범위를 지속해서 탐색하는 경우 int count = 0; //투 포인터 선언 int s_index = 0; int e_index = P-1; while(e_index = A && hm.get('C') >= C && hm.get('G') >= G && hm.get('T') >= T){ count++; } //차이가 발생하는 왼..

개념 정의: 리스트에 순차적으로 접근할 때, 2개의 포인터로 알고리즘 시간 복잡도를 최적화 하는 방법 시간 복잡도: O(n) 단, 정렬이 된 상태여야만 사용 가능하기에 정렬이 필요한 경우 O(nlogn) 언제 사용? 기준값(N)을 만드는 두 수의 조합 기준값(N)을 만들 수 있는 두 수의 조합의 경우의 수 int[] A = new int[n];//정렬된 배열 int M; //기준값 //투 포인터 선언 int s_index = 0; int e_index = n-1; //결과 경우 수 저장 int count = 0; while(s_index < e_index){ //기준값 보다 작은 경우 if(A[s_index] + A[e_index] < M){ s_index++; } //기준값 보다 큰 경우 else if..

개념 정의: 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수 구현 방법 모든 약수가 가운데 약수(제곱근)를 기준으로 곱셈 연산에 대해 대칭을 이룸 따라서, 특정 자연수의 약수를 찾을 때, 가운데 약수까지만 확인하면 됨 코드 public class Main { public static boolean isPrimeNum(int x){ //2부터 x의 제곱근까지만 모든 수를 확인 for(int i=2; i

개념 정의: 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는 방법 즉, 메모리를 적절히 사용하여 수행 시간 효율성을 늘리는 방법 사용 조건: 점화식을 가진 구조 최적 부분 구조: 큰 문제를 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있어야함 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야함 언제 생각? : 여러가지 선택지가 있는데 그리디 기법으로 안풀리면 한번 생각해보기 단, i번째 선택지가 i-1번째 선택지에 영향을 받아야함 즉, 이전 선택을 계속 누적해서 가는 문제들 다이나믹 프로그래밍 vs 분할 정복 공통점: 두 방법 모두 최적 부분 구조를 가진다. 차이점: 다이나믹 프로그래밍: 동일한 작은 문제를 반복적으로 해결 분할 정복: 동일한..

개념 순차 탐색: 데이터를 찾기 위해 앞에서부터 데이터를 확인하는 방법 시간 복잡도: O(N) 이진 탐색: 정렬되어 있는 리스트의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법 즉, 시작점 + 끝점 + 중간점을 설정을 해줘야함 시간 복잡도: O(logN) 방법 public static int binarySearch(int[] List, int target, int start, int end){ int mid; int result = -1; while(start

개념 정의: 데이터를 특정 기준에 따라 순서대로 나열하는 것 언제 사용?: 데이터의 입력 순서가 문제 푸는 것에 의미가 없을때 사용 시간복잡도: O(NlogN) 요약 선택 정렬 정의: 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 방법 시간 복잡도: O(N^2) public static void selectSort(int[] List){ int minIndex; for(int i=0; i= Right ) 기준값과 작은 값(Right)의 위치를 변경 기준 값을 기준으로 데이터 묶음을 나누어 작업을 진행 시간 복잡도: O(N * LogN) 하지만, 이미 정렬된 배열에 대해서 작업을 한다면 O(N^2) 복잡도가 발생 public static void quic..

개념 정의: 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정 어떤게 구현?: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 예시: 알고리즘 간단 but 코드가 길어짐 실수 연산에서 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어서 처리해야 하는 문제 적절한 라이브러리 찾아서 사용해야 하는 문제 (예시 - 순열, 조합) 시뮬레이션 유형 정의: 일련의 명령에 따라 개체를 주어진 공간내에서 이동시키는 문제 행렬(2차원 배열) 알고리즘 문제에서 2차원 공간은 행렬로 사용 방향 벡터 시뮬레이션 및 완전 탐색 문제에서는 방향 벡터가 잘 활용 됨 // 동, 북, 서, 남 순서로 이동 벡터 방향 값 int[] dx = {0, -1, 0, 1}; int[] dy = {1, 0, -..

개념정의: 현재 상황에서 지금 당장 좋은 것만 고르는 방법언제 사용?: 여러가지 선택지가 있고, 선택지를 골라서 최적의 방법을 찾는 문제에서 생각해봐야함핵심: 단순히 가장 좋아 보이는 것만 선택해도 최적의 해가 도출되는지를 검토해야함예시: 루트 노드부터 거쳐 가는 노드 합이 최대가 되도록 하는 해 찾기그리디 알고리즘을 선택하여 가장 큰 노드만 찾아서 탐색을 하도록 진행하면 최적해가 나오는지 검토그리디 기법정답5 -> 10 -> 4 = 195 -> 7 -> 9 = 21 해당 문제는 그리디가 아님일반적인 상황에서 그리디는 최적의 해를 보장할 수는 없음하지만 코테에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황을 만듬  문제거스름 돈 최적의 해를 구하기 위해서 가장 큰 화폐 단위부터 ..