Algorithm (6) 썸네일형 리스트형 해시테이블 // string 자료형의 key에 해당하는 공간에 string 자료형의 value를 넣은 것 // 키와 값의 형태로 데이터를 저장하는 구조는 자바스크립트 object or map으로 구현가능 class HashTable { table = new Array(100); // key, item을 파라미터로 받아와 넣어줌 setItem = (key, value) => {}; // key를 파라미터로 받아서 table key에 맞는 value를 불러옴 getItem = (key) => {return '' ; }; } // 함수 선언 function hashStringToInt(s) { return 3; } // setItem함수 선언 // key에 어떤 값을 넣든 idx =3 setItem = (key, val.. [알고리즘] 문자열 출력 / substr / substring / charAt 코테 문제를 풀다 보면 문자열을 잘라서 출력해야 할 경우가 있다. 그래서 관련된 자바스크립트 메서드를 찾다가 정리해놓으면 한번에 보기 좋을 것 같아 적어보는 포스팅.. 대표적으로 substr / split / substring / charAt 까지 정리해보았다. .slice(beginIndex, [,endIndex]) 문자열을 뒤에서부터 자르기 위해서 slice()함수를 사용하면 효율적 substring()과 동일하지만, 음수를 자유롭게 사용가능 var st = "자바스크립트"; var result1 =st.slice(0,2); // 자바 var returt2 = st.slice(2,6); // 스크립트 var result3 = st.slice(-4); // 스크립트 // => 뒤에서부터 4번째 ~ 끝 .. [알고리즘] 유클리드 호제법 / 최대공약수 2개의 자연수 or 최대공약수를 구하는 알고리즘 중 하나 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같음 최대공약수를 구하는 일반적 방법 소인수분해를 통해 두 수의 최대공약수를 구하기 위해서 사용 -> 두 수를 소인수분해 한 후, 공통 소수를 찾음 그러나, 숫자가 커질수록 소인수분해 하기 어려움 MOD연산 두 값을 나눈 나머지를 구하는 연산 유클리드 호제법은 MOD연산의 반복 나머지가 0이 되었을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수 1112 mod 695 = 417 695 mod 417 = 278 417 mod 278 =139 278 mod 139 = 0 * 두 수에 대한 유클리드 호제법.. [알고리즘] BFS / DFS 그래프 탐색 그래프 탐색의 목적 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문 (e.g. 특정 도시에서 다른 도시로 갈 수 있는가) 그래프의 데이터는 배열처럼 정렬되어있지 않기 때문에, 원하는 자료를 찾으려면 하나씩 방문해야 함 그래프의 모든 정적 탐색 방법 지하철 노선 애플 경로를 탐색할 때, 최단 경로 OR 최소 환승 등 여러 방법이 존재함 그 방법 중 DFS, BFS는 데이터를 탐색하는 순서가 다르지만, 모든 자 료를 하나씩 확인해봄 BFS (Breadth-First Search) : 너비 우선 탐색 너비(최단경로)를 우선적으로 탐색하는 방법, Queue를 활용 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때 사용 시작점의 가까운 정점들을 차례대로 방문한 후, 방문했던 정.. [알고리즘] 시간복잡도 Time Complexity 알고리즘은, 어떤 목적을 달성하거나 결과물을 만들어 내기 위해 거치는 일련의 과정 효율적으로 프로그래밍 문제를 풀기 위해 사용하는 것이 "시간복잡도"가 낮은 알고리즘을 사용함 입력값이 커짐에 따라서 증가하는 시간비율을 최소화한 알고리즘을 구현하는 것이 목표 알고리즘의 실행시간 = 컴퓨터가 알고리즘 코드를 실행하는 속도 컴퓨터의 처리속도 / 사용자의 언어종류 / 컴파일러의 속도에 따라 달려있음 1) 입력값의 크기에 따라서 알고리즘의 실행시간을 검증 2) 입력값 크기에 따라 함수증가량(성장률)에 집중하는 것 (점근적 표기법 : 오메가 / 세타 / 빅오) 시간 복잡도의 표기법 (빅오 표기법) 1) 오메가 표기법 Big-Ω (최상) 2) 세타 표기법 Big-θ (평균) 3) 빅오 표기법 Big-O (최악) : .. [알고리즘] Queue / Stack Queue 막대 형식의 자료구조 (입력들을 순서대로 저장) 한 쪽 끝에서 자료를 넣고 다른 한쪽에서만 자료를 뺄 수 있는 구조 (선입선출, FIFO) JS에서 제공하는 push, shift()메서드를 사용하고, shift의 경우 배열탐색이 필요하므로 시간복잡도O(N)임 → JS배열은 해시 테이블로 구현된 객체라, 데이터량이 많아질수록 런타임 길어짐 (1000건 이하는 Shift 사용가능) 순서대로 처리해야 할 작업을 임시로 저장해두는 버퍼로 사용 createQueue () 큐를 생성 ( 맨앞 front , 끝 rear - index -1) enQueue : 큐에 요소 추가 / rear + 1 deQueue : 큐에서 맨 앞의 요소 빼기 (front +1 ) push() / enqueue() 큐에 자료를 .. 이전 1 다음
