'Algorithm' 카테고리의 글 목록

2023.05.19· Algorithm/DailyCoding

tiling 세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다. 이런 경우의 수 문제는 일단 작은 수를 손수 계산해서 규칙을 찾아가는 것이 빠르다. 모아놓고 보니 규칙성이 보인다 n=1 -> 1 n=2 -> 2 n=3 -> 3 n=4 -> 5 n=5 -> 8 ... 세로의 길이는 고정된 채로 가로의 길이만 늘어난 것이기 때문에, 쪼개어서 생각하면 편리하다. 결국 한 칸을 차지하는 2x1을 제외한 나머지 모양이 바로 전 (n-1)과 같고, 두 칸을 차지하는 최소 2x2를 제외한 나머지 모양이 (n-2)와 같다는 것을 알 수 있다. 즉 피보나치와 완전 유사한 수열이 되는 것. 단순한 재귀로 나타내어 보면 let t..

[23.02.24] Daily Coding 24

2023.05.19· Algorithm/DailyCoding

isSubsetOf 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다. const isSubsetOf = function (base, sample) { return sample.every((number) => base.includes(number)); } array 매서드인 every, inclueds사용. -> 시간 초과 시간 복잡도를 개선하기 위해 일단 배열을 오름차순으로 정렬했다. base.sort((a, b) => a - b); sample.sort((a, b) => a - b); for(let i = 0; i < base.length; i++) { if(base[i] === sample[0]) { sample.shift(); } } i..

[23.02.22] Daily Coding 23

2023.05.19· Algorithm/DailyCoding

bubbleSort 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다. 버블 정렬 알고리즘은 아래와 같습니다. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교) 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다. 1~3의 과정을 첫 요소부터 다시 반복합니다. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번..

[23.02.21] Daily Coding 22 - fibonacci

2023.05.19· Algorithm/DailyCoding

fibonacci 아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다. (반복문 사용x) 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 7번째 피보나치 수가 나오는 과정 (n=7)을 나열해보면, 0 1 1 = 0 + 1 2 = 1 + 1 3 = 2 + 1 5 = 3 + 2 8 = 5 + 3 13 = 8 + 5 이를 함수로 표현해보면 f(n) = f(n-1) + f(n-2) n>=2인 자연수, f(0) = 0 , f(1) = 1 즉 f(n)은 숫자를 입력받아서 총 n+1 개를 더하게 되는 함수가 된다. functio..

[23.02.20] Daily Coding 21

2023.05.19· Algorithm/DailyCoding

largestProductOfThree 정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다. 섹션3들어 급격히 어려워진 난이도에 오함마로 한대 맞은 기분.. ㅎ_ㅎ 섹션2부터 다시 시작하게 된 데일리코딩. 일단 처음에 생각했던 것은, 음수와 0이 섞여있으니 이걸 주의해야겠다 싶었던 거였음. // 배열 중 (절댓값이) 가장 큰 수 3개? // 음수는 짝수 개여야 함. // 3개 중에 0은 없어야 함. let arr = [-1, 8, 0, -134, -44] arr.map(Math.abs) = [1, 8, 0, 134, 44] arr.map(Math.abs).sort() = [0, 1, 134, 44, 8] let plus = arr.map(Math.abs) plu..

빅오 표기법 (Big - O notation)

2023.05.18· Algorithm/알고리즘 스터디

시간 복잡도 O(입력)O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^2) < O(n!) 오른쪽으로 갈 수록 실행 횟수가 많은, 시간 복잡도가 높은 것이다.O(1)var n = []; // n에 계속적으로 숫자 대입 function o1() { return (n[0] === 0) ? true : false; } // 데이터가 증가해도 위 function o1 function의 성능은 그대로다. O(n)let n = []; for (let i = 0; i < n.length; i++) { return n[i] } // 배열의 n의 길이가 증가할 때마다 처리 시간이 증가한다.입력n만큼 출력을 반복하는 반복문 O(n^2)let n = []; for(let i = 0;..

Hash 알고리즘

2023.05.18· Algorithm/알고리즘 스터디

해시의 개념해시는 키:밸리의 자료구조를 갖는 배열 전화번호부처럼 검색창에 이름(키)을 검색 -> 전화번호(밸류)가 나옴 키가 스트링이다해시맵 함수HashMap.put("A", true); 라고 입력하면 마치 HashMap["A"] = true;원래 해시맵함수는 a가 있다는 것을 전제로 하기 때문에 a가 없다면 에러가 발생하는 작업이 필요. 그래서 a가 있다는 것을 확인해야 하는 번거로움이 있는데 이걸 개선하기 위한 것이 겟올 티폴트 함수이다 키가 없을 경우 에러처리를 한 함수내에서 전부해주는 것. get/ put/ getOrDefaultString을 기반으로 정보를 기폭하고 관리해야 될 때 (스트링타입을 기준으로 정보를 기록하고 관리하려면 단순배열을 쓸 수 없으니 해시를 쓰자) 1) 완주하지 못한 선수 ..

[22.11.02] Daily Coding 25

2023.05.17· Algorithm/DailyCoding

25번. tiling 세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다. 내가 쓴 답 let tiling = function (n) { // 2 x 4 보드에 타일을 놓는 경우 // 1) 처음에 세로로 하나 놓는 경우 : 2 x 1 + 2 x 3 // 2) 가로로 놓는 경우 (밑에도 가로로 놓게 됨) : 2 x 2 + 2 x 2 // => 즉 n=4 일 때 경우의 수 : n = 2, 3 일 때를 더한 것 (재귀) let arr = [0,1,2]; const boxTiling = (n) => { if(arr[n]) return arr[n]; return arr[n] = boxTiling(n-1) + boxTili..

[코딩 테스트] Programmers - 모음사전(Javascript)

2023.05.17· Algorithm/알고리즘 스터디

프로그래머스 - 모음사전 문제 설명 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요. 제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다. 입출력 예 입출력 예 설명 입출력 예 #1 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE",..

[코딩 테스트] Programmers - 괄호 변환(Javascript)

2023.05.17· Algorithm/알고리즘 스터디

프로그래머스 - 괄호 변환 문제 설명 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 ..

[코딩 테스트] Programmers - 구명보트(Javascript)

2023.05.17· Algorithm/알고리즘 스터디

프로그래머스 - 구명조끼 문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solut..

[22.10.04] Daily Coding 10

2023.05.17· Algorithm/DailyCoding

10번. 문자열을 입력받아 연속된 한자리 홀수 숫자 사이에 '-'를 추가한 문자열을 리턴해야 합니다. function insertDash(str) { let result = str[0] for (let i = 1; i

티스토리툴바