본문 바로가기

알고리즘8

[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.
[2302] 극장좌석 - c++ https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 정말 미세하게 DP에 대한 감이 잡히기 시작한 것 같다. DP문제라는 것을 알고 풀긴 했지만! 점화식을 찾아냈다는 것이 뿌듯했다. 하지만 점화식을 찾아낸 것 그뿐이고 그다음을 어떻게 해야 할지 몰라 답을 찾아서 봤다....ㅎ 풀이 먼저 점화식을 찾아낸 방법은 하나하나 다 써봤다. 이것만큼 좋은 게 있을까? $$\Large d[i] \space =\space d[i-1] \space + \space d[i-2].. 2023. 6. 17.
백준 18080 - c++ 요약 1. 노트북 뒷면에 스티커를 붙일 거다 2. 스티커를 붙일 때 왼쪽 가장 위에 붙일 수 있다면 바로 붙인다. 3. 안되면 스티커를 90도씩 돌려가면서 계속 붙여본다. 4. 그래도 안되면 그 스티커는 버린다. 5. 마지막에 스티커를 붙인 총넓이를 구한다. 아이디어 1. 스티커를 붙일 수 있는지 한 번씩 모든 좌표에서 확인해봐야 한다. 노트북 배열을 돌면서 로직을 구성한다. 2. 붙일 수 있다면 붙인다. 3. 안되면 스티커를 돌려야 한다. 구현 1. 스티커를 돌리는 함수 void rotate(){ int tmp[12][12]; for(int i =0; i < r; ++i) for(int j =0; j < c; ++j) tmp[i][j] = sticker[i][j]; for(int i =0; i < c;.. 2023. 5. 28.
[Algorithm] 2839 설탕 배달 문제 처음에 내가 생각한 코드 N = int(input()) count = 0 a = N % 5 if a == 0: count = N/5 elif a % 3 == 0: count = (N/5) + a/3 else: for i in range(1, N): b = (N - (3*i)) if b % 5 == 0 and b >= 0 : count = i + b/5 break; else: count = -1 print(int(count)) 1. 5의 배수 먼저 거르고 2. 3의 배수 거르고 3. 위의 둘에서 걸러지지 않았다면 1, N까지 반복하며 N에서 -(3 * i)를 해줌 만약 해준 결과값에서 % 5 (5의 나머지)를 구해서 0이 나오면 count에 i + 5를 해줌 4. 만약 모두 아니면 1 ~ N까지 반복.. 2022. 8. 11.

티스토리툴바