케이스윔의 개발 블로그

문제 정의N+1일째 되는 날 퇴사하기 위해서 남은 N일 동안 최대한 상담을 많이해서 얻을 수 있는 이익을 구하는 문제이다. 매일 하루의 상담일정이 있는데 각 상담에 소요되는 기간이 다르기 때문에 가장 많은 이익을 가져다주는 상담일정을 짜야한다.문제출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14501) 문제 풀이이 문제도 이전에 풀었던 문제와 마찬가지고 N이 15보다 작기때문에 완전탐색을 통해 모든 경우를 탐색해봐야 한다. DFS를 수행해서 여러가지 경우를 탐색해보면 될 것 같다. i번째 날의 상담을 하게 된다면 i일로부터 T[i]일 이후의 상담으로 탐색해야한다. 이런식으로 DFS+백트래킹을 통해서 모든 경우의 수익을 계산하고 최대 수익을 저장하도록 한다.(+ 201..

문제 정의n개의 수로 이루어진 수열과 덧셈(+), 뺄셈(-), 곱셈(x), 나눗셈(÷) 중에서 n-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14888) 문제 풀이지금 내가 풀고 있는 문제들이 전부 삼성 sw 역량 테스트 문제집에 있는 문제들인데, 왠지 다 비슷한 방식으로 푸는 문제인 것 같다. 일단 대부분의 문제가 완전 탐색으로 풀 수 있었는데 이 문제에서도 N이 2이상 11이하이므로 완전 탐색을 하더라도 시간이 많이 소요되지않는다. 어떠한 연산자가 들어왔는지를 저장해놓은 다음, 연산자를 순서가 있는 n-1개로 나열할 수 있는 경우의 수를 구해야 한..

문제 정의1~49의 숫자 중에서 k(k>6)개의 숫자를 골라 집합을 만들고, 그 집합에서 6개의 숫자조합을 만드는 모든 방법을 출력해야 한다. 문제 출처: 백준 온라인 저지 (https://www.acmicpc.net/problem/6603) 문제 풀이k개의 숫자 중에서 6개의 숫자를 고르는 모든 방법을 구하고, 그 방법에 해당하는 숫자를 출력해야 한다. 사실 이 문제는 다른 문제를 풀던 와중에 m개 중에서 n개를 고르기와 같은 경우를 어떻게 찾아야 할지 해결을 하지 못해 찾아보다가 풀게 된 문제다. 이러한 문제를 풀 때는 DFS에서 백트래킹을 응용해서 풀어야 한다. 주어진 집합 k개 숫자는 서로 다 이어져 있는 그래프라고 생각을 하고 DFS를 하다가 6개가 되면 하나의 방법을 찾은 것이고, 출력한다. ..

문제 정의N명이 주어졌을 때, N/2명으로 두 팀을 나눠야 한다. S[i][j]는 i번 사람이 j번 사람과 같은 팀에 속했을 때의 능력치를 뜻하는데, 두 팀의 능력치 차이가 최소가 되는 경우를 구해야 한다. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14889) 문제 풀이 N이 최대 20이므로 완전탐색을 통해 N/2명의 팀을 짜는 모든 경우를 탐색해도 시간이 오래 걸리지 않는다. 완전 탐색을 통해서 가장 비슷한 능력치를 가지는 쌍을 구하도록 한다. 앞서 이 문제를 풀기 전 로또 문제를 풀었던 방식을 응용해서 N/2명의 두 팀을 나눌 수 있다. DFS를 통해서 N/2명이 되었을 때 그 팀의 능력치를 구하고, N/2명에 속하지 않은 다른 팀원들이 속하는 팀의 능력..

오늘 공부할 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘도 하나의 정점으로부터 다른 정점으로의 최단 거리를 구하는 알고리즘인데, 다익스트라 알고리즘과 다르게 cost가 음수일 때도 사용을 할 수 있다. 벨만 포드의 점화식을 통해서 어떻게 cost가 음수일 때도 고려해서 최단 거리를 구할 수 있는지 보도록 하겠다. 우선 base가 되는 식은 d(1)(v, u)=length(v, u) 이다. 첫 괄호의 1은 1개의 이하의 간선을 의미하고, d(1)(v,u)는 한개 이하의 간선을 거쳐 v에서 u로 가는 최단 경로의 cost를 뜻한다. length(v, u)는 v에서 u로 가는 edge의 cost를 담고 있으며, 이 경우 v에서 u로의 edge 값이 최단 경로의 c..

문제 정의N*N의 동굴의 [0][0]번 칸에서 시작해서 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 칸마다 도둑루피가 있는데, 도둑루피의 크기만큼 소지금을 잃게 되는데 최소한의 금액을 잃으며 동굴 건너편까지 이동을 해야 한다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/4485)문제 풀이최단경로 문제에서는 다익스트라 알고리즘을 그대로 따라 해보는 정도였다면 이 문제는 다익스트라를 이용해서 어떻게 최단 경로를 구할 수 있는지를 생각해볼 수 있다. 다익스트라에서 한 정점에서 다른 정점으로의 최단거리를 구할 때 cost를 비교하여서 구했다. 이 문제에서는 최소한의 금액을 잃으며 이동해야하므로 다음 칸의 도둑루피의 크기만큼이 그 칸으로 이동하기..

문제 정의방향그래프가 주어질 때 주어진 시작점에서 다른 모든 정점으로의 최단 경로의 경로값을 구해야한다. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1753) 문제 풀이다익스트라 알고리즘을 사용해서 각 정점으로의 최단 경로를 구할 수 있다. 우선 주어진 입력을 통해서 인접리스트를 만들고, 다익스트라 알고리즘을 수행하면된다. 그런데 아직 가중치가 주어진 그래프를 벡터로 표현해서 사용해본적이 없어서 벡터를 통해 인접리스트를 만들 때 가중치를 어떻게 저장해야할지 생각해보아야 한다. 가장 쉽게 생각을 하면 각 정점에서 어느 정점으로 갈지를 나타내는 수와 가중치를 함께 저장할 수 있도록 pair를 사용해봐야겠다. 인접리스트를 만든다음에는 시작점에서부터 다익스트라 알고리..

오늘 공부해볼 알고리즘은 Greedy Algorithm이다. 단어 Greedy의 욕심이 많다는 뜻 그대로 바로 눈앞의 가장 큰 이익만을 찾는 기법이다. 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다. 그리디 알고리즘은 최적의 결과를 낼 수 있고, polynomial 한 시간에 실행할 수 있다는 장점이 있지만, 항상 최적의 결과를 보장하는 것은 아니다. 예를 들어보도록 하겠다. 만약 1에서 4로 가고자 할 때 1에서 2로 가는 비용은 1이고, 1에서 3으로 가는 비용은 10이다. 그리고 2에서 4로 가는 비용은 100이고 3에서 4로 가는 비용은 1이다. 그리디 알고리즘을 사용해서 1에서 4를 가는 최소 비용의 경로를 찾는다면 1에서 2로 가는 경로를 선택할 것이다. 하지만 이 ..