알고리즘

문제 링크 : https://www.acmicpc.net/problem/14501 출처 : 삼성 SW 역량테스트 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 ..

Backtracking(되추적) 알고리즘이란 큰 공간에서 하나의 해를 찾아가는 도중 올바른 해가 아니여서 막히면 다시 돌아와서 해를 찾아가는 기법이다. Backtracking은 DFS 와의 차이를 비교하며 살펴보면 이해하기 더 쉽다. DFS(Depth First Search, 깊이우선탐색) DFS, 깊이우선탐색은 그래프에서 root를 먼저 방문한 뒤 그 root의 후손들을 방문하면서 가장 깊숙히 위치하는 노드에 닿을 때까지 순회하는 방법이다. 즉, 트리 순회 중 preorder(루트 -> 왼 -> 오) 방식을 사용하고 있는 것이다. DFS의 c++ 수도 코드와 python 코드를 살펴보자 void depth_first_tree_search(node v) { node u; // 자식 노드 visit v; ..

문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 게임의 룰은 다음과 같다. 1. 숫자가 쓰인 카드들은 N X M 형태, 이때 N은 행의 개수, M은 열의 개수를 의미 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 함 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 함 카드들이 N x M 형태로 놓여있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오. 입력 조건 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 ..

문제 큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 1) 배열의 특정한 인덱스에 해당하는 수가 K번을 초과하여 더해질 수 없는 것이 특징 2) 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주 ex) 2,4,5,4,6의 배열 , M = 8, K =3 큰 수의 법칙에 따라 6 + 6+ 6 + 5 + 6 + 6+ 6+ 5 = 46 입력 조건 첫째줄에 N(2