hades

🥅 문제https://www.acmicpc.net/problem/1509 🔍 설계부분 문자열들 중에서 어디서부터 어디까지 팰린드롬인지 먼저 구해야 한다. 팰린드롬을 구하는 방법은 다음과 같다. 문자 개수가 하나인 경우, 팰린드롬이다.문자 개수가 2개인 경우, 두 문자가 같으면 팰린드롬이다.문자 개수가 3개 이상인 경우, 맨 앞과 맨 뒤가 같고, 가운데가 팰린드롬이면, 팰린드롬이다. 이제 팰린드롬을 구했으니, 최소로 분할해야 한다. 최소 분할 수는 반복문으로 어떤 인덱스까지의 최소 분할 개수를 저장하면서, 구할 수 있다. 주의해야할 점은 팰린드롬이 기본적으로 성립해야 한다는 것이다. 기존에 저장된 값과 0부터 end 사이의 인덱스를 start라고 할 때, start부터 end까지 팰린드롬이 성립한다면,..

🥅 문제https://www.acmicpc.net/problem/6198 🔍 설계처음에는 벡터에 높이들을 모두 저장하고, 이중 반복문을 수행하려고 했으나, 시간 복잡도 O(N^2)에 의해 시간 초과가 발생할 것이다. 건물 관리인들은 오른쪽만 보기 때문에, 반복문으로 건물 하나의 높이를 고려하면서, 스택에 그 건물을 볼 수 있는 다른 건물들을 저장한다.  만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 낮거나 같다면, 새로운 건물과 이후에 나오는 건물들을 볼 수 없으므로 이제 결과에 영향을 주지 않기 때문에 지운다. 만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 높다면, 그 건물에서 새로운 건물을 볼 수 있으므로 스택에 있는 건물의 개수를 추가한다. 👊 풀이#include #i..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

🥅 문제https://www.acmicpc.net/problem/15486 🔍 설계데이터가 엄청 많고, 최대의 이익을 얻도록 상담을 구성하므로, 다이나믹 프로그래밍으로 방향을 잡았다. dp[i]에는 상담을 i번째 날까지 했을 때, 최대 이익을 저장한다. i로부터 상담이 끝나는 날은 i + 소요 날 - 1이고, 이것을 finish_day로 지정하였다. i번째 날에 상담을 시작한다면, 상담이 끝난 날 얻는 이득인 dp[finish_day]는 dp[i-1] + 상담 이익이다. 여기서 dp[i]가 아닌 dp[i-1]을 더해야 함에 유의한다. dp[i]는 i번째 날까지 상담이 이루어지므로 상담을 시작할 수 없다. 또한, i번째 날에 상담이 끝나지 않는 경우를 고려하면, 전날까지의 이익과 비교하여 최댓값을 구하..

🥅 문제https://www.acmicpc.net/problem/30805 🔍 설계사전 순으롤 가장 뒤에 있는 공통 부분 수열을 찾으면 되므로, 먼저 각 수열을 큰 수가 앞에 오도록, 수의 크기가 같다면, 인덱스가 작은 것이 앞에 오도록 하게 하기 위해 우선순위 큐를 이용하였다.  각각의 우선순위 큐에서 앞에 있는 하나를 꺼내면서 같다면, 결과에 추가한다.다르다면, 큰 것이 있는 우선순위 큐에서 하나를 없앤다. 큰 것이 계속 남아있다면, 그와 같은 것이 다른 쪽에 없기 때문이다. 주의해야할 것은 크기 뿐만 아니라 결과에 포함되는 수가 각각 양쪽 수열에서 어느 인덱스에 위치하는 지를 기록하고, 그 인덱스보다 작다면 결과에 추가될 수 없으므로 없애는 과정이 포함되어야 한다. 👊 풀이#include #i..

🥅 문제https://www.acmicpc.net/problem/16236 🔍 설계초기 설계에서는 초를 늘리면서, 거리가 동일할 때는 위, 왼쪽, 오른쪽, 아래 순으로 우선순위가 높으므로, 탐색 순서도 위, 왼쪽, 오른쪽, 아래 순으로 탐색한다.  먹을 수 있는 것이 있으면, 바로 먹고, 거리를 반환한다. 먹을 수 없으면, 거리를 갱신하고, 큐에 담는다. 반환된 거리가 0이 아니면, 먹을 수 있는 것이 있다는 의미이므로, 최종 결과에 더한다.반환된 거리가 0이면 먹을 수 있는 것이 더 이상 없다는 의미이므로 반복문을 종료한다.#include #include #include #include using namespace std;int n, baby_shark_size = 2, eat_count = 0, ..

🥅 문제https://www.acmicpc.net/problem/5639 🔍 설계입력으로 주어진 50 30 24 5 28 45 98 52 60 에서 루트, L, R을 구분하면, 50 30 24 5 28 45 98 52 60 이다.L, R 서브트리 각각의 서브트리를 구해도 루트는 첫 번째, L은 두 번부터 루트보다 작은 수까지, R은 루트보다 큰 수부터 끝까지라는 것을 알 수 있다. 서브 트리에 해당하는 인덱스의 범위를 재귀로 만들어서 LRV를 진행하면 된다. 주의해야할 점은 개수가 정해져 있지 않기 때문에, while을 이용하여 벡터에 입력값을 지정했는데, 이럴 경우 최종 인덱스는 마지막 인덱스보다 하나 더 많은 총 개수이다. 따라서 범위를 지정할 때, end는 사용되지 않는다는 것에 유의해야 한다...

🥅 문제https://www.acmicpc.net/problem/17144 🔍 설계확산, 반시계 순환, 시계 순환을 각각 구현하면 된다. 먼저, 확산을 설계해보았다. 확산은 동시에 일어나기 때문에, 기존 벡터에서 진행하면 안된다.  예를 들어, 0행 0열에서 확산이 일어났고, 확산된 양을 0행 1열에 추가하면, 0행 1열에서 확산이 일어날 때, 더해진 양을 고려한 미세먼지의 양으로 확산이 일어난다. 따라서, 확산과 관련된 연산은 before_spread에서 하고, 확산되는 양과 남은 양을 저장하기 위해 after_spread를 만들었다. 확산되는 양의 총합을 구하기 위해 확산되는 위치에서 더하는 것은 잘했으나, 남은 양을 저장하는 데 있어서 =으로 처리해서 문제가 있었다. =으로 처리할 경우, 확산되..

필요성데이터베이스에서 칼로리가 100보다 낮은 요리명을 선택하라는 SQL 쿼리문은 다음과 같다.SELECT name FROM dishes WHERE calorie SQL 쿼리문에서는 반복자, 누적자 같은 것이 필요 없이 기대하는 것이 무엇인지 직접 표현할 수 있다. 즉, 질의를 어떻게 구현해야 할지 명시할 필요가 없으며, 구현은 자동으로 제공된다. 컬렉션에서도 이와 비슷한 기능을 만들고 싶다. 많은 요소를 포함하는 컬렉션의 성능을 높이고 싶다. 성능을 높이려면, 멀티코어 아키텍처를 활용해서 병렬로 컬렉션 요소를 처리해야 한다. 또한, 통화별로 트랜잭션을 그룹화하고 싶다면, 다음과 같이 구현해야 한다. 코드가 상당히 길다.Map> transactionsByCurrencies = new HashMap();f..