🔗 문제 링크https://www.acmicpc.net/problem/1083💡 문제 풀이 및 해석배열의 크기가 최대 50이므로 항상 최대로 옮긴다고 해도 50 * 49 / 2 밖에 되지 않는다. 완전탐색, 그리디 방식으로 풀 수 있다는 뜻이다.문제 풀이 순서도는 다음과 같다.2-1. 기회가 끝나거나(S == 0) 모두 정렬(left == right)이 될때까지 반복한다.2-2. 옮길 수 있는 기회만큼(left_index + S) 탐색한다. 단, 탐색이 N을 넘어가는 순간 멈춘다.2-3. 탐색한 범위에서 가장 큰 숫자의 위치와 left_index의 위치를 교환한다. 그만큼 기회를 차감한다.2-4. 교환을 한 뒤에는 다음으로 정렬하는 위치를 옮겨준다. (left_index + 1)⭐️ 정답 코드 및 설..
분류 전체보기
🔗 문제 링크https://www.acmicpc.net/problem/1197💡 문제 풀이 및 해석문제에서 최소 스패닝 트리라고 나와 있으므로 같은 방식으로 풀면 좋다.사실 최소 스패닝 트리가 기억이 잘 나지 않지만, 일단 트리 형식을 갖추면서 가중치가 가장 적은 트리를 만들어야 한다는 것을 알 수 있다.그러면 최대한 낮은 비용의 간선부터 연결해야 한다.단, 간선을 연결할 때, Cycle이 생기면 안된다. => Root가 같은 것들끼리는 연결해서는 안된다.따라서 비용을 오름차순으로 정렬하고 4번을 지키면서 낮은 것들을 계속 연결해가면 된다.단, 매번 부모를 계속 찾을 수 없으므로 매번 현재 나의 Root가 무엇인지 업데이트 해준다.⭐️ 정답 코드 및 설명#include #include #include..
🔗 문제 링크https://www.acmicpc.net/problem/1253💡 문제 풀이 및 해석일단 수가 10억까지 늘어날 수 있다. 이는 배열을 만들어서 풀면 메모리초과가 발생하니 배열로 풀 수 없는 문제이다.그러면 모든 수에 대해서 모든 경우를 더해야하나? 이것도 아니다. 2000개가 있을 때, 2000 * 2000 * 1999 / 2 라는 식을 계산해보면 40억이라는 숫자가 나온다. 따라서 모든 경우를 구하는 방법도 안된다.이런 문제를 풀어본 경험이 있다면 비교적 쉽게 풀이 방식을 찾을 수 있다. 바로 투 포인터이다.3-1. 배열을 입력받은 뒤 정렬한다.3-2. 가장왼쪽의 숫자와 가장 오른쪽의 숫자를 정한다.3-3. 둘의 합이 내가 구할려는 숫자보다 작으면 left++ 크다면 right--를..
🔗 문제 링크https://www.acmicpc.net/problem/1106💡 문제 풀이 및 해석냅색 문제지만, 주의해야 할 점이 한가지 있다. 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구해야 하는 것이다. 이는 C명을 늘리거나 혹은 그 이상 늘렸을 때, 최소비용이 되어야 한다는 뜻이다. 따라서 C명보다 많이 뽑아도 C명을 뽑을 때의 최소비용보다 낮다면 더 뽑아도 된다는 뜻이다.냅색 문제는 직접 보면 이해가 생각보다 쉬운 편이다. X에는 항상 최소비용이 들어가야 한다. 일단, 아무도 뽑지 않으면 0의 비용이 들어간다. 1명을 뽑을 때는 0명에서 1명을 뽑을 때 비용을 더해주면 된다. 2명을 뽑을때는 1명에서 1명을 더 뽑는 비용 vs 0명에서 2명을 뽑는 비용 중에서 낮은 비용..
🔗 문제 링크https://www.acmicpc.net/problem/1327💡 문제 풀이 및 해석일단, 최소 횟수이고, 모든 경우를 생각해봐야 하기 때문에, BFS로 풀어야 한다.뒤집어 볼 수 있는 위치는 모두 뒤집어본다. 단, 뒤집었을 때 이미 테스트한 경로라면 그 분기는 거기서 끝낸다.이미 테스트한 방식은 set에 저장하여 확인한다.⭐️ 정답 코드 및 설명#include #include #include #include #include using namespace std;int N, K;queue q;set isTest; // 이미 테스트한 항목들은 다시 테스트하지 않기 위한 목록string input() { cin >> N >> K; string str = ""; for (int..
🔗 문제 링크https://www.acmicpc.net/problem/1188💡 문제 풀이 및 해석최대공약수를 구하는 문제이자 패턴 문제이다. 모든 소시지를 합쳐서 1개로 만들고 균일하게 자른다고 생각하면 된다. 이 때, 소시지를 합치는 자리를 칼질하는 경우만 카운팅을 안하면 된다.예제 2번 케이스에서 3 4 => 인당 3/4가 필요하다는 뜻이고, 이는 소세지 3개를 이어 붙여서 1개로 만든 다음에 4등분하면 된다는 뜻이다. 따라서 3번만 자르면 된다.다시 예제 1번 케이스를 보자 2 6 이 들어오고 인당 2/6이 필요하다. 이는 소세지 2개를 이어 붙여서 1개로 만든 다음에 6등분하면 된다는 뜻인데, 그러면, 총 5번의 칼질 중 1번의 칼질은 카운팅할 필요가 없다. 이는 최대공약수로 나타낼 수 있다..
🔗 문제 링크https://www.acmicpc.net/problem/1034💡 문제 풀이 및 해석처음에는 50X50의 문제여서 완전탐색으로 풀 수 있는 문제라 생각했는데, 1000번의 열의 스위치를 킬 수 있다는 선택지 때문에, 2^50의 가짓수라 모든 경우를 찾아볼 수 없는 문제였다.문제의 조건을 보았을 때, K번을 반드시 눌러야 하므로 예제에서 열이 1개일 때, 짝수번이면 변화가 없는 것을 알 수 있다. 이 점에 유의해야 한다.모든 경우를 찾을 수 없다면, 경우를 줄여야 하는데, 이때, 패턴을 찾는 것이 그 방법이다. 예를 들어서 100 100 101 110 이런 식이라고 하자. 100과 101, 110은 같은 열의 솟자가 바뀌기 때문에 최종적으로 모두 1인경우가 나올 수가 없다. 따라서 100..
개발 환경⚙️ [ Java17, Gradle, Spring 3.3.1 ], [ Github, GithubActions ], [ AWS, EC2 - ubuntu, S3, CodeDeploy ] CI/CD?CI/CD는 지속적 통합(Continuous Integration)과 지속적 배포 (Continuous Deployment)의 약자입니다. CI는 지속적으로 코드를 통합하고 자동화된 테스트를 거치는 것을 의미합니다. 이로 인해서 버그가 줄어들고, 코드의 변경사항이 생길 때 마다 수동으로 테스트하지 오류가 줄어듭니다. 또한 개발자들 끼리 서로 코드가 충돌(conflict)날 수 있는데, 이를 잡아줄 수 있습니다. CD는 CI된 코드를 자동적으로 배포하는 것을 의미합니다. 배포 과정을 자동화하여 사람이 낼 수..
