jyoon dev log

Memoization으로 중복 연산을 방지하며, 작은 부분 문제로 큰 문제를 해결 하며 해를 도출하는 알고리즘 설계 기법. 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 동적 계획법 특징 부분 문제는 중복되며, 상뮈 문제 해결 시 재사용한다. Memoization 기법을 사용한다( 동일한 계산을 반복할 때, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 따라서 이전에 계산한 값을 메모리에 저장하여 중복 연산 방지함) 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (O..

🌼 시간복잡도 알고리즘의 로직을 코드로 구현할 때, 시간복잡도를 고려한다는 것은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'라는 말이다. 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는 것이다. 시간 복잡도는 Big-o 표기법을 사용해 나타낸다. 🌼 Big-o 표기법 시간복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 (최악의 경우) Big-Ω(빅-오메가) ⇒ 하한 점근 (최선의 경우) Big-θ(빅-세타) ⇒ 그 둘의 평균 (평균의 경우) 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 이 중에서 Big-O 표기법이 가장 자주 사용되며..

정렬(sorting) 배열 내 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘. 1. 거품정렬(bubble sort): 서로 인접한 두 원소를 비교하면서 정렬하는 알고리즘 평균 시간 복잡도: O(n^2) 1.인접한 값 비교 => 큰값 교환 2. index N번 3. N 차례 N-i //swap함수는 arr를 받고 매개변수 두개를 받아 각각의 인덱스를 받는다. let swap = function (arr, idx_1, idx_2){ //원소의 값 교환 let tmp = arr[idx_1]; arr[idx_1] = arr[idx_2]; arr[idx_2] = tmp; }; let bubbleSort_1 = function (arr){ for (let i = 0; i < arr.leng..

[프로그래머스] Lv.1 나누어 떨어지는 숫자배열 https://programmers.co.kr/learn/courses/30/lessons/12910 [문제] array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요. [제한사항] arr은 자연수를 담은 배열입니다. 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다. divisor는 자연수입니다. array는 길이 1 이상인 배열입니다. 입출력 예 arr divisor return [5, 9, 7, 10] 5 [5, 10] [2, 36, 1, 3] 1..

힙이란? 최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조다 최소힙은 작은 값이 항상 가장 위에 노드에 있게해서 트리의 루트에는 가장 작은 값이 오게하는 최소힙이다. 가장 큰값이 맨 위에 오도록하는 구조가 최대힙이다. 최소힙에 노드 삽입하기 완전 트리에 맨 끝에 노드를 추가한다. 트리가 컴플리트 바이너리 형태를 잃지 않도록 마지막 레벨의 왼쪽부터 채워나간다. 다음 스텝은 자신의 부모 노드와 비교해서 자신이 값이 작으면 부모 노드랑 자리를 바꾼다. 부모 노드가 자기보다 작을 때 까지 반복한다. 완전 이진 트리에서 이루어지니까 한번 돌 때 마다 o(logn)의 시간 복잡도를 가진다. 최소힙에서 노드 꺼내오기 최소힙에서 작은 값은 루트에있으니까 어렵지 않다. 루..

수박수박수박수박수박수? 문제 설명 길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다. 제한 조건 n은 길이 10,000이하인 자연수입니다. 입출력 예 n return 3 "수박수" 4 "수박수박" function solution(n) { let str = "수박"; let temp = ''; let str1 = ''; temp = str.repeat(n); str1 = temp.substring(0,n); //return str.repeat(n).substring(0,n); 으로 한줄로 쓸 수 있다. return str1; } '수', '박' 이 n개 출..

숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → "one4seveneight" 234567 → "23four5six7" 10203 → "1zerotwozero3" 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요. 참고로 각 숫자에 대응되는 영단어는 다음 표와 같습니다. 숫자영단어 0 zero 1 one 2 two 3 three 4 four 5 five 6 s..