목록자료구조&알고리즘 (3)

망각에 재주 있는 나를 위해 기록하는 곳.

정렬(sorting)

아래의 사이트와 영상을 보면 알겠지만 상황마다 어떤 정렬이 더 좋은지 대략적으로 알 수 있다. 무조건 좋은 정렬이 있는건 아니다. 근데 선택 정렬은 쓰레기인듯...? 몇가지 대표적인 정렬 방법 별로 비교한 사이트 및 유튜브 https://www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com https://www.youtube.com/watch?v=kPRA0W1kECg
자료구조&알고리즘 2023. 4. 10. 22:54
나이브 문자열 검색(Naive String Search)

같은 패턴의 문자열을 검색하는 단순한 방법. 예를 들어, "moghohoi pqoiwhoimq" 라는 (아무거나쓴거) 문자열이 있을때 "hoi"라는 같은 패턴의 문자열을 찾는 것이다. Naive String Search Pseudocode: 긴문자열을 반복하는 루프 작성. (long) 찾을 패턴인 문자열을 반복하는 루프 작성.(short) 패턴의 문자열의 길이는 대상 긴문자열 보다 짧거나 같아야한다. 더 길 수 없다. 루프안에서 문자열이 일치하지 않으면 break한다. 일치하는 문자열이 있다면 패턴 문자열이 다 맞는지 계속 검색 진행. 패턴과 일치하는 문자열을 찾으면 count를 +1하고 검색을 마치면 return. function naiveSearch(long, short){ var count = 0;..
자료구조&알고리즘 2023. 4. 10. 22:08
이진검색(Binary Search)

이진검색은 정렬된 배열을 대상으로 작동함. divide and conquer : 중간점 기준으로 찾는 값이 오른쪽, 왼쪽 어디에 있는지 찾는다. 찾는 값이 포함되지 않는 부분은 버림. 이런 방식으로 범위를 좁혀가며 원하는 값을 찾는다. (해당 배열은 정렬되어 있어야 한다.) Binary Search Pseudocode: 시작점(start)과 끝점(end)을 설정한다. 중간점(middle)을 찾는 코드를 만든다. num이 배열의 중간점과 같지 않고 시작점이 끝점보다 작을 경우에 아래의 과정을 반복한다. 만약 num이 중간점 보다 작을 경우, 끝점을 중간점-1로 변경한다. 만약 num이 중간점 보다 클 경우, 시작점을 중간점+1로 변경한다. 중간점은 반복적으로 갱신한다. 마지막으로 중간점이 찾는값과 같을 경..
자료구조&알고리즘 2023. 4. 10. 21:14
이전 Prev 1 Next 다음