✔ 수 정렬하기 2 [백준 2751] 문제 분석하기 N의 최대 범위가 1000000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행해야 하므로 병합 정렬로 정렬을 수행 손으로 풀어보기 정렬할 그룹을 최소 길이로 나눈 후, 나눈 그룹마다 병합 정렬을 수행 병합된 그룹을 대상으로 정렬 예) 원본 배열의 길이가 5이므로 2, 2, 1 길이로 나눠 병합 정렬 (2 / 3 분할 → 2 / 2 / 1 분할) step0 1 2 3 4 5 5 4 3 2 1 step1 (분할 후 그룹마다 정렬) 1 (index1) / 2 (index2) 3 (index1) / 4 (index2) 5 4 / 5 2 / 3 1 step 2 (합병 후 그룹마다 정렬) 1 2 3 (index1) / 4 / 5 (index2) 4 5 1 / ..
✔ K번째 수 [백준 11004] 문제 분석하기 N의 최대 범위가 5000000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 됨 이때 어떤 값을 pivot으로 정하면 K번째 수를 더 빨리 구할 수 있을지 생각해보면서 문제에 접근 정렬을 수행하면서 pivot의 왼쪽 부분에 K가 있을 경우 왼쪽만 정렬을 수행하고 오른쪽에 K가 있을 경우 오른쪽만 정렬을 수행 손으로 풀어보기 중간 위치를 pivot으로 설정한 다음 i, j의 이동을 편하게 하기 위해 pivot을 맨 앞에 있는 값과 swap i와 j를 pivot을 제외한 그룹에서 왼쪽, 오른쪽 끝으로 위치하도록 함 j를 이동하면서 j가 pivot보다 크면 j-- 연산을 반복 j를 이동한 후 i가 pivot보다 작으면서 i보다 j가 크면 i++ 연산을 ..
✔ ATM [백준 11399] 문제 분석하기 인출 시간을 기준으로 값을 정렬한 후 각 사람이 돈을 인출하는 데 필요한 시간을 더하는 방식으로 문제에 접근 손으로 풀어보기 삽입 정렬을 이용해 인출 시간을 기준으로 데이터를 오름차순 정렬 정렬된 데이터를 바탕으로 모든 사람이 돈을 인출하는 데 필요한 최솟값을 구함 인출에 필요한 시간은 앞사람들의 인출 시간의 합 + 자신의 인출 시간이므로 합 배열을 이용 슈도코드 작성하기 N(사람 수) A(자릿수별로 구분해 저장한 배열) S(A 합 배열: 각 사람이 인출을 완료하는데 필요한 시간을 저장하기) for(N만큼 반복하기) { A 배열 저장하기 } for(i: N만큼 반복하기) { for(j: i - 1 ~ 0까지 뒤에서부터 반복하기) { 현재 범위에서 삽입 위치 찾..
✔ 버블 소트 [백준 1377] 문제 분석하기 버블 정렬의 swap이 한 번도 일어나지 않는 루프가 언제인지 알아내는 문제 하지만 N의 범위가 500000이므로 시간 복잡도가 O(N²)인 버블 정렬로 문제를 풀면 시간을 초과할 수 있으므로 안 쪽 for문이 몇 번 수행되었지 구하는 다른 아이디어가 필요 그러므로 swap을 수행할 때 swap의 왼쪽으로 이동할 수 있는 최대 거리는 1이므로 데이터의 정렬 전 index와 정렬 후 index를 비교하여 왼쪽으로 가장 많이 이동한 값을 찾아 문제를 해결 손으로 풀어보기 자바에서 기본적으로 제공하는 시간 복잡도가 O(NlogN)인 sort() 함수로 배열을 정렬 각 데이터마다 정렬 전 index 값에서 정렬 후 index 값을 빼고 최댓값을 찾음 그리고 swap..
✔ 절댓값 힙 [백준 11286] 문제 분석하기 N의 최대 범위가 100000이므로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있음 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제에 접근 이 때 절댓값이 같을 때는 음수를 우선하여 출력해야 하는 정렬이 필요하므로 우선수위 큐의 정렬 기준을 직접 정의해야 함 손으로 풀어보기 x = 0일 때 큐가 비어 있을 때는 0을 출력하고 비어 있지 않을 때는 절댓값이 최소인 값을 출력함 단, 절댓값이 같다면 음수를 우선하여 출력함 x ≠ 0일 때 add로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬 예) [1, -1, 0, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0, 0, 0, 0, 0, ..
✔ 오큰수 [백준 17298] 문제 분석하기 N의 최대 크기가 1000000이므로 반복문으로 오큰수를 찾으면 제한시간이 초과되므로 스택을 사용해 문제에 접근 손으로 풀어보기 스택이 채워져 있고 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감 수열 길이만큼 반복한 다음 현재 스택에 남아 있는 인덱스에 -1을 저장 예) [3, 5, 2, 7] 스택 0 1 (push) 0 (pop → 5) 2 (push) 1 3 (push) 2 (pop → 7) 1 (pop → 7) 3 (pop → -1) 0 1 2 3 5 7 7 -1 슈도코드 작성하기 N(수열 개수) A[](수열 배열) ans[](정답 배열) 수열 배열 채우..
✔ 최솟값 찾기 [백준 11003] 문제 분석하기 슬라이딩 윈도우와 정렬을 사용하여 일정 범위 안에서의 최솟값을 구하도록 문제에 접근 하지만 N과 L의 범위가 5000000이므로 일반적인 nlog(n)의 시간 복잡도를 가지는 정렬를 사용할 경우 2.4초를 초과하므로 O(n)의 시간 복잡도로 해결하기 위해 덱으로 슬라이딩 윈도우를 구현 손으로 풀어보기 덱에 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장 새 노드가 저장될 때 덱 뒤에서부터 비교를 시작 만약 기존에 존재하는 덱의 숫자가 새 노드의 숫자보다 클 경우 기존 노드를 제거 기존에 존재하는 덱의 숫자가 새 노드의 숫자보다 작을 경우 탐색을 멈추고 새 노드를 덱에 저장 덱을 이용한 정렬 효과를 통해 정리한 후 인덱스 범위가 슬라이딩 윈도우 범위..
✔ 좋다 [백준 1253] 문제 분석하기 N의 개수가 최대 2000이므로 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N² 보다 작지 않을 경우 최종 시간 복잡도가 N³(8000000000 > 200000000)이 되어 제한 시간 안에 문제를 풀 수 없게 됨 그러므로 데이터를 정렬하고 자기 자신을 포함하지 않도록 투 포인터를 지정하여 문제에 접근 손으로 풀어보기 수를 입력받아 배열에 저장한 후 정렬 투 포인터 i, j를 양쪽 끝에 위치시킨 후 조건에 적합한 포인터 이동 원칙을 활용해 탐색을 수행 A[i] + A[j] > K: j--; A[i] + A[j] < K: i++; A[i] + A[j] == K: i++; j++; count++; 배열의 모든 수에 대하여 반복 슈도코드 작성하기 N(수의 개수) ..
