알고리즘

(C++) 백준 11047번 - 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 가장 동전 수를 적게 이용하려면 금액이 큰 동전부터 빼가면서 계산해야 한다. 금액이 오름차순으로 입력되기 때문에 배열의 뒷부분부터 계산해 나가는 식으로 풀이하였다. #include using namespace std; int coins[12]; int n, k, cnt; i..

(C++) 백준 1654번 - 랜선 자르기

문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 매개 변수 탐색을 사용해 풀이하였다. 매개 변수 탐색은 다음의 두 조건을 만족할 경우에 사용할 수 있다. 최적화 문제를 결정 문제로 변경할 수 있는지? 위의 결정 문제로 얻어진 함수가 감소 혹은 증가함수인지? 여기서는 N개를 만들 수 있는 최대의 랜선을 구하는 최적화 문제를 랜선의 길이가 X일 때 랜선의 개수가 N개 이상인가 아닌지 구하는 결정 문제..

(C++) 백준 18870번 - 좌표 압축

문제 링크 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 먼저 입력받은 배열을 sort() 메서드를 사용해서 정렬하고, 그 후 unique()와 erase() 메서드를 사용해서 중복을 제거한다. 마지막으로 lower_bound() 메서드를 사용해서 현재 어느 위치에 존재하는지 알아낸다. #include #include #include using namespace std; vector ..

(C++) 백준 10816번 - 숫자 카드 2

문제 링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 sort() 메서드와 해당 값보다 큰 값이 처음으로 나타는 index를 반환하는 upper_bound() 메서드, 해당 값이 처음으로 나타는 index를 반환하는 lower_bound() 메서드를 사용하면 간단하게 풀 수 있는 문제이다. #include #include using namespace std; int A[500005]; int n,..

(C++) 백준 1920번 - 수 찾기

문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 sort() 메서드와 binary_search() 메서드를 활용하여 간단하게 풀 수 있는 문제이다. #include #include using namespace std; int A[100005]; int n, m; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ci..

(C++) 백준 12852번 - 1로 만들기 2

문제 링크 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 백준 1463번과 마찬가지로 입력이 1일 때 0, 입력 2일 때 1이라는 초기값을 부여해 주고 그 이후에 상황에 맞춰 1씩 더해주는 방식으로 풀이하였다. 그리고 연산의 순서대로 출력을 해야 하므로 1로 가는 경로에 있는 다음 값을 배열에 저장하였다. ex) arr[16] = 8, arr[8] = 4, arr[4] = 3, arr[3] = 1 #include using namespace std; int arr[1000005]; int hist..

(C++) 백준 11659번 - 구간 합 구하기 4

문제 링크 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀이하였다. 처음부터 특정 인덱스까지의 합을 배열에 저장하고, 구간 사이의 합을 구하기 위해 특정 인덱스까지의 합(sum[j-1])에서 구간에 속하지 않는 값의 합(sum[i-2])을 빼는 방식으로 구현하였다. #include using namespace std; int sum[100002]; int num[100002]; ..

(C++) 백준 11726번 - 2xn 타일링

문제 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀이하였다. 2*N 크기의 타일을 채우는 방법은 제일 처음 1*2 크기의 타일을 먼저 채웠을 경우와 제일 처음 2*1 크기의 타일 2개를 먼저 채우고 시작할 경우의 합이다. 즉 2*(N-1) 크기의 타일을 채우는 방법과 2*(N-2) 크기의 타일을 채우는 방법의 합을 구하면 된다. #include using namespace std; int tile[1002]; int..

(C++) 백준 1149번 - RGB 거리

문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 house[x][0]은 x번째 집이 빨간색일 때의 최소 비용, house[x][1]은 x번째 집이 초록색일 때의 최소 비용, house[x][2]은 x번째 집이 파란색일 때의 최소 비용을 저장하도록 하였다. #include #include using namespace std; int hous..

(C++) 백준 2579번 - 계단 오르기

문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 arr[x][0]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟지 않았을 경우, 즉 x-2번째 계단을 밟았을 때로, arr[x][1]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟았을 경우, 즉 x-1번째 계단을 밟았을 때이다. 마지막으로 다이나믹 프로그래밍을 진행할 때 x-2가 인덱스일 때의 값이 필요하므로 초기값으로 ..