DHistory

문제https://www.acmicpc.net/problem/1254 풀이1. 이미 팰린드롬인 경우 해당 문자열의 길이가 최소2. 앞에서 부터 하나씩 거꾸로 붙여나가며 팰린드롬 문자열 확인 예시abcd 코드import systext = sys.stdin.readline().rstrip()def palindrome(text): if text == text[::-1]: return len(text) for i in range(len(text)): temp_text = text + text[:i + 1][::-1] if temp_text == temp_text[::-1]: return len(text) + i + 1 # 무의미 ..

문제https://www.acmicpc.net/problem/17086 풀이1. 상어 주변은 미리 제외해야 함.   : 재탐색을 진행하면 안되기 때문에 미리 주변을 제외해야한다.   (핵심: 주변을 미리 제외하려면 Queue에 미리 넣어서 BFS 탐색을 진행)2. 상어로부터 먼 거리 확인 예시5 40 0 1 00 0 0 01 0 0 00 0 0 00 0 0 1 # 미리 제외0 2 1 22 2 2 21 2 0 02 2 2 20 0 2 1# 이후 채워지지 않은 거리 채우기3 2 1 22 2 2 21 2 3 32 2 2 23 3 2 1 코드import sysfrom collections import dequen, m = map(int, sys.stdin.readline().rstrip().split())sha..

문제https://www.acmicpc.net/problem/2304 풀이오목하게 들어간 부분이 없으려면, 루프탑 기준 왼쪽과 오른쪽으로 나누어 문제 풀이를 진행해야 합니다.오른쪽 부분은 순서를 뒤집어서 문제를 풀어야 루프탑과 연결했을 때 오목한 부분이 없습니다. 루프탑 기준으로 왼쪽 부분과 오른쪽 부분으로 나눈 후 왼쪽 부분의 합 + 오른쪽 부분의 합 + 루프탑 사이의 합을 구하면 됩니다. 예시72 411 415 84 65 38 1013 6 왼쪽 배열: (2, 4) (4, 6) (5, 3) (8, 10)오른쪽 배열: (8,10) (11, 4) (13, 6) (15, 8)→ 루프탑: (8, 10) 왼쪽 배열의 합: (4 - 2) * 2 + (5 - 4) * 6 + (8 - 5) * 6오른쪽 배열의 합: ..

문제https://www.acmicpc.net/problem/24444 풀이그래프 탐색 이용1. 정점 번호 오름차순 정렬2. BFS를 이용한 풀이3. 정점 방문 전 숫자 1 증가 예시5 5 11 41 22 32 43 4  코드import sysfrom collections import dequen, m, r = map(int, sys.stdin.readline().rstrip().split())edges = [[] for _ in range(n + 1)]visited = [0] * (n + 1)for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split()) edges[x].append(y) edges[y].append(x..

문제https://www.acmicpc.net/problem/24479 풀이그래프 탐색 이용1. 정점 번호 오름차순 정렬2. DFS 를 이용한 풀이3. python 함수 호출 수 제한 변경 예시5 5 11 41 22 32 43 4   코드import syssys.setrecursionlimit(130000)n, m, r = map(int, sys.stdin.readline().rstrip().split())edges = [[] for _ in range(n + 1)]visited = [0] * (n + 1)for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split()) edges[x].append(y) edges[y].a..

문제https://www.acmicpc.net/problem/5567 풀이그래프 탐색 이용1. BFS 활용2. 방문하지 않았으면 방문 (기존 방문 + 1)3. 인접 정점 할당 예시651 21 33 42 34 5  코드import sysfrom collections import dequen = int(sys.stdin.readline().rstrip())m = int(sys.stdin.readline().rstrip())edges = [[] for _ in range(n + 1)]visited = [0] * (n + 1)for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split()) edges[x].append(y) edg..

문제https://www.acmicpc.net/problem/1965 풀이큰 문제를 작은 문제로 풀 수 있는 DPd[n]: n 번째 상자일 때, 한 번에 넣을 수 있는 최대의 상자 개수 예시1) 기준 상자일 때,2) 기준 상자보다 왼쪽에 있는 상자들 중 최대 상자 개수 구하기3) 본인 상자 추가 코드import sysn = int(sys.stdin.readline().rstrip())boxes = list(map(int, sys.stdin.readline().rstrip().split()))d = [1] * 1000for i in range(n): for j in range(i): if boxes[i] > boxes[j]: d[i] = max(d[i], d[j] + ..

문제https://www.acmicpc.net/problem/2075  풀이우선 순위 큐 사용1) 주어진 숫자를 구하고자하는 길이 만큼 넣는다.2) 제일 작은 수보다 큰 숫자가 주어진 경우 제일 작은 수를 제외하고 큰 숫자를 넣는다. 예시127915513811196211026311648142835255220324149 첫번째 줄5, 7, 9, 12, 15 두번째 줄13인 경우: 5, 7, 9, 12, 15 → 5제외 13추가 → 7, 9, 12, 13, 158인 경우: 7, 9, 12, 13, 15 → 7제외 8추가 → 8, 9, 12, 13, 1511인 경우: 8, 9, 12, 13, 15 → 8제외 11추가 → 9, 11, 12, 13, 1519인 경우: 9, 11, 12, 13, 15 → 9제외 1..

문제https://www.acmicpc.net/problem/11048 풀이큰 문제를 작은 문제로 나누어 풀 수 있는 DP 문제이다. D[N][M]: (N, M) 위치에 있을 때, 사탕을 최대한 많이 가져올 수 있는 개수 1. 첫 블럭 예외 (첫 블럭이 곧 사탕 최대 개수)2. i 열이 0인 경우 첫 블럭부터 계속 쌓아온 사탕 개수3. j 열이 0인 경우 첫 블럭부터 계속 쌓아온 사탕 개수4. 대각선인 경우 아래 경우의 수 중 가장 큰 사탕 개수  4-1) 위에서 온 경우  4-2) 왼쪽에서 온 경우  4-3) 대각선에서 온 경우예시3 x 4사탕 수123400059876 최대 개수136101361510182531 코드import sysn, m = map(int, sys.stdin.readline().rs..

문제https://www.acmicpc.net/problem/9184 풀이재귀함수 호출 결과를 미리 저장한다. (팩토리얼 문제와 유사)함수를 호출하는 부분을 미리 저장한 내용을 불러오면 된다. 코드import sysnumber = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]def w(a, b, c): if a 20 or b > 20 or c > 20: return number[20][20][20] if a