전체 글110 [3015] 오아시스 재결합 - C++ 온전히 내 힘으로 풀었다 할 수는 없지만, 첫 플레티넘 문제이고 내가 생각한 아이디어와 다른 사람의 아이디어를 적어보고 싶어 글로 작성해 본다. 아이디어 일단 규칙(?)을 찾아보려고 한다. 전 값보다 큰 게 들어온다면 전 값(2) 보다 큰 값이 들어온다면 앞의 2는 다음 사람을 보지 못하기 때문에 스택에 존재할 이유가 없어진다. 4와 같거나 큰 값, 또는 스택이 빌 때까지 POP해 준다. 전 값보다 작은 값이 들어온다면 카운트를 증가시킨다 같은 값이 들어온다면 그렇다 (2, 2), (2, 2), (2, 2), (4, 2), (4, 2), (4, 2)가 가능하다. 중복된 값을 생략하여 넣는 방법을 스택을 하나 더 만들어 구현해 봤지만 아닌 것 같아 중간에 그만뒀다. 이 부분을 대체 어떤 식으로 구현해야 할.. 2023. 6. 28. [16236] 아기 상어 - C++ 풀이 이번 글에서는 어떻게 구상하고 설계했는지 자세하게 적어 보려고 한다 1. 나에게 가까운 것을 찾아야 한다. BFS를 사용할 수 있을 듯하다. 가까운 것이 여러 개 있다면 가장 위에 있는 것, 그중에서도 여러 개 있다면 가장 왼쪽의 것을 고르라 하니 BFS를 돌고 for문을 사용해도 될 듯하다. 시간을 표시해줘야 하니 Dist라는 -1로 채워진 $ N \times N $ 배열을 만들어 줘야 한다. 2. 상어를 성장시켜야 한다. baby라는 상어의 현재 크기를 담는 변수 growing이라는초기값은 0이고, 물고기를 먹을 때마다 증가시킨다. 만약 baby 변수와 값이 동일해진다면 baby증가, growing은 0으로 초기화 즉 상어의 무게를 늘려주는 식으로 구상했다. 3. 종료 조건 무한 반복을 돌리며 .. 2023. 6. 27. [10942] 팰린드롬? - C++ 문제 모든 경우의 수를 확인하는 브루트 포스로 푸는 것은 불가능해 보인다. N은 최대 2000개 이고, 질문의 개수가 최대 1,000,000개 [ 1, 2000 ]이라는 질문이 1,000,000개 나온다면 20억 번 연산을 해야 하므로 0.5초 안에는 절대 불가능 Q. DP로는 가능 할까? A. 가능하다. 점화식 명령 : [ 1, 7 ]이 팰린드롬이지 확인하고 싶다면 [ 2, 6 ] 이 팰린드롬 인지 확인 하고 [ 1 ] == [ 7 ]이 같은 지 확인해 주면 된다. 그런데 또 [ 2, 6 ]이 팰린드롬인지 알려면 [ 3, 5 ]를 알아야 하므로 DP로 풀 수 있다. 테이블 정의 DP [ i ][ j ] = i번째부터 j번째 까지가 팰린드롬 인지 확인 Boolean Type 입력받기 for(int i =.. 2023. 6. 27. [11057] 오르막 수 - C++ 문제 왜 DP를 써야 하는지 감조차 오지 않을 당신을 난 이미 알고 있다. 기본 적으로 입력이 1일 때는 10개이다. 0 1 2 3 4 5 6 7 8 9 2일 때 00 01... 09 - 10개 11 12... 19 - 9개 22 23... 29 - 8개 33 34... 39 - 7개 ... 99 - 1개 3일 때 000 001... 009 - 10개 011 012... 019 - 9개 022 023... 029 - 8개 ... 999 뭔가가 보인다면 대단한 것이며, 안 보여도 좋다, 당신의 눈을 뜨이게 하는 것이 나의 역할이다. Q. DP 테이블에 어떻게 의미를 부여해 줘야 할까? A. DP [i] = i번째 숫자가 처음인 상태에서의 최대 경우의 수 위의 설명은 좀 어려울 수 있으니 그림으로 보자 그림.. 2023. 6. 26. [9465] 스티커 - C++ 이 글은 정말 이해가 가지 않는 분들을 위해 쓰인 글입니다. 문제 브루트 포스를 생각할 수 도 있지만 $ O(2^n) $이며 입력의 최대 값이 100'000만 인 것을 보아 불가능하다. Q. 과연 DP로는 풀 수 있을까? A. DP [i] = i번째 까지 스티커를 떼었을 때의 최댓값으로 놓고 푼다면 가능하다. 경우의 수들이 존재하는데 그림으로 보자 i번째 스티커를 떼기 위한 경우의 수들 떼려는 스티커 = 파란색 파란색을 뗴기 위한 전까지의 최댓값 = 주황색 위 그림처럼 4가지 존재하며 이것을 구현해 주면 된다. 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } in.. 2023. 6. 26. [1915] 가장 큰 정사각형 - C++ 정말 너무 진이 빠진다ㅏㅏ 풀이 정사각형인지 판단하려면 어떻게 해야 할까? 위, 옆, 대각선을 확인하면 된다. 이걸로 이 문제는 해결이라 볼 수 있다. 점화식 $$\large dp [x][y] = min(\{dp [x-1][y], dp [x][y-1], dp [x-1][y-1]\})$$ 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, m; int arr[1002][1002], dp[1002][1002]; int main(){ init(); cin >> n >> m; //입력 for(int i = 1; i > str; for(int j = 1; j 2023. 6. 23. [9252] LCS2 - C++ 풀이 먼저 내가 썼던 글을 보고 오도록 하자, 그래야 이 문제도 이해할 수 있다! https://juuuuung.tistory.com/126 [9251]LCS - C++ 풀이 LCS - 최장 공통부분 수열 점화식 if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 비교하는 두 문자가 같다면 dp [i-1][j-1] + 1 비교하는 두 문자가 다르다면 dp[i-1][j], dp [ juuuuung.tistory.com ※위의 글을 읽었다는 가정하에 풀이를 시작하겠다.※ 최대 공통 문자열의 수를 구하는 알고리즘(LCS) cin >> A >> B; for(int i = 1; i A >> B; .. 2023. 6. 23. [9251]LCS - C++ 풀이 LCS - 최장 공통부분 수열 점화식 if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 비교하는 두 문자가 같다면 dp [i-1][j-1] + 1 비교하는 두 문자가 다르다면 dp[i-1][j], dp [i][j-1] 둘 중 큰 값을 구한다. 그림 설명 더보기 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } string A, B; int dp[1003][1003]; int main(){ init(); cin >> A >> B; for(.. 2023. 6. 23. [2294] 동전 2 - C++ 안 좋은 풀이와 좋은 풀이 두 가지 다 보여 드리겠습니다. 안 좋은 풀이 DP테이블을 이차원 배열로 놓고 풀었다. 행 ( row ) = 내가 가진 동전의 순서 열 ( column ) = 만들 수 있는 임의의 가치 먼저 코드를 보고 그림으로 이해해 보도록 하자 //상수 #define MAX 2E+9 //변수들 int n, k; int coin[101]; int dp[101][10'002]; //입력 cin >> n >> k; for(int i =1; i > coin[i]; //실행 로직 for(int i = 1; i 2023. 6. 22. [1107] 리모컨 - C++ 브루트 포스로 문제를 풀어야겠다는 생각 조차 하지 못했다. 풀이 수빈이는 현재 100번 채널에 있다. 부서진 리모컨 입력 받기 부서진 리모컨의 번호를 bool 배열로 표시한다. bool breakDown[11]; //부서진 번호 입력 for(int i = 0; i > num; breakDown[num] = true; } 초기 최솟값 설정 최소 이동을 표현하기 위한 minimum 변수를 만드며, 초기값은 abs(n-100) int minimum = abs(n-100); 위처럼 구현한 이유는? 만약 n 이 100보다 작을 수 있기 때문에 예) n = 10, mnimum = 90, 현재로서 최솟값은 90번 ( - ) 버튼을 눌러야 10에 도달할 수 있다. 연산 로직.. 2023. 6. 22. 이전 1 2 3 4 5 6 ··· 11 다음
