본문 바로가기

전체 글348

백준 1915 c++ - 가장 큰 정사각형 [필자 처음 생각 ] 처음 문제를 읽고 DFS, BFS 문제라 생각했지만 모든 정사각형인지 판단하려면 코드를 짜는것도 쉽지 않고 무엇보다 시간복잡도 측면에서 어긋나게 된다는걸 알았다. 다음으로 분할로 사고를 바꿨지만 사각형이 어디에 존재하는지 정확히 알 수 없는 상황에서는 균등하게 분할로 풀 수 없었다. [해결과정] 조금의 사고 과정후 DP문제라는걸 알게 되었다 [KEY POINT] 만약 배열 값이 1이면 사각형 오른쪽 아래 꼭짓점이라 가정을한다. 그 점 기준으로 왼쪽, 위쪽, 왼쪽위의 값중 가장 작은값을 구하고 +1을 해주면 동적프로그래밍 완성이다. #include #include #include #include using namespace std; int Arr[1001][1001]; int N, M.. 2024. 2. 13.
백준 9252 C++ - LCS 2 필자: LCS의 정의를 이해하는데 시간이 걸렸다. 공부해보니 순서대로 각 두 문자열의 가장 긴 공통요소를 구하는 뜻이다. 또한 문제 유형이 DP인걸 이해하는데도 시간이 걸렸다. [핵심 사고 ] 문자가 같으면 DP[i][j]= DP[i-1][j-1] +1 왼쪽 위에서 하나 더해준다. 문자가 다르면 DP[i][j] = max(DP[i-1][j], DP[i][j-1]) 왼쪽 혹은 위쪽중 큰 값을 저장한다. #include #include #include #include using namespace std; int N; int D[1001][1001]; string A, B; vector Path; void getText(int r, int c); int main(void) { cin >> A >> B; for.. 2024. 2. 13.
백준 c++ 13398 - 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 필자 처음 사고과정 : DP문제가 이 문제의 해결 KEY다 -> D[idx] 마다 최댓값을 저장하려 했지만 문제의 조건중에 자유롭게 하나의 수를 제거할 수 있다. 라는 이유로 이 방식은 포기했다. 해결과정 : 이 문제의 핵심은 위의 그림처럼 X표시 되는 모든 구간을 조사하여 최댓값이 되는 값을 구해야 되는 문제다. 이러한 이유로 L벡터와 R벡터를 만들었다. L 벡터에는 왼쪽부터 시작하여 배열의 마지막.. 2024. 2. 13.
환영합니다! #1 글을 작성하고 블로그를 관리해보세요. 님의 회원 가입을 진심으로 축하합니다. 이 글은 비공개로 작성돼 있습니다. '편집'으로 내용을 바꾸시거나, 삭제 후 '새 글을 작성'하셔도 됩니다. 글 뿐만 아니라 블로그의 각종 설정을 변경할 수도 있습니다. '블로그관리'를 확인해보세요. #2 다양한 스킨이 있어요. 티스토리에 있는 다양한 '스킨'도 살펴 보세요. 블로그나 사이트를 사용하는 목적에 맞게 스킨을 고를 수 있습니다. 어떤 이야기를 주로 하실 건가요? 잘 생각해 보시고, 마음에 드는 스킨을 고르세요. '스킨 편집'을 통해 다양한 커스텀, 그리고 홈 꾸미기를 적용하실 수도 있답니다. #3 포럼에서 사람들과 소통하세요. 마지막으로 사용하시다가 티스토리에 대해 궁금한 내용이 있다면 '포럼'을 확인하세요. .. 2024. 2. 10.

티스토리툴바