Youngble_개발스토리

재귀란? 자신의 함수에서 자기자신을 호출하는 것 재귀함수를 사용하는 이유 모든 곳에서 재귀함수를 사용하고 있다. 예로 간략한 리스트는 다음과 같다. - JSON.parse - JSON.stringify - document.getEementById - DOM traversal algorithm(DOM 순회 알고리즘) - data structures - cleaner alternative to iteration DOM traversal algorithm(DOM 순회 알고리즘) DOM의 모든요소가 중첩된 트리 구조로 되어있기 때문에 만약 div 태그안에 div가 들어있고 이러한 중첩 계층이 100개나 될때 그것을 살펴보고자 할때 흔한 접근법 중 하나가 재귀적으로 코드를 작성하는 것이다. Data structu..

분할정복이란? 알고리즘 디자인 패러다임 중 하나이다. 정의 : 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법 분할정복 핵심 진행방식 ① 분할 : 동일한 타입의 하위 문제로 큰 문제를 분할한다. ② 정복 : 재귀적으로 하위 문제들을 해결한다. ③ 병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결한다. 분할정복 종류 이진탐색, 퀵정렬, 병합(합병)정렬 이글에서는 이전 알고리즘&자료구조 글로 썼던 이진탐색의 예시로 진행한다. 선형탐색/순차탐색(Linear search, Sequential Search) function search(arr, val..

슬라이딩 윈도우란? 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘 여기서 말하는 윈도우와 슬라이딩은 창문 틀에서 창문이 슬라이딩 하는 것 같은 알고리즘이라는 뜻 프로그램을 작성할때나 코딩테스트에서 리스트를 활용하는 경우는 굉장히 많다. 일반적으로 인덱스를 처음부터 끝까지 완전 탐색을 하게 되는데, 완전 탐색을 할 경우 효율성이 좋지 않을 때 활용할 수 있는 알고리즘 3가지는 다음과 같다. Two Pointer Sliding Window Prefix Sum 문제설명 주어진 Array에서 주어진 number 만큼의 연속되게 붙어있는 값들을 더했을때 가장 큰 값 max를 구해야한다. 예를들어 maxSubarraySum([2,6,9,2,1,8,5,6,3],3) 라는..

문제 해결 패턴 중 Frequency Counter 패턴(빈도카운터)과 Multiple Pointers 패턴(다중포인터)을 공부하였다. 빈도카운터 정확한 공식적인 이름이 있는게 아니지만 문제 해결할때 많이 등장하고 Colt Steele은 이를 frequencty counter 라고 정의하여 사용하기 때문에 이렇게 외우기로 했다. Frequency Counter Pattern, 빈도 카운터 패턴 빈도카운터패턴은 애너그램 anagram과 같은 문제나, 두 배열이나 문자 string값을 비교하여 배열의 값들이 다른 한쪽의 배열의 제곱인지 체크하는 등에서 사용하는데 자바스크립트 객체의 속성접근을 이용하여 있는지 확인후 없다면 +1 있다면 있는 값의 +1 해주는 식으로 만들고 비교할때 하나씩 지우는 방식이다. 말..

스택이란? 한쪽 끝으로만 넣고 뺄수 있는 자료구조 예를들어 빨래통이 있다고 한다면 빨래를 빨래통에 차례대로 넣고나서 세탁기에 넣을때 처음에 넣은 맨아래 빨래가 아닌 마지막에 넣은 빨래부터 아래로 세탁기에 넣는다. → 이러한 자료구조를 Last In First Out 이라고 해서 LIFO 자료구조 라고한다. 왜필요한가? 넣은 순서를 쌓아두고 있고 그 순서가 필요한 경우가 있다. 예를들어 컴퓨터의 되돌리기(Ctrl+Z) 기능의 경우 직전 행동으로 되돌리고 싶을때 사용하는 기능인데 이를위해서 행동들의 순서대로 기억해야하고 마지막 행동부터 처리해야하기때문에 이러한 스택을 사용한다. 스택구현 스택 이라는 자료구조에서 제공하는 기능 push(data): 맨위(뒤)에 데이터 넣기 pop(): 맨위의 데이터뽑기 pee..

정렬 버블정렬 요소들이 마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고하여 버블정렬이라고 부른다. 배열첫인덱스부터 끝인덱스까지 순차적으로 비교해가면서 순회하는 반복문을 사용 끝인덱스에 가장 큰수를 넣었다면 다시 처음부터 끝에 넣은 큰수 인덱스제외 비교해가며 순회한다. 시간복잡도는 O(N^2) 선택정렬(Selection Sort) 인덱스 0부터 배열의 길이만큼의 값을 비교하여 전체중 최소값의 인덱스를 기억하고 그것을 순차적으로 왼쪽부터 정렬하는것 시간복잡도는 O(N^2) 삽입정렬(Insertion Sort) 전체에서 필요할때만 하나씩 올바른 위치에 “삽입"하는 방식 인덱스0 부터 차례로 정렬을 하기때문에 만약 그다음 for문에 해당하는 인덱스값이 그 앞 인덱스에 해당하는 값과 비교하여 더 크다면 ..

이진탐색(이분탐색) binary search 업다운 게임 전체범위의 딱 절반으로 탐색 총 배열의 길이가 N이라고 할때 그 절반을 탐색하므로 N/2 그다음 N/2/2 이므로 N/(2^2).... 가면 N/2^k 가 되고 이렇게 무한히 반복하다보면 1개만 남았을때를 가정하면 N/2^k = 1이 여야 하므로 k = log N 이된다. 즉 시간복잡도는 O(log N) 이라고 할수있다. 만약 배열이 정렬이 되어있지않다면 이진탐색이 되지않는다. 이럴때 정렬을 이용하여야한다. 재귀함수 자신의 함수안에서 다시한번 자신의 함수를 호출한다. 예를들어 60에서 0까지 카운트하는 함수를 만들때 위와같이 재귀함수를 쓴다. 팩토리얼 3! = 321 4! = 4321=43! 즉, Factorial(n)=n*Factorial(n-1..

자료구조 특정 자료구조는 삽입/삭제가 빠르고, 특정 자료구조는 조회가 빠르다. 이렇게 어떤 경우에 이 자료가 좋고, 어떤 경우는 저 자료가 좋은 것 처럼 경우에 따라 다양한 자료구조와 알고리즘을 사용해야한다. 비유 못을 박을때는 망치가 필요, 나사를 뺄 때는 뺀치가 필요한것처럼, 다양한 공구들의 사용법을 배우는것이다. Array 순차적으로 데이터를 저장 배열은 크기가 정해진 데이터의 공간. 한번 정해지면 바꿀수 없다. ->원소를 새로 추가하려면, 새로운 공간을 할당을 해야하기때문에 매우 비효율적 자료구조 index를 통해 원소에 즉시 접근할수있다. Ex rooms[3] -> 즉시 접근 가능하다는것은 상수 시간내에 접근할수있으므로 O(1)내에 접근 할수있다고 말한다. 배열은 원소를 중간에 삽입/삭제 하려면..

시간복잡도 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계 중첩for문시 N^2의 수식을 가짐 따라서 중첩문이 생기면 시간이 기하급수적으로 늘어난다는것 참고 공간복잡도 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계 Array 길이, 값을 넣어줄 각 변수들을 계산하여 카운트, 단 재할당하는 중복되는 변수의 공간은 카운트하지않는다. ->만약 공간복잡도가 그저 숫사상수로 29,30 이라면 공간복잡도 보단 시간복잡도로 비교하여 알고리즘의 효율성을 생각한다.따라서 시간복잡도를 더 신경써야한다. 보통 시간복잡도의 효율성을 비교할때 예를들어 3N+106 이라는 시간이 걸린다면 상수 106은 비교대상에서 제외하고 3N 부분만 계산한다 N에 따라 걸리는시간이 무한대로 커지기때문에 106은 비교대상에 넣지 않는것..

https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 내가푼방식 function solution(m, musicinfos) { var answer=[]; var numb=[]; for(var i=0; i< musicinfos.length; i++){ var b= musicinfos[i].split(","); var totalmusicplay=0; var end= (b[1].substr(0,2)/1)*6..