분류 전체보기

[JavaScript] 알고리즘에 쓰이는 문법(형변환)

형변환 Number() string을 숫자로 바꿔줌 문자가 하나라도 포함되어 있을경우 NaN출력 Number('123') // 123 Number('12.3') // 12.3 Number('123e-1') // 12.3 Number('') // 0 Number(null) // 0 Number('0x11') // 17 Number('0b11') // 3 Number('0o11') // 9 Number('foo') // NaN //문자가 하나라도 있으면 Nan Number('100a') // NaN parseInt string을 진수별 10진수 정수로 바꿔줄 수 있음 숫자가 하나라도 있으면 숫자출력(Number와의 차이점) ECMAScript 5는 8진수 해석을 삭제했음 parseInt('12.68') //..

[JavaScript] 알고리즘에 쓰이는 문법 (자르기)

자르기 slice() start부터 end전까지 복사본을 새로운 배열 객체로 반환 원본 배열 수정x const array = [1, 2, 3, 4, 5] let arr = array.slice(1, 4) //[2, 3, 4, 5] splice() start지점부터 length개 인자 삭제 원본배열 수정됨 뒤에 추가할 인자 삽입가능 var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]; var arr1 = arr.splice(10, 2, 'a', 'b', 'c'); //start, length, 추가인자 console.log(arr); //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10,'a', 'b', 'c'] console.log(arr1); //[11, 12..

[다이나믹프로그래밍] DP - JS, Python

다이나믹 프로그래밍 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하려는 알고리즘 기법 다이나믹 프로그래밍을 사용할 수 있는 경우 1. 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다) 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결 (최적화)) 위의 두 조건이 모두 충족할 경우 다미나믹 프로그래밍을 사용할 수 있다 (점화식 사용) 다이나믹 프로그래밍 최적화의 핵심 각 작은 문제는 한 번만 풀어야 한다 Optimal Substructure를 만족하기 때문에 같은 문제는 구현 때마다 정답이 같다 정답을 한 번 구했으면 어딘가에 메모해 놓는다 메모하는 것을 코드에서는 배열로 구현할 수 있다 메모한다고 해서 memoization 용어를 쓴다 다이나믹 프로그래밍의 ..

[이진탐색] binary Search - JS, Python

이진탐색 알고리즘 이진탐색의 전처리 과정은 오름차순 정렬이다 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 알고리즘 반으로 쪼개면서 탐색하기 1. 정렬된 리스트를 준비한다 2. idx 0부분을 start, idx 마지막 부분을 end, (start + end) // 2를 mid로 설정 3. array[mid]값이 target보다 크면 end를 mid-1지점으로 바꾼다 + mid도 다시 설정 4. array[mid]값이 target보다 작으면 start를 mid+1지점으로 바꾼다 + mid도 다시 설정 5. start가 end보다 클때까지 반복한다 6. 반복했음에도 값이 없으면 None을 반환하고, array[mid]가 t..

[정렬] Counting Sort - JS, Python

계수정렬 알고리즘 계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 최악의 경우에도 O(N+K)를 보장한다 **K는 가장 큰 수 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능 가장 작은 데이터의 차이가 1,000,000을 넘기지 않을 때 효과적으로 사용할 수 있다 원소간 직접 비교하지 않고 각 원소가 몇 개 등장하는지 갯수를 세서 정렬하는 방법 1. array data값의 min, max값 찾기 1. 모든 범위를 포함하는 리스트 선언하기 (data의 min~max값 크기만큼, 0으로 초기화) 2. array의 data값을 list의 idx와 매치하여 count 1씩 증가시키기 3. list idx의 count한 값 만큼 차례대로 출력해주기 Big ..

[Python] 정렬 라이브러리

헷갈려하던 python 정렬에 대해 정리해 보려 합니다 python 정렬 라이브러리는 sorted와 sort가 있습니다 sorted와 sort의 공통점은 오름차순으로 key값을 사용해 정렬가능하다는 것이고 sorted는 별도의 정렬된 리스트를 return해주고 sort는 별도 정렬된 리스트가 반환되지 않고 내부원소가 바로 정렬된다는 차이점이 있습니다 sorted() array = [5, 3, 2, 4, 1] result = sorted(array) print(result) // [1, 2, 3, 4, 5] sort() array = [4, 5, 2, 1, 3] array.sort() print(array) // [1, 2, 3, 4, 5] key를 활용한 소스코드 sort와 sorted는 key매개변수를..