알고리즘 개념 특정 제한 조건 내에서 가장 높은 가치를 얻을 수 있는 선택 조합을 찾는 문제를 해결하기 위한 알고리즘즉, 조합 최적화 문제의 일종 배낭문제가 대표적 -  담을 수 있는 최대 무게가 정해진 배낭과 함께     각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때,     배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제  알고리즘 종류이때, 주어진 아이템의 분할 가능 여부에 따라 두 종류로 나뉜다.이번 블로그 글에서는 분할 불가한 0/1 Knapsack을 다룰 것이다.알고리즘 종류해결 방법특징(아이템 분할 여부) 0/1 Knapsack 동적 계획법, 백트레킹아이템 분할 불가  Fractional Knapsack 탐욕적 접근법아이템 분할 선택 가능 1..

문제https://www.softeer.ai/practice/6275  사용 알고리즘구현, 시뮬레이션 풀이고려사항1. 출발점, 출발방향 찾기 - 연결된 곳이 1개인지2. 다음 방향 설정 후기1.이 문제에서는 출발점 탐색과 경로 이동 두 로직으로 나뉜다.2. 우선, 출발점은 현재 위치에서 상하좌우를 살피며 이어진 곳이 1곳인지, 2곳인지 확인하여 찾는다.이어진 곳이 1곳인 경우 출발점으로 시작한다.이때, 이어진 곳의 방향을 함께 확인하여 출력한다.3. 이후 경로 이동을 진행하는데 앞으로 전진 시 2칸씩 이동한다.이때, 2칸씩 이동하더라도 다음 방향 탐색은 1칸을 기준으로 진행해야한다.#.#과 같이 앞으로 진행은 안되지만 돌아서 2칸 앞에 놓인 곳을 지나가게 되는 경우가 존재하기 때문이다.처음에는 2칸을 기..

문제N과 M(9) : https://www.acmicpc.net/problem/15663N과 M(10) : https://www.acmicpc.net/problem/15664N과 M(11) : https://www.acmicpc.net/problem/15665N과 M(12) : https://www.acmicpc.net/problem/15666 사용 알고리즘Backtracking 풀이후기1. 이번 시리즈의 keypoint는 중복되는 숫자 처리이다. N과 M 시리즈 1(1 ~ 4)와 로직이 비슷하나 동일 숫자의 중복 처리가 더해져 조금 더 까다로웠다.2. 백트레킹 유형을 통해 중복 수를 활용한 순열과 조합 등의 방식을 직접 구현 할 수 있었다. 15663. N과 M (9) 1. 이 문제가 이후 문제 풀이에..

문제N과 M(5) : https://www.acmicpc.net/problem/15654N과 M(6) : https://www.acmicpc.net/problem/15655N과 M(7) : https://www.acmicpc.net/problem/15656N과 M(8) : https://www.acmicpc.net/problem/15657 사용 알고리즘Backtracking 풀이후기1. 이번 시리즈는 N과 M 시리즈 1(1 ~ 4)와 로직은 동일하나 연속된 수가 아닌 입력받은 수로 진행하는 문제이다.때문에 로직에 큰 변화없이 입력받은 수를 가지고 저번과 동일하게 진행하였다.2. 백트레킹 유형을 통해 입력받은 수로 순열과 조합 등의 방식을 직접 구현 할 수 있었다.15654. N과 M (5) 1. 이 문제..

문제https://www.acmicpc.net/problem/15649https://www.acmicpc.net/problem/15650https://www.acmicpc.net/problem/15651https://www.acmicpc.net/problem/15652 사용 알고리즘Backtracking 풀이후기1. 이 문제 시리즈는 큰 틀은 비슷하고 조건에 따라 약간의 변화를 추가한 백트레킹 문제이다.백트레킹은 주로 들어가기 전에 해준 처리를 나와서 초기화 시키며 진행하는 방법을 사용한다.2. 백트레킹 유형을 통해 순열과 조합 등의 방식을 직접 구현 할 수 있었다. 15649. N과 M (1) 1. 이 문제가 이후 문제 풀이에 가장 기초 틀이 되는 문제이다.2. 1부터 N까지 자연수 중에서 중복 없이 ..

문제https://www.acmicpc.net/problem/20500 사용 알고리즘DP 풀이고려사항1. 1과 5로만 구성된 수인지2. 15의 배수인지 후기1. 이 문제의 경우 가능한 수의 범위가 크기 때문에 DP로 진행하였다.2. 우선, dp배열에는 digit 자리 숫자 중에서 각 자리 수가 1 또는 5로만 구성되며,    15로 나눈 나머지가 mod15인 경우의 수를 저장한다.    dp[0][0]을 1로 초기 세팅을 진행한다.3. 이후 자리수를 늘리며 이전 자리 수까지의 숫자들에서    15로 나눈 나머지 값을 기반으로 새로운 자리 수를 추가했을 때 나머지를 계산한다.    - 현재 나머지 mod15에 1 또는 5의 숫자를 추가하여 새로운 나머지를 계산한다.    - 이전 자리 수까지 mod15였던..