본문 바로가기
  • 기억의 유한함을 기록의 무한함으로✍️　 　 　 　 　 　 예비 개발자가 꿈꾸는 공간 여기는 안나의 개발 블로그 💻

Algorithm45

99클럽 코테 스터디 1일차 TIL + 배열/스택 💡문제[level 2] 뒤에 있는 큰 수 찾기 - 154539문제 링크성능 요약메모리: 206 MB, 시간: 259.36 ms  🤔접근법주어진 정수 배열을 순회하면서 본인보다 오른쪽에 있는 수들 중에서 본인보다 크지만 가장 가까이 있는 수 찾기범위 체크 및 시간복잡도 예상1 ≤ N ≤ 1,000,000O($NlogN$) 보다 더 작아야 한다. 풀이법❌ 접근 방법. 완탐주어진 정수 배열을 인덱스 0 ~ N 까지 반복가르키는 정수로부터 오른쪽에 존재하는 모든 정수를 탐색만약 본인보다 큰 정수가 나오면 answer에 저장하고 정지➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$ → 시간 초과 ⭕ 접근 방법. stack을 사용하자 !스택에는 정수배열의 인덱스와 값을 넣는다.스택은 top 보다 값이 작을때만.. 2024. 7. 22.
[알고리즘 정리] Merge Sort ( 병합정렬 ) - O(NlogN), 추가메모리, Stable 🤔Merge Sort(병합정렬) 이란 ? 병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘 💡 과정 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할) → mergeSort() 메소드 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다. → if (start == end) return; 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복) → merge() 메소드 ⚡ 특징 시간 복잡도 : 최선, 평균, 최악 모두 $O(NlogN)$ 데이터를 “비교”하면서 찾기 때문에 비교정렬 추가 메모리 필요 .. 2024. 1. 20.
[백준 Java] 3020번 개똥벌레 💡문제 [Gold V] 개똥벌레 - 3020 문제 링크 성능 요약 메모리: 29804 KB, 시간: 252 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 $O(\sqrt {NH}$ 또는 $O(N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 H개의 높이에 대해서 N개의 장애물에 대해 탐색하며 몇개의 장애물을 통과해야할지 판별→ $O(NH)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(NH)$ 당연히 시간복잡도 초과 ❌ 접근 방법. 완탐 높이 H를 인덱스로 가지는 배열을 생성 장애물을 차례대로 탐색하며 높이에 장애물이 존재하는 높이에 업데이트 → $O(NH)$ 길이가 2인 석순이라면 높이 1에 +1, 높이 2에 +1 길.. 2024. 1. 13.
[백준 Java] 2143번 두 배열의 합 💡문제 [Gold III] 두 배열의 합 - 2143 문제 링크 성능 요약 메모리: 112696 KB, 시간: 556 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 -1,000,000,000 ≤ T ≤ 1,000,000,000 (십억) 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 1,000 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수 $O(\sqrt T)$ 또는 $O(n^2)$이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 배열 A의 가능한 부분 배열 만들기 → $O(N^2)$ 배열 B의 부분합이 T-(배열 A의 부분합)인 모든 부 배열 찾기 → $O(N^2)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(N^4)$ 당연히 시간복잡도 초과 ⭕ 접근 방법. Map을 이용해 누.. 2024. 1. 13.
[백준 Java] 2015번 수들의 합 4 [Silver II] 수들의 합 4 - 2015 문제 링크 성능 요약 메모리: 35852 KB, 시간: 312 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ N ≤ 200,000 |K| ≤ 2,000,000,000 (20억) $O(N\sqrt N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 시작점이 0 ~ N-1 , 끝점이 0 ~ N-1로 두고 가능한 모든 부분 배열을 지정한다. → $O(N^2)$ 부분 배열을 순회하며 부분합을 구한다. → $O(N)$ 부분합이 k와 같은지 비교한다. ➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$ 시간복잡도가 너무 커서 시간이 부족하다. ❌ 접근 방법. 누적합 누적합 배열($S_n)$을 만든다. → $O(N)$ $S_b-S_{.. 2024. 1. 12.
[백준 Java] 2004번 조합 0의 개수(정수론) ## 💡문제 ### [Silver II] 조합 0의 개수 - 2004 [문제 링크](https://www.acmicpc.net/problem/2004) #### 성능 요약 메모리: 11564 KB, 시간: 76 ms --- #### [깨진 부분은 여기에서 확인](https://velog.io/@dksek3050/%EB%B0%B1%EC%A4%80-Java-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98%EC%A0%95%EC%88%98%EB%A1%A0) ## 🤔접근법 ### 범위 체크 및 시간복잡도 예상 - 0 ≤ m ≤ n ≤ 2,000,000,000 (20억) n ≠ 0 - $O(\sqrt N)$ 또는 $O(logN)$ 이어야 한다. ###.. 2024. 1. 9.
반응형

티스토리툴바