for_develop for_develop

Algorithm

• [다이나믹 프로그래밍] 문제 이름 : 효율적인 화폐 구성

  Algorithm/유형별 문제 풀기 2021. 12. 22. 13:39

  문제 설명 N가지 종류의 화폐가 있을 때, 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있고, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 입력 조건- 첫째 줄에 N, M이 주어진다. (1

  Read More
• [다이나믹 프로그래밍] 문제 이름 : 바닥 공사

  Algorithm/유형별 문제 풀기 2021. 12. 21. 13:27

  문제 설명 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 입력조건- 첫째 줄에 N이 주어진다. (1

  Read More
• [다이나믹 프로그래밍] 문제 이름 : 개미 전사

  Algorithm/유형별 문제 풀기 2021. 12. 21. 11:52

  문제 설명 여러 개의 식량창고가 존재하고, 식량창고는 일직선으로 이어져 있다. 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있기 때문에 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최대값을 구하는 프로그램을 작성하시오. 입력 조건 - 첫째 줄에 식량창고의 개수 N이 주어진다. (3

  Read More
• [다이나믹 프로그래밍] 문제 이름 : 1로 만들기

  Algorithm/유형별 문제 풀기 2021. 11. 24. 12:06

  문제 설명 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. 1. X가 5로 나누어떨어지면, 5로 나눔 2. X가 2로 나누어떨어지면, 2로 나눔 3. X가 3으로 나누어떨어지면, 3으로 나눔 4. X에서 1을 뺌 정수 X가 주어졌을 때, 위의 연산 4개를 적절히 사용해 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 구하시오. 사용 개념 다이나믹 프로그래밍, 보텀업 방식 문제 해결 아이디어 모든 연산 가능 경우에 대해 생각해봐야 할 것 같은데 너무 많은 것 아니야..? → 맞아! 경우의 수로 모든 경우에 대해 봐야되는거 맞는데 다이나믹 프로그래밍을 사용해서 빠르게 구하는거지! 어차피 최소 연산 횟수 구하는 것이니까! 1. 함수 호출 과정 도식화하기 → 모든 경우의 ..

  Read More