본문 바로가기
300x250

자료구조8

[자료구조] 시간복잡도와 Big-O 표기법 시간복잡도와 Big-O 표기법 우리가 알고리즘 문제를 풀때 중요한 것은 해답을 찾는 것이다. 더 나아가 그 문제를 좀더 효율적인 방법을 찾는 것도 굉장히 중요하다. 좀더 효율적인 방법을 고민해 본 적이 있다면 시간 복잡도를 고민한다는 것과 같은 말이다. 알고리즘에서 빠르다는 의미는 시간으로 표현하지 않는다. 알고리즘에서는 절차(step)의 수로 결정된다. 10번의 스텝이 필요한 알고리즘보단 5번의 스텝이 필요한 알고리즘이 더 훌륭하다고 볼수있다. 시간 복잡도를 표기하는 방법은 다음과 같다. Big-O(빅-오) Big-Ω(빅-오메가) Big-θ(빅-세타) 다른건 잘 모르겠고,Big-O 표기법이 자주 사용된다. 빅오 표기법의 종류는 O(1), O(n), O(log n), O(n2), O(2n) 등이 있다. .. 2021. 7. 19.
[프로그래머스 2단계 문제] 기능개발 문제설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 주의사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자연수.. 2021. 6. 21.
[자료구조 with javascript] Graph 그래프 탐색 개념 정리(인접행렬) Graph란? 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 있다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다. 즉, 정점과 간선으로 이루어진 자료구조의 일종 무방향 그래프와 방향그래프 간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다. 무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있는 그래프를 말한다. 예를 들면 우리가 차를 타고 서울에서 부산으로 갈 수 있고, 부산에서 서울로 올수 있다. 정점 A와 B를 연결하는 간선은 (A,.. 2021. 6. 20.
코드스테이츠 11주차지만 6주차리뷰 - 기수이동 후 첫 주 섹션 투에서 기수이동되고나서 첫주가 흘렀다. 기수이동 되었을 때 약간의 충격을 받았던거와 달리 한주가 지나고 나서 이 글을 쓰는 지금, 기수이동 된 것에 굉장히 만족하고 있다. 그 이유는 자료 구조의 그래프와 트리를 조금은 이해할 수 있게 되었다. 기수이동 전 섹션투를 진행했을 때 자료구조 부분에서 나는 문제를 포기했었다. 13개의 스택, 큐, 트리, 그래프 문제가 있었고, 그 중에 나는 6개의 문제를 포기했었다. 레퍼런스는 봐도 이해 안되고, 뭔 소린지 도통 모르겠어서,,, 멘탈 붕괴 직전까지 가서 내가 싫었다ㅋㅋㅋㅋ 그냥 넘어가서 섹션쓰리를 배웠다면 오히려 더 고생했을거다. 두번째인 지금은 문제를 이해하고, 페어와 코드로 구현하고 반복하여 내것으로 만들었다. 다른 페어분도 도와줄 수 있을 정도로 문제.. 2021. 6. 20.
[알고리즘 문제풀이]올바른 괄호_프로그래머스 2단계 문제 문제설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 주의사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다. 입출력예시 코드 function solution(str){ let answer = true; let stack = []; if(str[.. 2021. 6. 20.
[알고리즘 문제풀이]3개의 수를 더한 숫자를 소수 만들기 문제풀이 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 입출력예시 코드 function solution(nums) { let answer = 0, number=0; for(let i=0;i 2021. 6. 16.
[알고리즘 문제풀이] 완주하지 못한 선수 with javascript 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예시 코드 작성 1. 정렬 후 같은 인덱스 위치에 없으면 리턴 function .. 2021. 6. 14.
자바스크립트_자료구조 stack과 queue 개념 정리 오늘은 자료구조에서 stack과 queue에 대해서 알아보겠습니다. 먼저 자료구조가 무엇인지 설명해보겠습니다. 자료구조란 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 것들을 우리는 자료라고 합니다. 자료들이 잘 분석되고, 정리되고 활용되어야만 의미가 있다고 볼 수 있는데, 무분별하게 마구잡이로 자료를 체계없이 저장하면 의미가 없어집니다. 자료를 구조화 시키는 것. 그렇기에 우리는 잘 정리된 자료를 활용하기 위해 자료 구조를 갖추려고 하는 것입니다. Stack stack이란 후입선출(LIFO, Last-in-first-out)의 구조이다. 스택은 데이터를 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 만약 0-1-2-3-4-5 순으로 쌓았다면, 5-4-3-2-1-0 순으로 빼낼 수 있다. .. 2021. 5. 19.
반응형