본문 바로가기

프로그래밍/알고리즘

 (9)
[알고리즘] Sliding Window 슬라이딩 윈도우 배열이나 문자열같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 것에 유용함! 규모가 큰 데이터셋에서 데이터의 하위 집합을 추적하는 문제에 매우 유용함 흠 넵 우선 예시로 풀어볼 문제는 첫번째 인자값으로 배열이 들어오며, 두번째 인자값은 number로 배열의 각각의 num만큼의 배열 합계중 가장 큰 합을 구하는 문제 maxSumArrSum([1, 2, 5, 2, 8, 1, 5], 2) -- 10 ( 1+2 , 2+5, 5+2, 2+8, 8+1, 1+5 중에서 가장 큰 합) maxSumArrSum([], 4) -- null maxSumArrSum([4, 2, 1, 6], 1) -- 6 function test (arr, num){ let maxNum =..
[알고리즘] Two Pointers 투포인터 (Two Pointers) 두개의 포인터로 정돈되어있는 배열에서 원하는 값을 찾을 때 사용하면 좋은 알고리즘 그냥 반복문을 쓰다보면 시간 초과가 걸리는 경우가에 있는데, 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있습니다. 코딩 테스트를 보면 시간 복잡도를 낮출 수 있는 경우에는 일부로 테스트 케이스에 n이 정말 큰 (엄청 긴 배열이나 문자열)을 사용해서 Time out을 걸리게 하는 케이스가 많다고... 우선 아래의 문제를 제가 일반적으로 풀수있는 방법으로 풀어보았고 그 밑에 투포인터 방식으로 풀이된 문제입니다. 주어진 배열에서 중복된 값을 제거한 특수한 값이 몇개인지 리턴하는 문제! countUniqueValues([1, 1, 1, 2, 1]) --> 2 countUniqueVal..
[알고리즘] Frequency Counter Pattern 강의를 들으면서 먼저 강의시작전에 풀어보는 문제로 아래의 예시와 같이 순서와 상관없이 해당 문자가 포함되어 있으면 true 하지만 여기서 빈도수는 첫번째 문자열과 동일해야함 validAnagram('', '') --> true validAnagram('cat', 'atc') --> true validAnagram('love', 'lovve') --> false 그래서 저는 우선 받아온 문자를 배열로 만들고 두 배열의 길이가 다르다면 제일 먼저 return false를 해주고, for문으로 구하기로 생각했습니다. // validAnagram('', '') true // validAnagram('cat', 'atc') true // validAnagram('love', 'lovve') false functi..
[알고리즘] 배열의 시간복잡도 *강의를 보고 정리한 노트입니다. 배열에 있는 데이터의 접근은 매우매우 빠른데 아래와 같이 각각의 역할에 따라 빅오가 달라진다. 접근 - O(1) 배열의 접근은 인덱스를 사용하여 매우매우 빠르게 접근이 가능함 입력 - 배열끝에 추가하면 O(1)이지만, 배열 앞에 추가 및 삭제를 하게 되면 배열의 모든 인덱스를 새롭게 배정해주어야 하기 때문에 O(n) 탐색 - O(n) 배열의 모든 인덱스를 거쳐서 탐색을 해야하기 때문 배열 메소드의 빅오 push / pop : O(1) - 배열의 맨끝에 추가하고 제거하는 작업은 배열의 크기와 상관이 없고 그냥 끝에 넣거나 삭제해주기만 하면 끝! shift / unshift : O(n) - 배열 시작에 추가하고 제거를 한다면 무조건! 인덱스를 재정의하게 됨 concat : ..
[알고리즘] 빅오표기법 - 1 *강의를 보고 정리한 노트입니다. 알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, 빅 오 표기법은 시간 복잡도를 다룬다. 하나의 문제를 해결하기 위한 해결법은 무수히 존재하고 다양한데, 그 중에서 가장 좋은 방법으로 해결할 수 있는 하나의 방법은 무엇일까? 예를 들어보자면, 문제를 접근하는 두가지 방식의 예시가 있습니다. 첫번째는 루프, 두번째는 리스트로 문제를 해결할 수 있다고 가정해봅니다. 루프와 리스트 둘 중에서 과연 뭐가 더 좋은 선택일까? 바로 이것이 빅오표기법의 궁극적인 목표입니다. 즉, 여라가지 코드를 일반적으로 서로 비교하고 성능을 평가하는 방법. 근데, 제대로 동작하기만 하면되는데 왜 제일 좋은 해결책을 찾는걸까? 그것은 바로, 수천개, 혹은 아주 큰 ..
[프로그래머스] 자바스크립트 코테 연습 - 4 (feat.reduce함수) 안녕하세요 (*•̀ᴗ•́*)و ̑̑ 오늘도 프로그래머스에서 문제를 하나 풀어보았습니다.. 쉬운 문제부터 차근차근 풀어보는게 부담이 덜하기도 하네요ㅎㅎ! 그래서 오늘 풀어본 문제는요! [음양더하기] 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 return 하도록 solution 함수를 완성해주세요. [제한사항] absolutes의 길이는 1 이상 1,000 이하입니다. absolutes의 모든 수는 각각 1 이상 1,000 이하입니다. signs의 길이는 absolutes의 길이와 같습니다. signs[i] 가 참이면 absolutes[i] 의 실제 정..
[프로그래머스] 자바스크립트 코테 연습 - 3 (feat.reduce함수) 정말... edabit 영어가 눈에 안들어오더라구여.... 그래서 프로그래머스에서 레벨1에 있는 문제 풀어보았습니다. 아마 오늘도 for문과 함께할거같쥬? 넹 오늘은 문제는 [ 없는 숫자 더하기😌 ] 0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. [ 제한사항 ] 1 ≤ numbers의 길이 ≤ 9 0 ≤ numbers의 모든 원소 ≤ 9 numbers의 모든 원소는 서로 다릅니다. [ 입력예시 ] [1,2,3,4,6,7,8,0] ---> 14 [5,8,4,0,6,7,9] ---> 6 제가 작성해본 코드는여 function sol..
[edabit] 자바스크립트 코테 연습 - 2 (feat.filter함수) Learn to Code with 10,000+ Interactive Challenges Learn to code with fun, bite-sized challenges. Earn XP, unlock achievements and level up. It's like Duolingo for learning to code. edabit.com Q. How Much is True? Create a function which returns the number of true values there are in an array. countTrue([true, false, false, true, false]) ➞ 2 countTrue([false, false, false, false]) ➞ 0 countTrue([..

티스토리툴바