https://www.acmicpc.net/problem/1738문제조건출발지부터 목적지까지 가야한다.단, 가는 경로에 깡패, 금품 두가지가 존재한다.목적지에 도착했을때, 금품의 양이 최대가 되는 경로를 구해라접근방법 다익스트라로 푸는 최단경로 문제인가? 라고 생각이 들었는데, 깡패가 금품을 갈취하면 음의 정수로 바뀌기 때문에, 다익스트라 알고리즘에서는 최단경로라고 판단된 노드는 더이상 갱신하지 않지만, 금품을 계속 반복해서 갈취당하면 음의 무한대로 짧아질수 있기 때문에 위 알고리즘은 아니다. 생각해보니 예전에 배웠던 음의 가중치가 있을때 최단거리를 구할수 있는 Bellman-Ford 알고리즘이 생각났다.Bellman-Ford 알고리즘 다익스트라 알고리즘과 더불어 최단경로를 구할 때 사용되는 대표적인 알..

https://www.acmicpc.net/problem/1162문제조건 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장포장하게 되면 도로를 지나는데 걸리는 시간이 0서울은 1번 도시, 포천은 N번 도시 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간은?접근방법 가중치가 있는 그래프에서 특정지점에서 시작해서 다른지점까지의 최단거리를 구하는 알고리즘인 다익스트라가 떠올랐다. 사실 이 문제는 푸는것 자체는 크게 어렵지 않았다. 다익스트라 알고리즘 자체가 dp를 기반으로 이때까지 계산된 거리와 새로운 거리를 비교해서 계속해서 기록하는 구조이므로, 엄청나게 큰값이 들어 갈수 있기때문엥 21억이 넘는 수 까지 처리해..

https://www.acmicpc.net/problem/1446문제조건D킬로미터의 고속도로 길이 주어진다.지름길의 시작위치, 도착위치, 지름길의 길이가 주어진다.고속도로 끝지점까지 가는 최소거리를 구해라.접근방법 Brute Force로 봐야하나,,? 평소에 잘 접하지 않은 유형의 문제여서 당황스러웠다.최단거리를 구한다고 하면 다익스트라가 떠올랐지만 어떻게 적용시키지,,,? 계속 생각이 안나서 검색의 힘을 조금 빌렸다.  Dijkstra 최단경로를 구하는 대표적인 알고리즘이다.이중 for문을 이용한것과, priority_queue를 이용해서 구현을 선택할 수 있는데, 우선순위 큐가 시간복잡도가 훨씬 작으므로 우선순위 큐를 사용한다.알고리즘의 동작과정은 이와같다.방문하지 않은 노드 중에서 최단거리가 가장 ..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제조건 n x n 크기의 대나무숲 어디든지 판다를 풀어놓을수 있다. 판다는 대나무를 다먹으면 상, 하, 좌, 우 중 한지역으로 이동한다. 이동하는 칸의 대나무가 원래있던 칸의 대나무 수보다 많아야 이동한다. 가장 많이 이동하는 경우의 이동수는? 접근방법 문제를 보자마자 생각이 들었다. '아 그냥 완전탐색돌려서 최댓값 갱신해서 찾자' 내가 좋아하는 DFS 알고리즘으로 모든 경우의 수를 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제조건 퇴사 전까지 상담을해서 얻을수 있는 최대 수익을 구하라 단순히 구현 + dp 문제였다. dp[i] : i일까지의 상담중에서 최대 수익 값 완전탐색을 진행하면서 상담에 걸리는 일수가 퇴사 전일때, 구하고자 하는 일자의 수익과, 지금까지의 수익 + 구하고자 하는 일자까지 상담하는 수익을 비교해서 최댓값을 갱신시켜줬다. 소스코드 #include #include using namespace std; int n, t[16], p[16], dp[16]; int main(){ cin >> n; for (int i = 0; i < n; i..

https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 문제조건 아래(↓), 오른쪽(→), 오른쪽아래(↘)로 갈수 있는 불도저가있고, 오른쪽 맨 아래칸까지 이동한다. A(불도저 아래쪽, 사과), B(불도저 위쪽, 바나나) 사과와 바나나의 합의 최댓값의 경우는? 처음 문제를 봤을땐, 탐색을 진행하는 경우의 수인것같아서 BFS로 접근했다. 하지만 이 접근방법은 최소일때 구하기 용이한 방법으로 생각을 좀더 했다. 우선 Brute Force를 떠올렸는데, ..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제. 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. 첫번째로 구해야할것은 LCS의 길이이다. 나는 완전탐색으로 두 문자열을 돌면서 dynamic ..

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제조건 어떤 문자열을 팰린드롬으로 분할한다. 분할된 수의 최솟값을 출력 팰린드롬이란? 어떤 문자가 있을때, 거꾸로 뒤집어서 읽어도 똑같은 문자를 의미한다. ex) 기러기 ☞ 기러기(O) cf) 거북이 ☞ 이북거(X) 이 문제에서 핵심은 문자가 입력으로 들어왔을때, 문자열안에서의 모든 경우의수를 탐색해서 팰린드롬인지 각각 파악해야..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 문제조건 각 구간은 한개이상의 연속된 수로 이뤄짐 서로다른 두 구간은 겹쳐있거나, 인접하면 안됨 정확히 M개의 구간이어야함 뭔가 좀처럼 접근방법이 떠오르지 않았다. 계속해서 경우의수가 다르기 때문에 DFS로 완전탐색을 돌려야하나 ,,? 어떻게 풀지 감이안와서 접근 방법만 찾아봤다. 역시 dynamic programming,,, 왠지 감이 안잡힌다 생각했다. 식을 세워야하는..

https://www.acmicpc.net/problem/1415 1415번: 사탕 첫째 줄에 슈퍼에 있는 사탕의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사탕의 가격이 주어진다. 사탕의 가격은 10,000보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제조건 사탕의 개수 : n개 사탕 가격의 합이 소수 모양이 똑같은 방법은 사지 않는다. 제일 먼저 떠오른 생각은 집합이었다. 집합이 한번 나오면 모양이 똑같은 방법을 커버할 수 있고, 그 집합의 원소들의 합이 소수가 되면 되기 때문이다. 라고 생각했지만 도저히 이 방법으로는 풀리지 않을 것 같았다,,, 일단 로직에 대해서는 더 고민해보기로 하고 소수 구하는 알고리즘을 보겠다. void isP..