초코chip의 코딩 생활

개념 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘 DFS/BFS 재귀함수(Recursive Function) 자기 자신을 다시 호출하는 함수 스택 구조로 함수들이 쌓임 스택 구조로 함수가 쌓이기 떄문에 스택 자료구조 대신 재귀함수를 이용하는 경우가 있음 모든 재귀함수는 반복문을 이용하여 동일한 기능 구현 가능 재귀 함수는 반드시 종료 조건을 설정 해야함 DFS(Depth-First Search) 깊이 우선 탐색 그래프가 있을때 방문 기준을 문제 조건을 잘 보고 설정 해야함 탐색 노드를 스택에 삽입하고 방문 처리 진행 방문 기준으로 다음 인접 노드를 스택에 넣고 방문 처리 진행 위 과정 계속 코드 주의!) 노드 연결시 양방향 그래프이면 서로 연결을 해줘야함 boolea..

개념 언제 사용?: 데이터 업데이트가 가능한 상황에서 구간 합를 구해야할 경우에 정의: 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

배경 코테를 풀다가 출력 시간 때문에 시간 초과 문제가 발생하였다. 그래서 자바로 빠른 출력을 하는 방법을 정리하였다. 방법 StringBuilder를 사용하여 한번에 출력하기 .append()를 사용해 출력할 내용들을 모으고 System.out,print()를 이용해 한번에 출력 // 1. 생성 StringBuilder sb = new StringBuilder(); // 2. 출력 모으기 for(int i=0; i < n; i++){ for(int j=0; j

개념 정의: 데이터를 특정 기준에 따라 순서대로 나열하는 것 언제 사용?: 데이터의 입력 순서가 문제 푸는 것에 의미가 없을때 사용 시간복잡도: 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..