반응형
Algorithm
[Dynamic Programming] 배낭 문제(Knapsack Problem)
[Dynamic Programming] 배낭 문제(Knapsack Problem)
2020.07.17설명 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제다. 예를 들어 설명해보자. 한 여행가가 여행을 떠나려고 한다. 여행가가 가지고 가는 배낭에는 담을 수 있는 무게의 최댓값이 정해져 있고 배낭에 넣을 수 있는 짐에는 각각의 무게(W)와 가치(V)가 정해져 있다. 이 여행가가 배낭의 무게를 최대한 꽉 채우되 가치의 합이 최대가 되도록 짐을 고르려면 어떻게 해야 할까? 여기서 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우 두 가지로 나눌 수 있다. 짐을 쪼갤 수 있는 분할 가능 배낭 문제(Fractional Knapsack Problem) - 그리디 알고리즘 짐을 쪼갤 수 없는 배낭 문제(Knapsack Problem) - 동적 계획법(Dynami..
[C++, Golang] 12865번: 평범한 배낭
[C++, Golang] 12865번: 평범한 배낭
2020.07.17해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 ..
[C++, Golang] 2798번: 블랙잭
[C++, Golang] 2798번: 블랙잭
2020.07.14해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net 문제 설명 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근..
[C++, Golang, Java] 14888번: 연산자 끼워넣기
[C++, Golang, Java] 14888번: 연산자 끼워넣기
2020.07.10해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 문제 설명 N개의 수로 이루어진 수열 A1, A2,..., AN이 주어진다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷..
[C++, Golang] 11729번: 하노이 탑 이동 순서
[C++, Golang] 11729번: 하노이 탑 이동 순서
2020.07.10해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 설명 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑..
[C++, Golang] 2012번: 등수 매기기
[C++, Golang] 2012번: 등수 매기기
2020.07.08해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 설명 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당 조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부..
[C++] 2447번: 별찍기 - 10
[C++] 2447번: 별찍기 - 10
2020.07.07해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 문제 설명 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27,...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는..
[Golang] 2447번: 별찍기 - 10
[Golang] 2447번: 별찍기 - 10
2020.07.07해당 글의 내용은 최적의 알고리즘이 아닌 글쓴이의 주관적인 풀이입니다. 더 좋은 풀이가 있다면 댓글로 피드백 부탁드립니다(__) 링크 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 문제 설명 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27,...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는..
[C++] 주식 가격
[C++] 주식 가격
2019.09.15링크 https://programmers.co.kr/learn/courses/30/lessons/42584# 코딩테스트 연습 - 주식가격 | 프로그래머스 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 programmers.co.kr 문제 설명 초 단위로 기록된 주식 가격이 담긴 배열 prices가 ..
[C++] x만큼 간격이 있는 n개의 숫자
[C++] x만큼 간격이 있는 n개의 숫자
2019.09.10링크 https://programmers.co.kr/learn/courses/30/lessons/12954# 코딩테스트 연습 - x만큼 간격이 있는 n개의 숫자 | 프로그래머스 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요. 제한 조건 x는 -10000000 이상, 10000000 이하인 정수입니다. n은 1000 이하인 자연수입니다. 입출력 예 x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] programmers.co.kr 문제 설명 함수 solution은 정수 x와 자연수 n을 입력받아,..
[Golang] x만큼 간격이 있는 n개의 숫자
[Golang] x만큼 간격이 있는 n개의 숫자
2019.09.10링크 https://programmers.co.kr/learn/courses/30/lessons/12954# 코딩테스트 연습 - x만큼 간격이 있는 n개의 숫자 | 프로그래머스 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요. 제한 조건 x는 -10000000 이상, 10000000 이하인 정수입니다. n은 1000 이하인 자연수입니다. 입출력 예 x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] programmers.co.kr 문제 설명 함수 solution은 정수 x와 자연수 n을 입력받아,..