algorithm
-
그래프에 대한 이해IT 지식 2021. 8. 18. 22:24
그래프 용어 정점: 그래프를 형성하는 노드 간선: 그래프에서 노드 간의 연결을 말한다. 정점 차수: 정점(노드)에 연결된 간선의 개수를 나타낸다. 희소 그래프: 정점들 간에 가능한 연결 중 일부만 존재하는 경우 해당 그래프를 희소 그래프라고 한다. 밀집 그래프: 다양한 정점들 간에 연결이 많은 경우 해당 그래프를 밀집 그래프라고 한다. 순환 그래프: 어떤 정점에서 출발해 해당 정점으로 다시 돌아오는 경로가 존재하는 지향성 그래프를 말한다. 가중치: 간선에 대한 값으로, 문맥에 따라 다양한 것을 나타낼 수 있다. // 무지향성 그래프 function UndirectedGraph (){ this.edges = {}; } UndirectedGraph.prototype.addVertex = function (v..
-
[TIL]캐싱IT 지식 2021. 7. 25. 18:22
오늘 포스팅은 자바스크립트로 하는 자료구조와 알고리즘 14장 캐싱을 바탕으로 작성했습니다. 1. 캐싱이란? 캐싱(caching)은 자료를 임시 메모리에 저장하는 과정으로 추후에 해당 자료가 다시 필요할 때 쉽게 해당 자료를 얻을 수 있다. 캐싱의 예로 데이터베이스 시스템이 데이터를 캐싱해 하드 드라이브를 다시 읽는 작업을 피한다. 또한 웹 브라우저가 웹 페이지를 캐싱해 콘텐츠를 다시 다운로드 하는 작업을 피한다. 간단히 이야기 해서 캐싱의 목표는 히트(필요한 항목이 캐시에 존재하는 경우)를 최대화하고 미스(필요한 항목이 캐시에 존재하지 않는 경우)를 최소화 하는 것이다. 2. 캐싱 이해하기 캐시 설계는 다음의 두 가지 요소를 고려한다. 시간적 지역성: 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높..
-
[TIL] 스택과 큐IT 지식 2021. 7. 11. 17:49
1. 스택 1) 정의 스택은 자료구조의 일종으로, 마지막에 삽입된 항목만을 제거하고 접근할 수 있다. 이러한 원리를 후입선출(LIFO)이라고 한다. 스택은 속도가 빠르다는 장점이 있다. 스택은 알고리즘이 마지막에 추가된 항목만을 접근해야 하는 후입선출 형태로 자료를 처리해야 하는 경우에만 배열에 대해 사용한다. 스택의 한계는 배열과 딜리 마지막에 추가된 항목 외에는 직접 접근할 수 없다는 것이다. 게다가 초반에 추가된 항모글 접근하기 위해서는 이후에 추가된 항목들을 자료구조로부터 제거해야 한다. 자바스크립트에는 스택 클래스를 정의한 pop과 push라는 메소드가 있다 2) 들여다보기 스택의 마지막에 추가된 항목을 들여다보는 것(peeking)은 마지막에 추가된 항목을 스택 자료구조에서 제거하지 않고 반환..
-
[TIL] 해시 테이블IT 지식 2021. 7. 11. 17:04
1. 해시 테이블의 정의 해시 테이블은 고정된 크기의 자료 구조로 처음에 크기가 정해진다. 해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고, 키-값을 기반으로 자료를 얻을 수 있다. 자바스크립트에서 자바스크립트 객체는 해시테이블과 같은 방식으로 키와 해당 키의 연관된 값을 정의하는 방식으로 동작한다. 해시 테이블에는 put(), get() 이리ㅏ는 두 가지 주요 함수가 있다. put()은 자료를 해시 테이블에 저장하는데 사용하고, get()은 해시 테이블로부터 자료를 얻는 데 사용된다. 두 함수 모두 시간 복잡도가 O(1)이다. 간단히 말하자면 해시 테이블은 인덱스가 해싱 함수에 의해 계산되는 배열과 매우 유사하다. 이때 인덱스는 메모리에서 유일한 공간을 식별하기 위한 것이다. 2. 해싱 기법..
-
[TIL] 알고리즘 풀이 - 프로그래머스 '문자열 내 p와 y의 개수문제'IT 지식 2021. 5. 1. 16:31
문제 소개 더보기 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다. 예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다. 제한사항 문자열 s의 길이 : 50 이하의 자연수 문자열 s는 알파벳으로만 이루어져 있습니다. 문제 풀이 더보기 function solution(s){ var count_p = 0; //p의 개수 카운트 var count_y = 0; // y의 개수 카운트 for(var ..
-
[TIL] 21/01/19 알고리즘 풀이IT 지식 2021. 1. 19. 11:59
오늘의 문제 - 프로그래머스 '체육복' 문제 소개 더보기 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 ..
-
[TIL] 21/01/18 알고리즘 풀이IT 지식 2021. 1. 18. 11:34
오늘의 문제 - 프로그래머스 '가운데 글자 가져오기' 문제 소개 더보기 가운데 글자 가져오기 단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다. 제한사항 s는 길이가 1 이상, 100이하인 스트링입니다. 입출력 예 sreturn abcde c qwer we 나의 풀이 초기 풀이 더보기 function solution(s) { var answer = ''; //단어를 추출하기 위해 단어를 하나하나 쪼개야 한다고 생각했습니다. let answerArr = []; s = s.split('') //그리고 가운데 글자의 위치를 파악하기 위해 중간 지점의 숫자도 설정해주었습니다. var n = parseInt((s.length - 1)..
-
[TIL] 21/01/15 알고리즘 풀이IT 지식 2021. 1. 15. 11:52
오늘의 문제 - 프로그래머스 코딩테스트 연습 '모의고사' 오늘 문제는 아쉽게도 해결하지 못해서 다른 분의 코드를 보면서 이해하는 쪽으로 공부를 했습니다. 문제 설명 더보기 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제..