알고리즘(3)
-
동적 계획법(Dynamic Programming)
동적 계획법: 하나의 문제를 여러 작은 문제로 나누고, 작은 문제의 결과를 저장하여 큰 문제를 해결한다. 하나의 문제를 여러 개의 하위 문제로 나눈 다음, 결합하여 답을 도출한다. 하위 문제들의 결과를 저장한다.(Memoization, 메모이제이션) -> 동일한 문제가 나왔을 때 저장해둔 결과를 가져다 쓰며, 실행속도 빠르게 한다. 겹치는 부분 존재 DP는 작은 문제의 결과를 저장하고 재사용하여 문제를 푼다. 따라서, 동일한 작은 문제가 있을 때 사용한다. 최적 부분 구조 작은 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 작은 문제에서 구한 최적의 결과가 큰 문제에서도 동일하게 최적으로 적용되는 경우이다. 동적계획법의 가장 대표적인 피보나치 수를 구현해보자! 피보..
2023.03.10 -
[프로그래머스] N으로 표현
동적계획법(Dynamic Programming)을 사용한 문제이다. 모든 값을 연산해봐야 한다는 것은 이해를 했다. 근데, 도대체 어떻게 구현해야 하는지 완전탐색과 다른것은 무엇인지... * 동적계획법을 공부하면서 완전탐색과는 완전히 다르다는 것을 알았다. 헷갈린다면, https://chyunlog.tistory.com/34 참고! 따라서 다른 분의 풀이를 해석해보기로 했다. 완전탐색처럼 도대체 컴퓨터 안에서 어떻게 돌아가는지 헷갈리지만... 주석을 꼼꼼히 달아놨으니 이해하는데 도움이 되길! function solution(N, number) { // 최솟값이 8보다 크면 -1을 return 합니다.라는 제한사항이 있기에 // 1~8까지의 경우의 수를 저장할 길이 8인 배열을 만든다. // 배열의 각 값..
2023.03.09 -
스택과 큐
자료구조 중 스택과 큐는 많이 들어보았지만, 항상 뭐가 뭔지 헷갈렸다. 이번 기회에 제대로 확실히 정리해보고자 한다! 일단 자료구조란 배열처럼 데이터를 저장하고 관리할 수 있는 것이다. 스택과 큐는 데이터를 어떻게 저장하고 관리하는지 알아보자 ! 스택은 후입선출 js에서 push()는 삽입, pop()은 삭제 함수이다. ex) 인터넷의 뒤로가기(그동안 쌓였던 것들의 뒷부분 부터 차례로 뒤로가기 됨) 큐는 선입선출 queue에 삽입하는 것은 enqueue라 하고, 삭제하는 것은 dequeue라고 한다. 마찬가지로 push()는 삽입, shift()는 가장 앞의 것 삭제 함수이다. ex) 은행창구 번호표(들어온 순서대로 나감) 시간복잡도에 대해 이야기 하자면 push()와 pop()은 O(1)의 시간복잡도를..
2023.03.02