목록CS/자료구조 (27)

기어가더라도 제대로

[기초 자료구조] 약수의 합 구하기

n 의 제곱근인 루트 N 까지의 약수만 구하면, 약수들의 합을 알 수 있다니.. func sumOfDivisors(_ n: Int) -> Int { var sum = 0 var i = 1 while i * i
CS/자료구조 2022. 10. 21. 14:04
[알고리즘 스터디 with 케이시] 동적 계획법

정의 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다. Dynamic Programming(DP) 이라고도 부른다. 동적 계획법이 어렵게 느껴지는 원인 중 하나 Dynamic 하지 않고 Programming 과도 관련이 없다. 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다. 두 가지 방법론이 있다. 메모이제이션(Memoization) 타뷸레이션(Tabulation) 메모이제이션 하향식 접근법 동적 계획법에서 작은 문제들의 결과는 항상 같다. 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다. 피보나치 수열이 주로 예시가 됨 위와 같이 있다고 할 때 중복되는 것들이 몇몇 있다. 이미 해결한 문제는 ..
CS/자료구조 2022. 8. 6. 09:07
[알고리즘 스터디 with 케이시] 백트래킹

정의 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다. 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 한다. 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. DFS, BFS 정말 많이 나오는데 코테를 풀 때는 꼭알고 있어야하는 개념이다. 백트래킹의 핵심은 가지치기! 가지치기를 얼마나 잘하느냐가 효율성을 좌우한다. 어떻게 작성할 것인가? 우선, 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머..
CS/자료구조 2022. 8. 6. 09:04
이전 Prev 1 2 3 4 ··· 9 Next 다음