Coding Diary

1. 개념 배열의 원소를 하나씩 살피면서, 살피는 원소와 살피는 원소 앞에 있는 원소를 비교해서 만약 앞에 있는 원소보다 작다면 살피는 원소를 앞으로 보낸다. 더 이상 앞으로 보낼 수 없을 때까지 반복한다.(오름차순 기준) 2. 특징 1) 장점 안정한 정렬 방법(정렬하면서 같은 원소가 있어도 위치가 변하지 않는다) 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다. 2) 단점 비교적 많은 레코드들의 이동을 포함한다. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다. 3. 시간복잡도 1) 최선(다 정렬되어 들어올 경우) 비교횟수 target이 target 바로 전 것과 비교되고 ..

1. 개념 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘, 해당 범위에서 특정 조건에 맞는지 확인한다 복도 전체의 길이가 10, 창문의 크기가 3이라고 하자. 크기가 3인 창문을 복도 처음에 놓고 1씩 옮기며 조건에 맞는지를 확인하는 것을 슬라이딩 윈도우라고 할 수 있다. 2. 특징 O(N)의 시간복잡도를 가짐 3. 관련 문제 백준 12891 GitHub - Lee-Min-Jung/coding_test_practice Contribute to Lee-Min-Jung/coding_test_practice development by creating an account on GitHub. github.com 백준 11003

1. 개념 두 개의 포인터를 사용하는 알고리즘, 보통 left와 right, start와 end 등으로 정한다 2. 투 포인터 이동 원칙 문제마다 이동 원칙은 달라짐 대체로 수가 차례대로 정렬되어 있을 때 적용 1) start와 end가 같이 처음부터 시작 sum은 start부터 end까지의 합을 의미함 sum N 주어진 수 보다 합이 더 커졌으니 이때의 start부터 end는 정답이 될 수 없는 범위인 것. 그러니 범위의 변경이 필요. 그런데 end를 증가시키면 소용이 없음. 어차피 더 커지기만 하니까. 그래서 su..

1. 개념 배열 A의 합 배열을 구해서 기존 배열의 일정 범위의 합을 구하는 방법 2. 합 배열 1) 개념 배열 A의 인덱스 0부터 인덱스 i까지 더한 값을 가지고 있는 배열 2) 공식 배열 A = {5, 4, 3, 2, 1} S[1] = A[0] S[2] = A[0] + A[1] S[3] = A[0] + A[1] + A[2] S[4] = A[0] + A[1] + A[2] + A[3] S[5] = A[0] + A[1] + A[2] + A[3] + A[4] int[] A = {5, 4, 3, 2, 1}; int[] S = new int[A.length + 1] // 합 배열 index를 1부터 시작하는거라고 하기 위해 길이를 1 늘림 for(int i = 1; i

1. 개념 배열의 원소를 순서대로 살피면서, 살피는 원소 아래에 있는 모든 원소를 확인해서 만약 더 작은 것이 있다면 현재 살피는 원소와 해당 원소를 바꾼다. 2. 특징 제자리 정렬 알고리즘의 하나(입력 배열 이외에 추가 메모리를 요구하지 않음) 1) 장점 구현이 쉽다 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 2) 단점 안정 정렬이 아니다(값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.) 정렬 규칙이 다수이거나 특정 순서를 유지해야 할 때 문제가 될 수 있다. 시간복잡도 상 효율이 좋지 않음 3) 단점 보완 방법 이중 선택 정렬 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다. 탐색을 응용하여 개선 한 번의 탐..