전체 글 (79) 썸네일형 리스트형 동적 프로그래밍 basic 문제-이항계수(Binomial Coefficient) - DP1 동적프로그래밍(Dynamic Programming)이란? 에서 동적프로그래밍이 무엇인지 알아보았고 동적 프로그래밍 문제를 해결하는 방법 에서는 dp 문제를 어떻게 접근해서 풀어야 하는지 설명하였다. 여기서는 기본적인 dp 문제를 풀어보면서 감을 익혀보자. 이항계수((Binomial Coefficient) 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 주어진 크기의 (순서 없는) 조합의 가짓수라고 정의되어 있다. 즉, 전체 집합에서 원소의 개수 n에 대해 r개의 아이템을 뽑는 이항계수(조합의 수)는 수학에서 다음과 같이 정의된다. 공식에 대한 자세한 설명은 생략한다. 이것을 재귀로 풀면 다음과 같다. 1 2 3 4 5 6 int binomial(int n, int k) .. 동적 프로그래밍 문제를 해결하는 방법? 동적프로그래밍(Dynamic Programming)이란? 에서는 동적프로그래밍 개념을 알아 보았다. 여기서는 동적프로그래밍으로 문제를 해결하는 방법에 대해서 설명한다. 동적프로그래밍 문제를 풀기위한 단계는 다음과 같다. step1. 요놈이 동적프로그래밍(DP) 방식으로 풀수 있을지 없을지부터 구분해라. 문제를 만나면 DP로 분류되는 문제인지 판단해야 한다. DP로 분류될수 있는 문제는 몇가지 특성이 있는데 문제의 해가 중복되는 하위문제(subproblems) 해를 사용하여 풀 수 있는 (Overlapping Subproblems) 특성이 있는지 또는 문제의 최적 해가 그 하위 문제의 최적 해로부터 얻을 수 있는 최적 하부 구조를 갖는 문제(Optimal Substructure)를 갖고 있는지 확인해라. .. [그래프]길찾기 bfs 알고리즘(maze algorithm) 자료구조 그래프에서 모든 정점을 순회하기 위한 방법으로 너비우선탐색(BFS, Breadth First Search) algorithm 과 깊이우선탐색(DFS, Depth First Search) 알고리즘을 알아 봤었다. 이 bfs 와 dfs 알고리즘은 길찾기 (미로 탈출) 에도 유용하게 사용되는데 이 post 는 bfs 를 통해 길찾는것을 설명하겠다. 우선 그림 1과 같은 미로가 있다고 가정하자. 설명을 빨리 하기위해 매우 단순한(?) 미로를 선택하였다. 미로를 자료로 표현하기 위해 graph 로 표현할수 있지만 행렬(matrix)로 도 가능하다. 여기서는 행렬로 하겠다. 7X7 미로인 위 그림을 행렬로 표현하면 다음과 같다. 0 1 2 3 4 5 6 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0.. [Stack]표현식에서 균형 잡힌 괄호 문제(balanced parentheses in an expression) 글이나 수학식을 표현하기위해 괄호 (ex. { , [, ( ) 등을 많이 사용한다. 보통 열린 괄호가 ( 가 있으면 순서에 맞게 닫힌 괄호가 있어야 하는데 이것을 우리는 균형잡힌 괄호(balanced parentheses )라고 얘기한다. 즉 [()]{}{[()()]()} 표현식은 열린, 닫힌 괄호들이 균형잡힌 형태로 표현된것이고 [(]) 는 두번째 ( 다음에 닫힌 괄호 ) 가 없기 때문에 균형잡힌 형태라고 볼 수 없다. Examples of balanced expression (()) {(([]))} {{}}[] [](){} {{}}{}()[] Examples of unbalanced expression {() [][]) }}}} ((() [{](){} 그럼 표현식 E 가 주어지고 그 표현식이 균형이 .. 호너의 법칙(Horner's method) 호너의 법칙은 영어로 Horner's rule (or Horner's method, Horner's scheme)라고 불리는데 다항식을 푸는데 계산량을 줄일수 있는 방법이다. 일반적으로 그림1과 같은 다항식이 있다고 가정하면 차수가 가장 높은것부터 낮은것까지 하나씩 계산하면서 모두 더해주면 된다. [출처] Horner`s Rule for Polynomial Computation 예를들어 5x4 + 2x3 – 3x2 + x – 7 가 있고 x = 3이라고 하면 그림2처럼 계산되고 결과 값은 428이 된다. 이 방법으로 프로그래밍하면 다음과 같고 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3.. 라빈 카프 문자열 매칭 알고리즘(Rabin-Karp String Matching Algorithm) 라빈 카프 문자열 매칭 알고리즘(Rabin-Karp String Matching Algorithm)은 문자열 S가 있고 찾으려는 패턴 P가 있을때 S문자열에 패턴 P가 있는지 없는지 문자(char)를 하나씩 비교하는 방식이아닌 해싱된 값을 비교하는 방식을 사용한다. 해싱이 무엇인지 잘 모르면 우선 해시테이블(Hash Table) 자료구조를 선행학습해야 한다. 그럼 해싱함수는 무엇이고 어떤 절차로 해싱값을 서로 비교하면서 문자열에 패턴이 있는지 확인할수 있을까? 해싱으로 비교하는 방법은 매우 심플한데 문자열 S와 패턴 P가 아래처럼 있다고 했을 때 문자열(S) = "THISISATESTTEXT" 패턴(P) = "TEST" P를 해싱한 Hp 값을 먼저 구하고 S문자열을 인덱스(i) = 0부터 순차적으로 증가.. 나이브 문자열 매칭 알고리즘 (Naive String match algorithm) 패턴 검색은 컴퓨터 과학에서 중요한 문제이다. 패턴 검색이 필요한 사례들은 매우 많은데 메모장, 파일, 브라우저 또는 데이터베이스에서 문자열을 검색 할 때 패턴 검색 알고리즘으로 검색 결과를 표시하는 것이 그 예이다. 문제는 매우 긴 문자열에서 내가 찾고자 하는 문자열(패턴)을 어떻게 빠르고 정확하게 찾아낼수 있을까? 이다. 문자열에서 패턴을 검색하기 위해 다양한 알고리즘들이 있는데 그 중 나이브 문자열 매칭 알고리즘 (Naive String match algorithm)은 문자열 처음부터 끝까지 우리가 찾고자 하는 패턴과 일치하는지 하나씩 비교해가면서 단순 무식하게 문자열을 찾는다. [출처] https://apprize.info/science/algorithms_2/7.html 예를들어 아래 표처럼 문.. 집합 덮개 문제(Set Cover Problem) [출처 : 위키백과] 집합 덮개 문제(set cover problem)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다 N개의 원소를 가진 집합 U가 주어진다면 U의 부분집합(subsets)들은 S = {S1, S2…,Sm} 말하고 모든 부분 집합 Si는 관련된 비용(cost)을 갖는다. S의 부분집합들을 합집합하여 U의 모든 요소를 커버할수있도록 해야 한다면 이때 선택되는 부분집합의 최소 비용 집합을 찾아야 한다. 집합 덮개 문제(.. 이전 1 2 3 4 ··· 10 다음
