Binary Journey

당장 눈 앞의 최적의 상황만을 좇는 알고리즘, 어느 조건에서는 최적의 해 보장 def greedy(n): result = 0 result += int(n / 500) n %= 500 result += int(n / 100) n %= 100 result += int(n / 50) n %= 50 result += int(n / 10) print(result) if __name__ == "__main__": n = int(input()) greedy(n) def greedy(n): result = 0 div, mod = divmod(n, 500) result += div n = mod div, mod = divmod(n, 100) result += div n = mod div, mod = divmod(n, 5..

35강에 대한 리뷰 일반적인 경우 빠르게 작동하며 간단한 구조를 가진 문자열 매칭 알고리즘이다. 해시 기법을 이용하여 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다. 동일한 해시값이 발생하는 이른바 충돌이 발생할 수도 있는데 발생률이 낮아 무시하고 지나간다. 보통 공식은 긴 글 해시값 = 2 * (긴 글 해시값 - 가장 앞 문자의 값) + 새롭게 들어온 문자의 값 def find_string(parent, pattern): parent_len = len(parent) pattern_len = len(pattern) parent_hash = 0 pattern_hash = 0 power = 1 for i in range(parent_len - pattern_len + 1): if i == 0: f..

34강에 대한 리뷰 https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12363 알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지 지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요.... www.inflearn.com 대표적인 문자열 매칭 알고리즘 모든 경우를 비교하지 않아도 부분 문자열을 찾아줌 접두사와 접미사의 개념을 활용함: 접두사와 접미사가 일치하는 최대 길이를 구함 ** Python def make_table(pattern): pattern_len = len(pattern) table = [0 for i in r..

33강에 대한 리뷰 https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12362 알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지 지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요.... www.inflearn.com 하나 씩 확인하는 가장 단순한 알고리즘 단순히 모든 위치에서 모든 문자열이 같은지 확인하므로 O(N*M)의 시간복잡도를 가짐 효율적이진 않음 ** Python def find_string(parent, pattern): parent_len = len(parent) pattern_len = len(patter..

인프런 32강에 대한 리뷰다 https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum [무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의 알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명 www.inflearn.com 이분 매칭은 쉽게 말하자면 A와 B라는 두 집합을 가장 효율적으로 매칭하는 방법의 알고리즘이다. 네트워크 플로우 때 음의 유량을 응용한 방법이라고도 볼 수 있다. 위 그림을 예를 들어 임의의 사람 1, 2, ..

인프런 29강에 대한 리뷰이다. https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12358 알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지 지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요.... www.inflearn.com 네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 표현 방식은 유랑/용량이다. 정체 현상없이 최대 유량을 보내야 한다. (최대 유량 문제, Max Flow) 최대 유량 문제는 각 간선에 정해진 용량이 있을 때 A에서 B로 최대로 보낼 수..

인프런 강의 28강에 대한 리뷰이다 https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12357 알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지 지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요.... www.inflearn.com 강한 결합 요소는 그래프 안에서 강하게 결합된 정점 집합을 말한다. 사이클이 발생하는 경우 그 집합은 무조건 강한 결합 요소(SCC)에 해당한다고 한다. SCC 로 대표적인 알고리즘은 코사라주 알고리즘과 타잔 알고리즘이 있는데 강의에서는 타잔 알고리즘을 소개하고 있다. (코사라주 알고리즘이 ..

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 떄 순서를 결정해주는 알고리즘이다. 위상정렬은 여러 개의 답이 존재할 수도 있고 사이클이 발생하는 경우 수행이 불가능하다는 특징이 있다. 위상 정렬 수행으로는 스택과 큐를 사용하는 데 큐로 더 고급적인 수행이 가능하다고 인강에선 큐를 이용하여 소스를 작성하였다. 순서로는 진입차수가 0인 정점을 큐에 삽입 큐에서 원소를 꺼내어 연결된 모든 간선 제거 간선 제거 이후 진입차수가 0이 되는 정점을 큐에 삽입 큐가 빌 때까지 2,3번 과정 반복 - 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다는 것 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과임 위 그림을 표로 나타내면 정점 1 2 3 4 5 6 7 진입차수 0 1 1 1 1 2..

지난번 배운 데이크스트라 알고리즘과 비슷하다. 데이크스트라는 한 정점에서 모든 노드로 향하는 가장 최단 거리를 구하는 것이고 플로이드 알고리즘은 모든 노드에서 모든 노드로 가는 최단 거리를 구한다는 점에서 약간의 차이점이 있다. 위 설명이 이해가 가기 어렵겠지만 예를 들어 문래동, 목동, 화곡동, 신대방동 이렇게 네 곳이 있을 때 문래동을 경유하는 최단 거리, 목동을 경유하는 최단거리, 화곡동을 경유하는 최단 거리, 신대방동을 경유하는 최단거리를 구한다고 생각하면 된다. 위 노드에 대해 코드를 작성하자면 ** C++ #include int number = 4; int INF = 1000000000; // 자료 배열 초기화 int a[4][4] = { { 0, 5, INF, 8 }, { 7, 0, 9, I..

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12354 알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지 지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요.... www.inflearn.com 인프런 25강에 대한 리뷰다. 데이크스트라 알고리즘은 dp (dynamic programming)을 이용한 최단 경로 탐색 알고리즘이다. 그리드 알고리즘으로 분류되기도 한다. (매번 가장 적은 비용의 노드를 선택해서 정렬하기 때문) * 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. ..