유미의 기록들

이분탐색 (Binary Search)오름차순으로 정렬되어 있는 리스트에서 같은 크기의 두 부분으로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 데이터를 찾는 알고리즘 1. 정렬된 배열의 중간요소와 어떠한 대상 값을 비교한다2. 그 요소가 아닌 경우 절반을 제거하고 나머지 절반에서 검색을 반복한다    2-1. 그 요소가 중간요소보다 작을 경우, 왼쪽으로 다시 탐색    2-2. 그 요소가 중간요소보다 클 경우, 오른쪽으로 다시 탐색  이렇게 정렬된 배열에서 중간값이 어떠한 대상 값보다 큰지, 작은지 비교하고 탐색 범위를 반으로 나누기 때문에 시간복잡도는 logN이다.   v배열에서 찾는 값이 n일때 코드이다while(l n) r = mid - 1; else if(v[mid] == n) r..

그리디 알고리즘 (탐욕법, Greedy Algorithm) 각 단계에서 최적이라고 생각하는 것인 지역적 최적해가 궁극적으로 전역최적해가 되는 것즉, 여러 경우 중 선택의 순간마다 최적이라고 생각하는 것을 선택해나가면서 최종적인 해답에 도달하는 알고리즘 ⚠️</s..

이진수 우리가 평소에 사용하는 0~9의 수는 십진법이다 각각의 자리는 0 ~ 9 로 10개의 숫자로 표현된다 컴퓨터는 내부적으로 모든 자료를 0과 1로 표현하는 이진법으로 표현한다 10진수 21을 2진수로 표현해보면 10101 으로 표현한다 각각의 자리는 비트라고 하며 Binary Digit의 약어로 이진수와 같은 개념인 것을 알 수 있다 비트 연산자 비트끼리 연산을 할 수 있는 연산자가 있다 비트 연산자 활용법 1. idx 번째 비트 끄기 S & = ~ (1

완전탐색 (Brute Force) 모든 경우의 수를 탐색하는 알고리즘 '노가다'라고 흔히 비유되는 이 방법은, 주어진 문제의 모든 가능성을 탐색하여 정답을 찾아내는 알고리즘 접근방식이다 흔히 사용하는 DFS, BFS도 완전탐색에 해당한다 ⚠️ 고려사항 완전탐색을 사용할 때 주의할 점은, 처리해야 할 데이터의 양이 너무 많지 않아야 한다. 보통 시간 복잡도 1억 미만으로 볼 수 있다. 📌 구현 방법 1) for / while를 이용 2) 재귀함수 이용 재귀함수를 활용하면 복잡하고 비용이 들기 때문에 반복문으로 해결이 가능하다면 가능한, 반복문으로 구현하는 것이 좋다 단, 매개변수의 수정만 필요한 반복적인 행위가 요구된다면, 재귀함수를 이용하는 것이 더 적합하다 - 조합이나 순열 - DFS, BFS 알고리즘..

그래프를 탐색하는 방법에는 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있다 그래프를 탐색하는 것은 하나의 정점으로 시작해서 모든 정점을 한 번씩 방문하는 것, 즉 방문한 정점은 다시 방문하지 않는다 깊이 우선 탐색 (DFS, Depth First Serch) DFS는 어떤 정점부터 시작해서 다음 분기(branch)로 넘어가기 전에 각 분기마다 가능한 가장 멀리 있는 정점까지 탐색하는 알고리즘 - 모든 정점을 방문하고자 하는 경우에 많이 사용한다 - 스택 또는 재귀함수로 구현한다 너비 우선 탐색 (BFS, Breadth First Search) BFS는 어떤 정점부터 시작해서 다음 깊이의 정점로 이동하기 전에 현재 깊이의 모든 정점을 탐색하는 알고리즘 즉, 레벨 별로 탐색한다는 의미이다 - 최단 거리를..

알고리즘 문제를 풀 때 예제 입출력이 맞게 나와도 실제 코드를 제출했을 때 시간초과로 통과하지 못하는 경우가 종종 있다. 우리가 작성한 코드의 실행 시간을 어떻게 알 수 있을까? 이러한 시간은 사용된 언어 종류, 컴퓨터 사양, 컴파일러 속도 등 여러가지 영향을 받게 된다. 따라서 시간복잡도를 설명할 때는 입력값과 연산 수행 시간의 상관관계를 중점으로 설명한다 시간복잡도 (time complexity) 입력크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간, 주요로직의 반복 횟수를 중점으로 측정됨 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 시간복잡도 표현방법은 3가지가 있다 1) 오메가 표기법 (Big-Ω) : 최상의 경우 2) 세타 표기법 (Big-θ) : 평균의 경우 3) 빅오 ..