홈 › 카테고리 › 프로그래밍 문제

구스타포

토, 2007-02-17 17:17 — 귤

Gustavo는 수를 셀 줄 알지만, 숫자를 1,2,3,4 밖에 쓸 줄 모른다. 게다가 4는 1과 같다고 생각한다. Gustavo는 큰 수를 나타낼 때 자신이 알고 있는 숫자를 더해서 나타낸다. 예를 들어 6은 1+3+2라고 쓴다.

Gustavo와 같은 방식으로 수를 표현한다면 한 수를 몇 가지 방법으로 쓸 수 있는 지 알아내는 프로그램을 만들어보자. 예를 들어 2는 1+1, 1+4, 4+1, 4+4, 2 다섯 가지 방법으로 나타낼 수 있다.
우선 간단히 4와 순서에 대해서는 생각하지 말고 수를 어떻게 1,2,3의 합으로 만들지만 생각해보자. 예를 들어 4는 3+1, 2+2, 2+1+1, 1+1+1+1 네 가지 방법으로 만들 수 있다.

‹ [공지] 이 게시판의 목적과 사용법 다이아몬드 그리기 ›

댓글 보기 옵션

원하시는 댓글 전시 방법을 선택한 다음 "설정 저장"을 누르셔서 적용하십시오.
토, 2007-02-17 17:17 — 귤

하스켈 버전

이런 문제를 배낭 문제 (knapsack problem)이라고 하는 데 정해진 크기 (여기서는 4)의 배낭에다가 각각 다른 크기의 물건 (여기서는 1,2,3)을 집어넣는 방법을 찾는 것과 같기 때문이다. 배낭 문제에 쓸 수 있는 가장 간단한 알고리듬은 큰 순서대로 집어넣는 탐욕법 (greedy method)이다. 그러니까 3, 2, 1 순서대로 집어넣는 것이다.

4의 경우, 먼저 3을 집어넣으면 자리가 1만큼 남는다. 그러면 1만 집어넣으면 3+1. 2를 집어넣으면 자리가 2만큼 남는다. 그러면 2를 집어넣으면 2+2. 여기서 두번째에 2 대신 1을 집어넣으면 1이 남으니까 또 1을 넣는다. 그럼 2+1+1. 처음에 1을 집어넣으면 3이 남고 1을 또 넣고 이렇게 계속하면 1+1+1+1. 이렇게 네 가지 방법을 모두 찾을 수 있다.

이렇게 수를 1,2,3의 합으로 만드는 방법을 찾은 다음에는 각각을 순서대로 늘어놓는 방법을 찾는다. 예를 들어 3+1은 1+3으로도 나타낼 수 있으니 2가지가 가능하고, 2+2는 1가지, 2+1+1은 3가지가 가능하다. 이런 경우의 수들은 수학 공식을 이용하면 간단히 구할 수 있다.

  1. 같은 것이 있는 순열: n개의 대상 중에 같은 것이 p개, q개 있으면 순서대로 늘어놓을 수 있는 경우는 n! / ( p! * q! ) 가지
  2. 중복순열: 2 종류의 대상을 r개를 순서대로 늘어을 수 있는 경우는 2^r 가지

이제 프로그램은 다음과 같이 간단히 작성할 수 있다. 

module Main where

fac 0 = 1
fac n = product [1..n]

numOfCase list = fac (sum list) `div` product (map fac list)

count list 1 r = 2^r * numOfCase (r:list)
count list d r =
    sum $ map (\x -> count (x:list) (d-1) (r-d*x))

        [0 .. r `div` d]

gustavo n = count [] 3 n

main = do
    n <- getLine
    print $ gustavo $ read n

fac은 계승 (factorial)을 구하는 함수다. fac n은 n!을 계산한다. numOfCase는 같은 것이 있는 순열을 계산한다. count에서 list는 앞서 넣은 수들의 개수, d는 이번에 넣을 수, r은 남은 자리다. 4의 경우 count [] 3 4라고 하면, [0.. 4 `div` 3]해서 [0,1]이라는 리스트가 나온다. 즉, 3을 0개 넣는 경우와 1개 넣는 경우를 찾아주는 것이다. 이들 각각에 대해 다시 d가 2일 때 count를 적용시켜 준다. 그리고 d가 1이되면 남은 자리만큼 1을 꽉채우고 numOfCase를 이용해 순서대로 늘어놓는 경우의 수를 계산한다. numOfCase 앞에 2^r을 곱해주는 이유는 1이 1과 4 두 종류가 있기 때문이다. 예를 들어 1+1+1과 같이 1이 세 개 있으면 첫 번째 1을 1로도 쓸 수도 있고 4로 쓸 수도 있으니 2가지가 있고, 두 번 째 1도 2가지, 세 번 째 1도 2가지. 그래서 2*2*2 = 2^3인 것이다.

토, 2010-03-27 19:53 — shakri

탐욕 알고리즘은

탐욕 알고리즘은 문제가 세계적인 최적을 찾는 희망의 각 단계에서 로컬로 최적의 선택의 여지가 만드는 metaheuristic 해결을 다음과 같이 어떤 알고리즘입니다 mcdst.

예를 들어, 외판원 문제에 대한 욕심이 전략은 다음과 같은 알고리즘을 적용 수율 : "각 단계를 방문하여 현재의 도시에 방문하지 않은 가장 가까운 도시". 다른 많은 문제를 들어, 욕심이 알고리즘은 최적의 솔루션을 제작하고, 실패도 최악의 독특한 가능한 솔루션을 생산할 수있습니다. 한 예로 가장 가까운 이웃이 알고리즘은 위에서 언급한입니다 : 도시의 각 전화 번호에는 가장 가까운 이웃에 대한 추론 도시 사이의 거리의 임무 고유의 최악의 투어를 생산하고있습니다 itil v3 certification.

겨우 25 센트, 10 센트, 그리고 4 센트짜리 동전이 동전을 예를 들어 상상해보십시오. 욕심이 알고리즘은 41 센트로 변경할 이후 수 없을 것이라고 한 25 센트짜리 동전 하나는 10이 6 센트의 잔액이 4 센트짜리 동전을 사용하는 것은 불가능하다 센트 동전을 사용하여 짓는했다. 사람 또는보다 정교한 알고리즘을 한 반면에 25 센트와 41 센트짜리 동전을 변경할 4 4 센트짜리 동전을 변경할 수있습니다 mcitp.

화, 2010-09-07 19:39 — john100998

함수형 언어를

함수형 언어를 실용적으로 사용한다면 몇 가지가 있을 듯 합니다. 첫째는 함수형 언어로 직접 개발하는 것이지만 이것은 pass4sure 642-971 대부분의 현장에서 불가능한 방법이죠. 둘째는 일요일 밤 토론에서 제영희님이 말씀하신 것인데 기존 프로젝트의 일부를 함수형 언어로 대체하는 것입니다. 로그 파서를 만든다든지 정책 관리 부분을 만든pass4sure HP0-J22 다든지 하는 것이겠죠.또다른 방법은 함수형 언어를 읽을만한 C++ 코드로 만들어주는 컴파일러를 개발하는 것입니다. 템플릿 등을 이용해서 함수형 프로그래밍을 하는 기법들은 Effective C++ 등의 책에 많이 소개되어 있지만 워낙 그 방법들이 pass4sure HP0-S21 기묘하고 어려워서 배보다 배꼽이 더 큰 경우가 있죠. 함수형 프로그래밍을 도입하는 이유는 프로그래밍을 쉽게하기 위해서인데 그런 기법들 자체가 지극히 난해하니까요. Haskell을 C++로 바로 바꿔주는 것은 좀 어려울 듯하고 C++과 비슷한 스크립트를 pass4sure JN0-100 만들면 배우기도 쉽고 컴파일러도 만들기 쉬울 것 같습니다.