PS/백준

난이도 : 골드 4유형 : BFS / DFS / DP링크 : https://www.acmicpc.net/problem/12869구현 시간 : 30분     문제 풀이 이 문제는 BFS / DFS 알고리즘의 유형으로, 뮤탈리스크는 한 번의 공격에서 세 개의 SCV에 각각 9, 3, 1의 피해를 줄 수 있으며, 세 개의 공격 순서를 자유롭게 선택할 수 있습니다.즉, 모든 가능한 공격 순서를 고려하여 최소 공격 횟수를 찾아야 하는 문제입니다. 얼핏 보면 SCV 체력을 내림차순으로 정렬하고, 9 -> 3 -> 1 순서로 공격하면 쉽게 해결할 수 있지 않나? 싶지만아래 예제를 보면 그리디하게 문제를 해결할 수 없다는 것을 알 수 있습니다.SCV의 체력이 (12 , 10, 4)일 때첫번째 공격 -> 1, 3, 2 ..

난이도 : 골드 1유형 : 그리디 / 구현링크 : https://www.acmicpc.net/problem/1700구현 시간 : 1시간     문제 풀이 이 문제는 그리디 알고리즘 유형으로, 멀티탭에 꽂힌 전기용품 중 어떤 것을 제거해야 하는지 결정하는 문제입니다. 멀티탭의 상태를 관리하기 위해 삭제 및 삽입이 용이한 List 자료구조를 사용하여 구현하였습니다.현재 멀티탭이 비어있거나 빈 구멍이 있는 경우새로운 전기용품을 그대로 꽂습니다.새로운 전기용품이 이미 멀티탭에 꽂혀 있는 경우추가적인 작업 없이 그대로 넘어갑니다.멀티탭이 꽉 찬 상태에서 새로운 전기용품이 등장할 경우 (🔥핵심)1. 이후 사용되지 않는 전기용품이 있다면해당 전기용품을 제거합니다.2. 모든 전기용품이 이후에도 사용된다면가장 마지막에..

난이도 : 실버 2유형 : 동적 계획법 / LIS링크 : https://www.acmicpc.net/problem/18353구현 시간 : 30분    문제 풀이이 문제는 ‘가장 긴 감소하는 부분 수열’을 찾는 문제로, LIS(가장 긴 증가하는 부분 수열) 알고리즘을 변형해서 해결할 수 있습니다.DP 테이블은 각 위치에서 끝나는 가장 긴 감소하는 부분 수열의 길이를 저장합니다. 예를 들어, dp[i]는 i번째 숫자를 마지막으로 포함하는 가장 긴 감소하는 부분 수열의 길이를 의미합니다.각 숫자를 기준으로 그 이전 숫자들과 비교합니다.만약 현재 숫자(arr[i])가 이전 숫자(arr[j])보다 작다면, 이전 숫자를 포함하는 감소하는 수열에 현재 숫자를 추가할 수 있습니다.이 경우, dp[i]를 dp[j] + ..

난이도 : 골드 5유형 : 조합 / 구현 / 백트래킹링크 : https://www.acmicpc.net/problem/15686구현 시간 : 30분       문제풀이위 문제의 핵심은 M개의 치킨집의 조합에 따라 최소 치킨 거리는 달라진다. 이 말이 무슨 뜻이냐면 항상 작은 치킨 거리의 합을 가지는 경우를 선택하면 안되므로 그리디 알고리즘은 사용할 수 없다. 예를 들어 6개의 치킨집 중 하나의 치킨집을 폐업시킬 때는 6개의 치킨집을 순회하며 하나씩 치킨집을 삭제해보고 최소값을 찾으면 되지만, 이 후 5개의 치킨집 중 하나의 치킨집을 다시 폐업시킬 때는 이전의 선택에 영향을 받을 수 있다는 의미이다.  따라서 현 상황에서 가장 좋은 선택을 하는 그리디 알고리즘은 사용하지 못하고, N개의 치킨집중 M개의 치..

난이도 : 골드 3유형 : 위상 정렬 / 동적 계획법링크 : https://www.acmicpc.net/problem/1005구현 시간 : 1시간 (못품)        문제풀이위상 정렬 알고리즘을 공부하고 나서 처음으로 풀어본 문제이다. 노드의 방문 순서를 구현하는건 쉬웠지만, 특정 건물마다 필요한 최대 시간을 구하는 방법을 생각해내지 못했다 ㅜ indegree[] 배열을 이용해 노드의 진입 차수를 저장하고, 방문마다 해당 노드의 진입 차수를 차감하여 위상 정렬을 구현했다. BFS에서 탐색 레벨마다 날짜를 계산했었던 토마토 문제가 기억이 나서 위상 정렬에도 반복마다 최대 시간을 누적하는 방식으로 최대 시간을 저장했다. 하지만 이 방법은 이전 단계에서 소요된 시간을 다음 단계에 반영하지 못하므로, 특정 노..

난이도 : 골드 3유형 : 최단 경로 / 다익스트라링크 : https://www.acmicpc.net/problem/11779 구현 시간 : 30분    문제풀이해당 문제를 해결하기 위해서 다익스트라 알고리즘을 사용하여 출발 도시에서 각 노드(도시)까지의 최소 시간을 구하고, 동시에 이전 방문 노드를 저장해야 한다. 이를 위해 인접한 노드를 방문하며 최소 시간을 distance[] 배열에 갱신하고, 이와 함께 이전 노드를 preN[] 배열에 저장한다.이렇게 하면 특정 노드에 도달했을 때 해당 노드로 오기까지의 이전 노드를 추적할 수 있다.이후 최단 거리를 출력하고, Stack을 사용하여 방문 순서를 역순으로 출력한다. 핵심은 다익스트라 알고리즘에서 distance[] 배열을 갱신할 때, 이전 노드를 pr..

난이도 : 실버 1유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/2156구현 시간 : 1시간     문제풀이이 문제를 풀기 위해 DP의 Bottom-Up 방식을 사용하며, 9465번 스티커 문제와 같이 이전 선택에 따라 다음 선택이 제한된다.연속 세 잔의 포도주를 마실 수 없기 때문에 마지막 잔의 앞 잔, 앞앞 잔의 값이 크다면 마지막 잔을 마시지 않을 수도 있다는 점도 고려해야 한다. 따라서 N 번째 잔의 최대값을 구하려면 아래와 같은 경우를 고려해야 한다.N 번째 잔을 마시지 않는다. N 번째 잔을 마신다.N - 3 -> N - 1 -> N 번째 잔을 마신다.N - 2 -> N 번째 잔을 마신다. 위 경우를 고려해서 표현한 점화식은 아래와 같다.DP[i]..

난이도 : 실버 1유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/9465구현 시간 : 30분       문제풀이이 문제를 풀기 위해 DP의 Bottom-Up 방식을 사용하며, 문제 해결의 핵심은 이전 선택에 따라 다음 선택이 제한된다는 점이다.특정 행의 스티커를 선택할 때, 바로 이전 행의 대각선 방향 스티커만 선택 가능하고, 따라서 N 번째 행의 스티커를 선택할 경우, 이전 선택 결과를 고려해야 최대값을 얻을 수 있다. 나는 이차원 배열을 선언하여 N번째 행의 스티커를 선택했을 때 최대값을 DP 테이블로 저장해서 구현하는 방식을 선택했다. 점화식은 아래와 같다.DP[i][0] = max(DP[i-1][1], DP[i-2][1]) + sticker[i][0]..

난이도 : 실버 3유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/2193구현 시간 : 30분      문제풀이위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였다. 이 문제를 해결하기 위해서는 이친수의 규칙을 파악해야 한다.이진수가 0으로 끝나는 수는 다음 자리 숫자일 때, 0과 1로 생성되고, 1로 끝나는 수는 0으로 생성된다. 예를 들면, 10010 이라는 이진수는 다음 6자리수에서 10010 + 0, 10010 + 1 로 생성된다.또한, 10001 이라는 이진수는 다음 6자리수에서 10001 + 0 으로 생성된다. 따라서 N 번째 자리수에서 0으로 끝나는 이친수와, 1로 끝나는 이친수의 점화식은 다음과 같..

난이도 : 실버 3유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/7569구현 시간 : 30분     문제풀이위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였고, Top-Down 방식은 다른 분들의 코드를 참조하여 작성했다. 우선 위 문제를 풀기 위해서는 점화식을 정의해야한다. DP[i] 번째의 최대 점수를 구하기 위해서는 DP[i-2] (두 개의 계단 전의 최대 점수) 와 DP[i-3] + stair[i-1] (세 개의 계단 전의 최대 점수 + 직전 계단의 점수) 간의 최대 값과 stair[i] (i 번째 계단의 점수) 를 더하면 구할 수 있다. A(i) = max(A(i-2), A(i-3) + K(i-1))..