본문 바로가기

Programming11

[백준 1727번 문제] 커플 만들기 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 문제를 이해하는데 다소 어려움이 있었는데, 문제를 요약하면 다음과 같습니다. 커플의 수는 최대여야 한다. 즉 남자의 수 n, 여자의 수 m이 있을 때, 커플의 수 = min(n, m)이 된다. 커플을 만들었을 때, 성격의 차이를 각각 구하고, 이 값을 누적한다. 누적한 값이 최소가 되도록 하라. 다이나믹 프로그래밍 문제입니다. 입력을 두 배열 men, wome.. 2021. 9. 26.
[백준 2042번] 구간 합 구하기 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다. 기본적인 설명은 여기를 참고해 주세요. 세그먼트 트리의 기본적인 문제입니다. 한 가지 유의할 점이 있다면, 값을 수정할 때입니다. b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다. 따라서 차이값 differenc.. 2021. 9. 25.
세그먼트 트리 다음과 같은 문제를 생각해 봅시다. 배열 arr에는 수많은 int형 정수가 들어 있다. arr의 크기 n은 최대 10만이며, 각 정수는 1000 이하의 크기를 가진다. 배열이므로, 당연히 arr의 모든 원소는 인덱스가 정해져 있다. 인덱스는 0부터 시작한다. 총 m줄에 걸쳐 구간이 주어질 때, 주어진 구간합을 출력하는 코드를 작성하시오. (n 2021. 9. 25.
[백준 15401번] 퇴사 난이도: 실버 4 문제 링크: www.acmicpc.net/problem/14501 출처: 삼성전자 SW 역량 테스트 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 지금까지 누적 얻은 이익을 매번 다시 계산하지 않고, 이전에 계산해서 저장해 놨던 값을 꺼내어 이용하면 됩니다. 이런 문제는 뒤에서부터 접근하면 보다 쉽게 풀 수 있습니다. 위 사진에 있는 예시를 기준으로 설명하겠습니다. N+1일 후에 퇴사를 합니다. 따라서 N일까지 일할 수 있는지 여부를 우선 체크해야 합니다. 주의할 점은 7일차에 하루가 걸리는 상담을 할 경우 7 + 1 = 8이지만, 상담을 할 수 있다는 점입니다. 따라서 x일차 + y일.. 2021. 3. 11.
[백준 12865번] 평범한 배낭 난이도: 골드 5 문제 링크: 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 오늘 공부한 다이나믹 프로그래밍을 응용해 보기 위해 풀어 본 문제입니다. 얼핏 보면 간단해 보이지만, 두 개의 변수 W와 V를 고려해야 해서 쉽지 않습니다. 제가 예전에 풀었던 최소 편집 거리 문제와 비슷하다는 느낌을 받았습니다. 나름 유명한 문제인데, Google 등에 knapsack 문제라고 검색해 보시면 이 문.. 2021. 2. 6.
[백준 1958번] LCS 3 난이도: 골드 3 문제 링크: www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net 앞에서 몇 번 다루었던 LCS 문제입니다. 차이점이라면 이번에는 문자열 3개를 비교한다는 점! 따라서 dynamic programming 기법을 이용하기 위한 array 역시 3차원을 사용합니다. 기본적인 LCS algorithm에 대한 설명은 이 글을 참고하시기 바랍니다. 주의할 점은 문제에서 LCS가 Longest Common Subsequence를 뜻한다고 명시하고 있습니다. 즉, 연속된 문자만을 인정한다는 의미입니다... 2020. 11. 15.

티스토리툴바