CS지식/알고리즘
-
검색 알고리즘1- 선형검색, 이진검색CS지식/알고리즘 2024. 9. 10. 11:59
검색 알고리즘경우1) 문자열이 있는데 해당 문자열에 포함된 다른 문자열이 있는지 확인을 하는 경우 경우2) 웹 사이트에 사람들이 가입하고 사용자명을 추가할 수 있게 해서, 사람들이 사용자명(username)과 비밀번호를 입력하고 회원가입 하게는 경우 username이 이미 사용중인 것인지 알려주어야 한다.let username = [ "Sadye", "Willette", "Nikolos", "Noel", "Sascha", "Brunhilda", "Evie", "Evered", "Kennie", "Ashlan", "Sophia", "Cecilio", "Josselyn", "Florrie", "Angela", "Ragnar","Robert", "Ennis", "Ephrayim" ] 데이터베이스가 없다고 가정..
-
알고리즘 (정렬) - 고급 정렬 알고리즘(Quick Sort)2CS지식/알고리즘 2024. 1. 2. 16:41
고급 정렬 알고리즘 퀵 정렬(Quick Sort) 퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰는 정렬 알고리즘이다. 우선 [그림 4-6]을 예로 들어 설명을 시작한다. 첫째 줄에 정렬해야 할 원소가 10개인 배열이 주어졌다. 아무원소나 기준 원소로 삼아도 상관이 없는데 여기서는 맨 오른ㅉ고에 있는 원소 15를 기준 원소로 삼는다. (a)에서는 기준원소인 15를 중심으로 이보다 작은 원소들은 15의 왼쪽에, 나머지 원소들은 15의 오른쪽에 재배치한다. 이 결과 8,11,3은 왼쪽에, 31,48,20,29,65,73은 15의 오른쪽에 오도록 재배치되었다. (b)에서 왼쪽의 원소 3개와 오른쪽의 원소 6개를 각각 독립적으로 정렬한다. 왼쪽3개의 원소를 정렬할 때 15의 자리는 영향을 받..
-
알고리즘 (정렬) - 고급 정렬 알고리즘(Merge Sort)1CS지식/알고리즘 2024. 1. 2. 11:27
고급 정렬 알고리즘 선택정렬, 버블정렬, 삽입정렬 과 같은 기본 알고리즘은 모두 평균 ϴ(n²)의 시간이 소요된다. 하지만 앞으로 게시물에서 다룰 고급 정렬 알고리즘은 모두 평균 ϴ(n log n)의 시간이 소요된다. 병합 정렬, 퀵 정렬, 힙 정렬을 소개하는데 회악의 경우에도 병합 정령과 힙정렬은 ϴ(nlogn)이 소요되고, 퀵 정렬 ϴ(n²)이 소요된다. 이 중 퀵 정렬은 최악의 경우 때문에 성능이 가장 나빠 보일 수도 있으나 평균 성능은 어떤 정렬에도 뒤 떠러지지 않아 실무에서 가장 많이 사용된다. 병합 정렬(Merge Sort) 병합 정렬은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다...
-
알고리즘 (정렬) - 기본적인 정렬 알고리즘(Bubble Sort,Insert Sort)CS지식/알고리즘 2023. 12. 29. 10:15
알고리즘 1. 버블 정렬(Bubble sort) 버블 정렬도 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. 알고리즘 4-2 버블정렬 public int [] bubbleSort(int []A){ int temp = 0; int n = A.length; for(int i = 0; i A[j] ){ temp = A[j-1]; A[j-1] = A[j]; A[j] = temp; } if(j == n-1) n--; } } return A; } 알고리즘은 크게 두 개의 for 루프로 구성이 되어 있다. 첫 번째 for루프, 즉 1️⃣..