목록알고리즘 (4)

Devlog

[PS:Leetcode] Factorial Trailing Zeroes

거의 2년만에 해보는 PS 포스팅... 문제난이도: medium문제 링크: https://leetcode.com/problems/factorial-trailing-zeroes/description/Given an integer n, return the number of trailing zeroes in n!.Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.0과 10000사이의 수 n이 주어졌을 때 n의 팩토리얼인 n!에서 0이 몇개 들어가 있는지 그 갯수를 구하는 간단한 문제 입니다. (단 n = 0일대 0의 갯수는 0입니다)  Solution 10의 갯수를 새는 방법은 간단합니다. n! = a * 10^b 라면 0의 갯수는 10의 제곱수인 b가 됩니다...
Problem Solving/코딩문제풀기 2024. 4. 23. 01:57
[알고리즘] 이분 탐색의 변종들 (1) - lower/upper bound를 알아보자

이분탐색 알고리즘 공부를 어느정도 해봤다면 누구에게나 친숙한 알고리즘 입니다. 정렬된 배열에서 특정 값의 위치(인덱스 값)을 찾는 알고리즘이지요. 이분탐색을 구현하는 코드는 아래와 같습니다. 해당 값이 존재하면 그 값에 대한 인덱스 값을 출력하고, 없으면 -1을 출력합니다. int process_binary_search(vector& arr, int e) { int n = (int)arr.size(); int left = 0, right = n-1, mid; while(left > 1; if(arr[mid] == e) return mid; else if(arr[mid] > e) right = mid - 1; else left = mid + 1; } return -1; } 이분탐색의 알고리즘은 선택된 값(..
Problem Solving/알고리즘 2023. 3. 26. 04:12
[알고리즘] 강한 연결 요소(2): 타잔 알고리즘

강한 연결 요소 (Strongly Connected Component) 시리즈 1. 코사라주 알고리즘 2. 타잔 알고리즘 3. 2-SAT 소개 지난 챕터 에서는 코사라주 알고리즘의 소개와 증명에 대해서 설명했습니다. 코사라주 알고리즘은 정방향/역방향 이렇게 DFS를 두번 돌려서 SCC를 구하는 방식으로, 구현은 간단하지만 DFS를 두번 돌려야 하고, 그렇기에 코드가 약간 긴 편입니다. 그러나 타잔 알고리즘은 DFS를 단 한번 실행함으로써 모든 존재하는 SCC를 구하게 됩니다. 비록 이해 난이도는 코사라주보다 조금 어렵지만, 코드량이 적은 편이라 응용 문제에서도 쉽게 활용할 수 있는 알고리즘 입니다. 코드는 아래 블로그를 참고해서 파이썬으로 옮겨적었습니다. 코사라주 때는 그냥 알고리즘만 보고 바로 코딩했는..
Problem Solving/알고리즘 2022. 7. 2. 12:26
[알고리즘] 강한 연결 요소(1): 코사라주 알고리즘

강한 연결 요소 (Strongly Connected Component) 시리즈 1. 코사라주 알고리즘 2. 타잔 알고리즘 3. 2-SAT 소개 강한 연결 요소(Strongly Connectioned Component)는 그렇게 잘 알려져 있는 알고리즘이 아니지만 제법 유용하게 쓰일 수 있는 알고리즘 입니다. 그래프에서 정점들 중 일부분이 서로 도달할 수 있는 정점들의 집합을 강하계 연결되었다. 라고 합니다. 강한 연결 요소 알고리즘이란 강하게 연결되어 있는 정점들의 집합의 정보를 구하는 알고리즘 입니다. 크게 코사라주 알고리즘과 타잔 알고리즘이 있습니다. 코사라주 알고리즘이 구현 난이도가 쉽기 때문에 이번 챕터에서는 코사라주 알고리즘 부터 설명합니다. 알고리즘 작동 방식 코사라주 알고리즘의 그래프이 간선..
Problem Solving/알고리즘 2022. 5. 31. 22:53
이전 Prev 1 Next 다음