내가 보는 세상 이야기

Lesson 4-1 - PermCheck내용 : Check whether array A is a permutation.시간 복잡도 : O(N)성공한 코드function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let A_len = A.length; let total = A_len*(A_len+1)/2; let rt_val = 0; let tmp_arr = {}; for(i in A) { rt_val += A[i]; tmp_arr[(A[i]-1).toString()] = A[i]; /* for [1,4,1] antisum test case */ } if(rt_val==total && Object.keys(tmp_arr).length =..

Lesson 3-3 - TapeEquilibrium내용 : Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|시간 복잡도 : O(N)성공한 코드function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let tot = 0; let rt_val = 100001; let tmp_tot = 0; for(i = 0;i

Lesson 3-2 - PermMissingElem내용 :Find the missing element in a given permutation시간 복잡도 : O(N) 성공 했지만 민망해서 공개 안하는 코드 : function isZero(element) { return element == 1; } function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let rt_arr=new Array(A.length+1); rt_arr.fill(1); for(i in A) { rt_arr[A[i]-1]=0; } //console.log(rt_arr.findIndex(isZero)+1); return rt_arr.findIndex(isZero)+..

Lesson 3-1 - FrogJmp내용 :Count minimal number of jumps from position X to Y.시간 복잡도 : O(1) 성공한 코드 :function solution(X, Y, D) { // write your code in JavaScript (Node.js 6.4.0) let rt_val = (Y-X)/D; return Math.ceil(rt_val); } 결론 : 요것도 좀 쉬운듯쉬워도 댓글 보면서 다른 방법에 대한 고민 필요댓글 살펴보다 든 생각:과연 잘 짠 소스랑 무엇일까?rt_val = (Y-X)/D; return Math.ceil(rt_val);return (Y-X) % D > 0 ? (Y-X)/D+1 : (Y-X)/D;Y = JD + X, JD = -..

Lesson 2-2 - CyclicRotation내용 :Rotate on array to the right by a given number of steps.시간 복잡도 : no 성공한 코드 : function solution(A, K) { // write your code in JavaScript (Node.js 6.4.0) let rt_arr = []; for(i in A) { let idx = (Number(i)+K)%A.length; rt_arr[idx]=A[i]; } return rt_arr; } 결론 : 요건 많이 해보던거라 좀 쉬움코딜리티 댓글에 배울게 좀 있음

Lesson 2-1 - OddOccurencesInArray내용 :Find value that occures in odd number of elements.시간 복잡도 : O(n) 성공한 코드 : function solution(A) { let rt = 0; for(i in A) { rt = rt ^ A[i]; } return rt; } 실패한 코드 :function solution(A) { let sort_A = A.sort();let rt = 0;for(i in sort_A) {if(i==0 || sort_A[i] != sort_A[i-1] && sort_A[i] == sort_A[i+1]){rt = sort_A[i];}}}return rt; 결론 : 아는게 힘간단한 코드라도 좀 더 신중하게알고리즘 ..

알고리즘 공부할 자료를 찾다보니애증의 codility 에서 연습문제를 주는 것을 발견 !!!!가능한 하루에 하나씩 풀어보기로 했다. 오늘은 첫 발 시작이 반 Lesson 1 - BinaryGap내용 : find longest sequence of zeros in binary representation of an integer.시간 복잡도 : logn 내 코드 : function solution(N) { // write your code in JavaScript (Node.js 6.4.0) let b_str = N.toString(2); let gap_pattern = /1[0]+(?=1)/g; let zero_pattern = /[0]/g; let match_arr = b_str.match(gap_pat..

자료 구조와 알고리즘 관련 내용을 정리하고 봐야 할 경우가 자주 생기고무시하고 갈 수 없는 상황이라구글 검색을 바탕으로 옛 기억을 꺼내 보고자 한다. 알고리즘의 기초만 정리하자면시간복잡도 - CPU 사용량에 대한 계산공간복잡도 - RAM 사용량에 대한 계산여러가지 표기법이 있지만 빅오 표기법이 가장 많이 사용계산법이 중요 , cpu 의 실제 실행 시간이 아닌 실행 횟수를 계산계산법은 간다하게 명령어의 실행 횟수를 계산해서 최고차항을 이용O(n), O(logn) , O(n2) .... 등등으로 표기지루하고 자세한건 위키백과 에서 확인 가능하다. 내가 볼때 중요한 것은 O(logn) 이다. 온라인 코딩 테스트도 이부분을 많이 물어보는 듯 하다.logn은 로그형 시간으로 시간이 지남에 따라 연산이 줄어드는 것..