fine
2022.03.09
@fine님이 새 포스트를 작성했습니다.
<탐색>
[탐색 알고리즘] 탐색 알고리즘의 종류 선형 탐색 알고리즘 이진 탐색 알고리즘 해시 탐색 알고리즘 📌 선형 탐색 데이터의 처음부터 끝까지 하나하나 확인하는 방식 가장 간단한 알고리즘 ex) 반복문을 사용해 값을 찾을 때 사용하는 알고리즘 배열의 첫 요소부터 하나하나 검사 -> 원하는 값이 마지막에 존재하면 배열의 크기와 동일한 연산 횟수가 필요 -> 최악의 시간 복잡도 : O(n) 📌 이진 탐색 (이분 탐색) 배열을 반으로 나누어서 원하는 값을 찾는 방식 (조건) : 배열의 데이터가 정렬이 되어있어야 한다. <배열의 중간 값을 확인, 목표 값과 비교> 중앙 값이 목표 값보다 작으면 우측을 탐색 대상으로, 중앙 값이 목표 값보다 크면 좌측을 탐색 대상으로 지정한다.
fine
2022.03.08
@fine님이 새 포스트를 작성했습니다.
<코딩테스트 - Level 1> 2일차
1️⃣ int a = 0, b = 0; for (i = 1; i < N; i++) { a = a + i } for (j = 2; j < M; j++) { b = b + j } 첫 번째 반복문과 두 번째 반복문은 각각 O(n)의 시간 복잡도를 가진다. 따라서 O(N+M) 이지만 , Big-O 표기법에 따라 상수항은 일반화하여 O(n)의 시간 복잡도를 가지게 된다. 2️⃣ a = 0, b = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { a = a + j; } } for (k = 0; k < N; k++) { b = b + k; } 첫 번째 반복문은 이중 반복문을 사용했기 때문에 O(n^2) 두 번째 반복문은 1번 문제랑 같은 O(n) Big-O 표기법에 따라 최악의 수행시간을 고려해서 첫 번째 반복문의 시간 복잡도인 O(n^2)가 답이 된다.