멘지의 기록장

난이도 🥇 4 링크 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 풀이과정 해당 문제는 그리디를 사용하는 문제이다. 생각해보면 굉장히 쉽게 풀 수 있는 문제여서 문제 설명에 쓰여진 예시를 보지 않는게 더 도움이 될 거 같다.. 예시 설명에서는 [40 30 30 50] 이라는 값이 있을 때 1) 먼저 40 + 30 = 70 2) 30 + 50 = 80 3) 70 + 80 = 150 이러한 과정으로 결과값을 출력하도록 설명하였는데 이렇게..

난이도 🥈 4 링크 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디 알고리즘을 사용해서 푸는 문제였다. 사실 다른 그리디 문제들과는 달리 A의 수를 재배열하고, B에 있는 수를 재배열하지 말라고 했지만, 그저 'S의 최솟값'을 출력하기만 하면 되기에 둘 다 정렬하여 결과값을 구했다 :) 1) 각각 입력받은 값들을 A와 B 배열에 저장한다. 2) A 배열은 오름차순으로, B 배열은 내림차순으로 정렬한다. ..

난이도 🥇 4 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이과정 해당 문제는 백트래킹을 사용하는 문제이다. 백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 즉, 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상..

난이도 🥈 1 링크 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이과정 해당 문제는 DP를 사용하는 문제이다. DP를 사용하는 전형적인 문제로, 코테에서도 종종 볼 수 있는 문제이다. 아직 알고리즘을 잘 풀지 못하기에 점화식을 찾기 굉장히 어려웠다.. 하지만 생각해보면 굉장히 쉬운 문제이다. 'N개의 카드를 갖기 위해 지불해야하는 최대금액을 출력'하는 문제이기 때문에 2중 for문을 사용하여 전부 비교해보면 된다! 예를 들어 설명하자면 dp..

난이도 🥇 5 링크 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이과정 해당 문제는 DP를 사용하는 문제이다. 처음에 조합을 사용해서 문제를 풀어보려고 하기도 했지만 순서만 다른 경우도 포함되어 어떻게 문제를 풀어야 되나 고민을 하였다. 순서만 다르고 조합이 같은 경우를 중복시키지 않기 위해선 ➡️ 원하는 값이 나올 때까지 사용할 수 있는 동전의 수를 메모이제이션 하면 되는 것이다! 문제에서 주어진 예시를 들어 설명해보자면 3가지 종류..

난이도 🥈 2 링크 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디 알고리즘을 사용해서 푸는 문제이다. 그리디 알고리즘에 대한 설명은 아래 글을 참고하면 좋을 거 같다! https://amepistheo.tistory.com/7 [백준] 1449 : 수리공 항승 (JAVA) 난이도 🥈 3 링크 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이..