반갑습니다!

14496번: 그대, 그머가 되어 boj.kr 풀이 각 글자를 정점이라고 생각하고 그래프를 만든 뒤, 최단 경로를 찾아주면 되는 문제이다. 다익스트라 알고리즘을 사용하면 어렵지 않게 해결할 수 있다. 코드 C++ #include #include #include using namespace std; const int INF = 1e9; int a, b, n, m; vector adj; vector dist; vector visited; void dijkstra(int start) { priority_queue pq; pq.push({ 0, start }); dist[start] = 0; visited[start] = true; while (!pq.empty()) { int now_dist = pq.top(..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 [프로그래머스] 도둑질과 동일한 문제이다. 차이점이 있다면 N이 1인 경우 예외처리를 해줘야한다는 점이다. 코드 C++ #include #include #include using namespace std; int solution(vector sticker){ int n = sticker.size(); if(n == 1) return sticker[0]; vector dp(2, vector(n, 0)); dp[0][0] = 0; dp[1][0] = sticker[0]; for (int i = 1; i < ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 동적 계획법 문제이다. 이 문제에서 관건은 모든 집들이 동그랗게 배치되어 있다는 것이다. 따라서 도둑이 첫 번째 집을 턴다면 마지막 집을 털 수 없게 된다. 즉, 첫 번째 집을 터는지에 따라서 정답이 달라질 수 있다는 것이다. 우선은 집이 직선으로 배치되어있다고 생각해보자. 도둑이 1번 집에서 n번 집까지 순서대로 이동한다고 생각해보자. 그렇다면 n번째 집까지 도둑질을 마무리했을 때의 경우는 2가지가 나온다. n-1번째 집을 털고, n번째 집은 털지 않은 경우 n-1번째 집을 털지 않고, n번째 집을 턴..

18353번: 병사 배치하기 boj.kr 풀이 병사 리스트를 뒤집으면 결국 LIS(Longest Increasing Subsequence) 문제가 된다는 것을 알 수 있다. LIS 알고리즘은 크게 2가지 방법이 알려져있다. 하나는 동적 계획법을 사용해 O(n^2) 시간에 해결하는 방법, 또다른 하나는 이분 탐색(lower_bound)를 사용해 O(nlogn) 시간에 해결하는 방법이다. 아래의 코드에서는 이분 탐색을 활용해 O(nlogn)의 복잡도로 해결했다. 코드 C++ #include #include #include using namespace std; int n; vector soldiers; int get_lis() { if (n == 1) return 0; vector lis; lis.push_b..

2491번: 수열 www.acmicpc.net 풀이 가장 긴 길이의 연속해서 커지거나 작아지는 수열을 찾는 문제이다. 연속해서 커지는 수열의 길이를 찾을 수 있으면, 입력 받은 숫자 배열을 뒤집어서 연속해서 작아지는 수열의 길이를 찾을 수 있다. 해당 문제에서 실제 연속해서 커지는 수열의 값이 필요한 것이 아니라 길이만 알면 되기 때문에 투 포인터 알고리즘을 사용해 해결했다. 코드 C++ #include #include #include using namespace std; int n; vector num; int two_pointer() { int left = 0; int right = 0; int last_value = 0; // 수열의 마지막 값을 저장할 변수 int ret = 0; // 수열의 최대..