Rootable의 개발일기

📌 DP(Dynamic Programming, 동적 계획법)이란 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 🔎 풀이 방법 ✔ 타뷸레이션(Tabulation) 작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법 예제: 피보나치 수열 import java.io.IOException;public class Main { static int[] A; public static void main(String[] args) throws IOException { int N = readInt(); A = new int[N + 1]; fibonacci(N); for (int i = 1; i ..

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도 : O(logN) 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다. 📌 탐색 과정 현재 데이터셋의 중앙값을 선택 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 중앙값 < 타깃 데이터일 때 중앙값 기분으로 오른쪽 데이터셋을 선택 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 응용 문제로 특정 범위를 주고 정렬이 가능한 상태에서 O(logN) 내에서 탐색해야 할 때 사용할 수 있다. Reference:

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 시간 복잡도 : O(N^2) - 평균/최악, O(N) - 이미 정렬된 경우 삽입 정렬은 정렬된 부분(Sorted Portion)과 정렬되지 않은 부분(Unsorted Portion)으로 나눠 이해하면 쉽다. 정렬되지 않은 부분의 첫 번째 요소를 가져와 졍렬된 부분의 올바른 위치에 삽입하는 과정을 반복 📌 정렬 과정 현재 index에 있는 데이터 값을 선택첫 번째 요소는 정렬된 부분으로 간주현재 선택한 데이터가 정렬된 데이터 범위에서 삽입될 위치를 탐색처음 자신보다 작은 값이 나올 때까지(오름차순)처음 자신보다 큰 값이 나올 때까지(내림차순)삽입 위치부터 index 위치까지 shift 연산(우측 이동)을 수행삽입 위치..

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 시간 복잡도: O(N^2) 📌 정렬 과정 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산 루프 범위가 끝날 때마다 2~3 반복 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외 비교 대상이 없을 때까지 1~5 반복 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 됨 📌 알고리즘 public class BubbleSort { public static void main(String[] args) throws IOException { BufferedWriter bw = new..