본문 바로가기
300x250

알고리즘18

[자료구조] 시간복잡도와 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.
코드스테이츠 12주차리뷰 한번의 기수이동으로 섹션투에서 2주가 지났다. 지금까지 토이문제도 끝까지 못풀더라도 시간맞춰 제출하고 있고, 일정에 맞게 스프린트를 잘 진행하고 있다. 공부 외적으로 지금은 알고리즘 공부를 위해 스터디도 시작하여 프로그래머스 1단계 문제들을 풀었다. 확실히 스터디가 있어서 그런지 강제적으로라도 하게 되어 공부가 된다. 스터디 외에도 예전에 페어했던 분과 함께 토요일마다 스터디처럼 줌으로 만나 조금은 난이도가 있는 문제를 풀어나가고 있고, 첫페어였던 형과도 계속연락하며 서로에게 도움이 될만한 정보를 공유하고 있다. 이번 주에 공부하며 약간 위축되었다. 정말 이대로 괜찮은가?라는 생각을 했다. 나름 열심히 하고 있다고 생각했는데, 다들 하는거 보면 정말 열심히 하는게 느껴진다. 알고리즘 문제를 같이 풀고 있.. 2021. 6. 28.
[알고리즘] DFS - 깊이 우선 탐색 개념 정리 깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. 깊이 우선 탐색(Depth First Search)은 맹목적으로 각 노드를 탐색할 때 주로 사용된다. 너비 우선 탐색(Breadth First Search)에선 큐가 사용되었다면, 깊이 우선 탐색(DFS)에서는 재귀와 스택(stack)이 사용된다. DFS 로직을 구현하는 과정에 재귀 함수를 활용하기 때문에, 더 이상 child node가 존재하지 않을 때까지 콜스택의 상단에 계속 쌓이게 되고, 끝에 다다랐을 경우부터 하나씩 pop up되면서 값이 담기기 때문이다. 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에 스택을 사용하지 않아도 구현이 가능하다는 특징이 있다. DF.. 2021. 6. 24.
[알고리즘] 동적계획법(DP), 다이나믹 프로그래밍 개념정리 다이나믹 프로그래밍이란 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. DP 동적계획법이라고 한다. 하나의 문제를 딱 한번만 풀어 비효율적인 알고리즘을 개선시키는 방법이다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문에제에도 동일하다. 크고 어려운 문제가 있을면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것이다. 이 과정에서 '메모이제이션(Memoization)이 사용된다. 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환만 하면 된다. 가장 기본적인 예시로 피보나치 수열이 있다. 첫번째 코드를 보게되면 오로지 재귀함수로만 문제를 풀게되면 다음과 같은 코드가 나온다. num .. 2021. 6. 22.
[알고리즘] 체육복_프로그래머스 1단계 문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 .. 2021. 6. 20.
[알고리즘] 폰켓몬_프로그래머스 1단계 문제설명 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택 두 번째(1번), 세 번째(2번) 폰.. 2021. 6. 20.
[알고리즘] 내적_프로그래머스 1단계 문제설명 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 길이) 주의사항 a, b의 길이는 1 이상 1,000 이하입니다. a, b의 모든 수는 -1,000 이상 1,000 이하입니다. 입출력예시 코드 function solution(a, b) { var answer = 0; for(let i =0 ; i< a.length ; i++){ let num = a[i] * b[i] answer += num } return answer; } 한줄 코드... let solution=(a,b).. 2021. 6. 20.
[자료구조 with javascript] Graph 그래프 탐색 개념 정리(인접행렬) Graph란? 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 있다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다. 즉, 정점과 간선으로 이루어진 자료구조의 일종 무방향 그래프와 방향그래프 간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다. 무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있는 그래프를 말한다. 예를 들면 우리가 차를 타고 서울에서 부산으로 갈 수 있고, 부산에서 서울로 올수 있다. 정점 A와 B를 연결하는 간선은 (A,.. 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.
반응형