✔ ABCDE [백준 13023] 문제 분석하기 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5 이상(5개의 A, B, C, D, E가 재귀 형태로 연결)이면 1을 출력 DFS의 시간 복잡도는 O(V + E)이므로 최대 4000(2000 + 2000), 모든 노드를 진행했을 때 4000 * 2000이므로 제한 시간 내에 문제를 풀 수 있음 손으로 풀어보기 그래프 데이터를 인접 리스트에 저장 모든 노드에서 DFS를 수행하며 재귀 호출마다 깊이를 더함 깊이가 5가 되면 1을 출력하고 프로그램을 종료 모든 노드를 돌아도 1이 출력되지 않았다면 0을 출력 슈도코드 작성하기 N(노드 개수) M(엣지 개수) A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열) arrive(도착 확인 변..
✔ 신기한 소수 [백준 2023] 문제 분석하기 DFS는 재귀 함수의 형태를 띄고 있으므로 재귀 함수에 자릿수 개념을 붙이고 문제 조건에 맞도록 가지치기하여 문제에 접근 손으로 풀어보기 자릿수가 1개인 소수는 2, 3, 5, 7이므로 이 수부터 탐색을 시작 소수가 아닌 4, 6, 8, 9를 제외한 가지치기 방식을 적용 이어서 자릿수가 2개인 현재 수 * 10 + a를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘림 단, a가 짝수인 경우는 항상 2를 약수로 가지고 있으므로 가지치기로 a가 짝수인 경우를 제외함 이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력 예) N = 4 자릿수 1개 자릿수 2개 자릿수 3개 자릿수 4개 신기한 소수 2 3 5 ..
✔ 수 정렬하기 3 [백준 10989] 문제 분석하기 N의 최대 개수가 10000000으로 매우 크기 때문에 O(nlogn) 보다 더 빠른 알고리즘을 사용해야 하므로 시간 복잡도가 O(kn)인 기수 정렬을 사용하여 문제에 접근하며 구간 합을 이용하여 구현 손으로 풀어보기 자릿수가 서로 다른 경우 자릿수가 적은 수 앞에 0이 채워져 있다고 생각하여 큐에 삽입 일의 자릿수를 기준으로 큐에 삽입 후 큐에서 순서대로 pop 십의 자릿수를 기준으로 큐에 삽입 후 큐에서 순서대로 pop 백의 자릿수를 기준으로 큐에 삽입 후 큐에서 순서대로 pop 마지막 자릿수를 기준으로 정렬할 때까지 반복 예) A = [5, 2, 3, 1, 4, 2, 3, 5, 1, 7] jarisu output bucket 1 [0, 0, 0,..
✔ 버블 소트 [백준 1517] 문제 분석하기 N의 최대 범위가 500000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행해야 하므로 버블 소트를 사용하면 제한 시간을 초과하게 됨 그러므로 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 이용해야 함 이때 그룹을 병합하는 과정에서 데이터가 앞으로 이동하는 수만큼 swap이 일어난 것과 동일하므로 이를 통해 문제에 접근 손으로 풀어보기 정렬할 그룹을 최소 길이로 나눈 후, 나눈 그룹마다 병합 정렬을 수행 병합된 그룹을 대상으로 정렬 이때 index가 이동한 거리를 result에 저장 예) 원본 배열의 길이가 3이므로 2, 1 길이로 나눠 병합 정렬 step 0 1 2 3 3 2 1 step 1 (swap : 1) 1 (index1) / 2 (index..
✔ 수 정렬하기 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..
