✔ 문제 난이도 : 골드5 🥇 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 N개의 물건이 주어질때 각 물건은 무게 W와 가치V를 가지는데, 해당 물건을 배낭에 넣어서 가면 V만큼 즐길 수 있습니다. 하지만 K만큼의 무게만 넣을 수 있는 배낭만 들고 다닐 수 있습니다. 이때 최대한 즐거운(가치가 높은) 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제..
🤔 해시?, 해시 테이블(Hash Table)? 해시 테이블을 알아보기 전에 해시(Hash)에 대해서 알아보겠습니다. 📌해시(Hash) 임의의 길이의 데이터를 고정된 길이의 값으로 매핑한 값을 말하며 해시 함수에 의해 매핑됩니다. 이때 매핑 전 원래 데이터를 키(Key), 매핑 후 고정된 길이의 값을 해시, 해시값(hash value) 매핑하는 과정을 해싱(hashing)이라고 합니다. 해시 함수에 의해 매핑된 해시값은 배열의 인덱스로 사용되고, 인덱스를 사용하여 값을 저장하거나 검색하게 됩니다. 📌 해시 테이블(Hash Table) '저장된 자료의 양에 상관없이 평균 상수 시간 작업이 가능하게 할 수는 없을까?' 라는 질문을 시작으로, 자료를 검색, 삽입, 삭제하는 데 평균 O(1) 시간(상수시간)이 ..
✔ 문제 난이도 : 실버1 🥈 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net NxN 게임판에 수가 적혀 있습니다, 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가야 합니다. 각 칸에 적혀 있는 수만큼 오른쪽 또는 아래쪽으로 갈 수 있습니다. ( 아래로 점프, 오른쪽으로 점프 두 경우만 존재 ) 가장 왼쪽 위 칸에서 가장 오른쪽 아래칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 문제입니다. ✔ 문..
✔ 문제 난이도 : 골드5 🥇 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net T : 상담하는데 걸리는 기간 P : 상담 했을 때 받을 수 있는 금액 N이 주어젔을 때 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하는 문제입니다. ✔ 문제 풀이 단순하게 1일~N일, 2일~N일... 모든 경우를 계산하게 되면..
✔ 문제 난이도 : 실버1 🥈 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 주어진 수열과 연사자를 사용하여 최댓값과 최솟값을 구하는 문제입니다. ✔ 문제 풀이 수열과 연산자들의 조합으로 최대값과 최솟값을 구하기 위해서는 모든 경우의 조합을 탐색하여 검사해야 한다고 생각했습니다. 그러기 위해서는 DFS처럼 재귀호출을 통해 주어진 수열과 연산자를 모두 사용한 조합을 우선적으로 구하고(깊..
✔ 문제 난이도 : 골드5 🥇 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 주어진 괄호열에 대해서 올바른 괄호일 때 주어진 조건에 맞게 계산하는 문제입니다. ✔ 문제 풀이 알고리즘 문제를 조금 풀어보았다면 괄호를 보자마자 stack을 떠올릴 수 있을 것입니다. 하나의 괄호는 열고 닫는 괄호로 이루어져 있습니다, 이러한 점을 stack의 LIFO의 특징을 활용하여 괄호에 하나씩 접근할 수 있게 됩니다. ( ( ) [ [ ] ] ) 하지만..
