본문 바로가기

IT 정보/Java42

[Java] 탐색 알고리즘!? (Search Algorithm) 방대한 정보 속에서 원하는 정보를 찾기 위해 우리는 정렬을 하고 검색을 한다. 그 과정이 바로 정렬 알고리즘과 탐색 알고리즘이다. 탐색 알고리즘의 종류 선형 탐색 알고리즘 ( Linear Search Algorithm ) 이진 탐색 알고리즘 ( Binary Search Algorithm ) 해시 탐색 알고리즘 ( Hash Search Algorithm ) 선형 탐색 알고리즘 : 데이터가 정렬 된 상태에서 절반씩 범위를 나눠 분할 정복 기법으로 특정한 값을 찾아내는 알고리즘 정렬된 배열의 가장 중간 인덱스 설정 if ( 찾는 값 == 중간 인덱스 ) return 인덱스 값 else 3번으로 이동 if ( 찾는 값 > 중간 인덱스 ) or ( 찾는 값 < 중간 인덱스 ) 비교 찾는 값이 있는 영역과 없는 영.. 2022. 5. 31.
[Java] 완전 탐색 알고리즘 (Brute-Force Algorithm) Brute-Force !? 컴퓨터 과학에서 시행착오 방법론이라고 말하고, 암호학에서도 사용한다. 이는 어떤 암호를 풀기 위해 모든 값을 대입해서 찾아내는 방법으로 지능적인 전략을 사용하지 않는다. 예를 들어 0000 ~ 9999 자물쇠가 있다면 모든 수를 대입해보는 방식인 것이다. Brute Force Algorithm ?! 의미 위 뜻과 마찬가지로 무차별 적인 대입하는 방법으로 모든 가능성을 시도하는 것이다. 따라서 공간 복잡도와 시간 복잡도를 전혀 고려하지 않은 방법이다. 때문에 최적의 솔루션이 될 수 없다. 사용 조건 프로세스 속도를 높이는 데 사용할 다른 방법이 없을 경우 문제를 해결할 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 주요 활용 알고리즘 순차 검색 알고리즘 (Sequential S.. 2022. 5. 31.
[Java] 탐욕 알고리즘 (Greedy) Greed Algorithm(탐욕 알고리즘)은 선택의 순간마다 최적의 상황을 찾고, 해답에 도달하는 방법이다. 선택절차 :(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택 적절성 검사 (Feasibility Check) : 해답이 문제의 조건을 만족하는지 검사 그렇지 않다면 선택절차로 복귀 해답 검사 (Solution Check) : 원래의 문제가 해결됬는지 검사하고, 그렇지 않다면 선택절차로 복귀 탐욕 알고리즘이 필요한 상황 탐욕적 선택 속성( Greedy Choice Property ) : 앞의 선택이 이후의 선택에 영향을 주지 않을 때 최적 부분 구조 ( Optimal Substructure ) : 최종 해결 방법은 각 부분적의 문제들의 해결방법으로 구성 마시멜로 실험 .. 2022. 5. 30.
[Java] 시간 복잡도 (Time Complexity) 위 이미지는 시간복잡도를 나타낸 이미지다. 시간복잡도는 알고리즘 로직을 코드로 구현할 때 입력값에 따라 요구되는 시간을 나타낸 것이다. 그리고 이것을 표현하기 위해 표기법이 존재하는 데 이것을 Big-O 표기법이라고 한다. Big-O : 최악의 경우 Big-Ω : 최선의 경우 Big-θ(빅-세타) : 평균의 경우 프로그램의 상태 상황에 따라 편차가 존재할 수 있는데, 이때 최악의 경우를 가정해서 시간을 계산함으로써 최악의 상황을 피하기 위함이다. Big-O 표기법 O(1) : 데이터와 관계없이 일정한 시간이 소요됨 O(log n) : 데이터가 많아 질 수록 시간이 증가되지만 BTS처럼 노드 이동시마다 절반씩 줄어들어 줄어듦 O(n) : 데이터가 많아질수록 linear 하게 증가 ( 비례하여 증가 ) O(.. 2022. 5. 30.

티스토리툴바