Toy Problem (4) 썸네일형 리스트형 LPS : Longest Prefix which is also Suffix 문제 : 문자열을 입력 받아 다음의 조건을 만족하는 LPS를 찾아 그 길이를 리턴한다. 조건: non-overlapping. 즉, 접두어와 접미어는 서로 겹치는 부분이 없어야 한다. 참고: prefix(접두어)는 문자열의 첫 인덱스부터 시작하는 모든 부분 문자열을 의미한다. suffix(접미어)는 문자열의 마지막 인덱스부터 시작하는 모든 부분 문자열을 의미한다. pseudocode 1. prefix이자 suffix인 것 중 가장 긴 부분 문자열을 구하면서 서로 겹치지 않으려면 - prefix는 최대 문자열 길이의 1/2지점까지이며 - suffix는 문자열 길이의 1/2 지점부터 끝까지가 되어야 한다. (str의 길이가 홀수인 경우 prefix가 더 길다.) abaab를 예로 들면 prefix === { .. Balanced Brackets 관련 : stack 자료 구조 문제 문자열을 입력 받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 한다. Pseudocode str[i]가 opener이면 stack 에 넣고 str[i]가 closer이면 1. stack에서 마지막 요소를 제거하고 이를 top이라고 한다. 2. top과 str[i]가 짝이 맞으면 true를 반환한다. 즉, stack에 쌓이는 것은 opener이고, str[i]가 closer일 때에는 이 closer가 stack에 가장 마지막에 넣은 요소와 짝이 맞는지 확인한다. 결과적으로 stack에 아무것도 남지 않게 되면 결과는 true이다. 코드 구현 const balancedBrackets = function(str) { let stack = []; let opener.. Quick Sort 오랜만에 알고리즘 문제를 풀게 되어서 기쁘게 생각한다. 꾸준히 해야하는데 생각보다 쉽지 않다. Quick Sort 란 Charles Antony Richard Hoare 가 고안한 정렬 알고리즘이다. 퀵 정렬은 최악의 경우엔 O(n^2)의 시간복잡도를 가지지만 평균적으로 매우 빠른 수행 시간(O(n log n)을 자랑한다. 매 단계에서 적어도 1개의 원소가 자기 자리를 찾기 때문에 이후 정렬 갯수가 줄어든다. 이 때문에 퀵 정렬은 다른 O 알고리즘에 비해 훨씬 빠르게 동작한다. => quick sort 라는 이름의 기원!! 원소들 중 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기와는 달라질 수 있어 불안전 정렬에 속한다. 알고리즘 : divide and conquer 분할 정복을 통해 리스트를.. Bubble Sort Bubble Sort 바로 옆에 있는 요소와 비교해서 자리를 바꾸면서 정렬 바로 옆에 있는 요소와 비교한 후 자리를 바꾸는 방식으로 정렬한다. 큰 수를 뒤로 보내다보니 큰 수가 먼저 가장 마지막에 자리를 잡는다. 즉, 매번 반복할 때마다 i만큼의 수가 뒤에서부터 자리잡으니까 i개는 더이상 계산할 필요가 없다. 시간 복잡도 O(n^2) 구현하기 let bubbleSort = function(arr){ /* arr = [2,1,3] 2,1 비교 : 2가 1보다 크니까 1,2 로 자리를 바꾼다. 2,3 비교 : 2가 3보다 작으니까 자리 바꾸지 않는다. */ let swap for(let i = 0; i < arr.length-1; i++){ for(let j = 0; j < arr.length-1-i; j+.. 이전 1 다음