백준 문제풀이 코드저장소/Platinum (14) 썸네일형 리스트형 Baekjoon 14517. 팰린드롬 개수 구하기 (Large) / Python https://www.acmicpc.net/problem/14517알고리즘 설명DP 배열 채우기:길이 2 이상인 부분 문자열에 대해 DP 배열을 채운다.dp[j][j + i]는 dp[j][j + i - 1]와 dp[j + 1][j + i]의 합에서 dp[j + 1][j + i - 1]을 뺀 값만약 s[j] == s[j + i]이면, dp[j][j + i]에 dp[j + 1][j + i - 1] + 1을 더한다결과 출력:dp[0][n-1] 값 = 전체 문자열에서 팰린드롬 부분수열의 개수s = input()# 문자열 길이n = len(s)# DP dp = [[0] * n for _ in range(n)]# 결과를 10007로 나눌 것이므로 이를 상수로 설정div = 10007# 길이가 1인 모든 부분 문자열.. Baekjoon 5719. 거의 최단 경로 / Python https://www.acmicpc.net/problem/5719문제 정리길의 최단 경로를 제외한 경로들 중의 최단 경로를 찾는다.문제 풀이 방식최단거리를 찾고 -> 최단 경로를 제거하고 -> 최단 경로를 찾는다.라고 하면 간단해 보이지만 생각보다 시간초과가 많이났던 코드다익스트라 알고리즘을 두 번 사용한다.import sysfrom heapq import heappop, heappushfrom collections import deque as dqinput = sys.stdin.readline inf = 1e10 def dijkstra(): dp = [inf] * n # 최단 거리 저장할 배열 q = [] heappush(q, (0, s, s)) # 시작점의 거리 0으로 설정하고 큐.. Baekjoon 2162. 선분 그룹 / Python https://www.acmicpc.net/problem/2162 2162번: 선분 그룹첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하www.acmicpc.net### Python- 함수 설명1. union_find : 노드의 루트 노드를 찾는 함수2. union_set : 두 노드가 속한 그룹을 합치는 함수3. CCW : 세 점의 방향을 계산하는 함수4. check : 두 선분의 교차여부를 판단하는 함수- 알고리즘 설명1. 입력된 선분들의 교차여부를 판단하여 같은 그룹으로 묶는다.2. 이 과정에서 유니온-파인드 알고리즘을 이.. Baekjoon 11014. 컨닝 2 / Python https://www.acmicpc.net/problem/11014 11014번: 컨닝 2최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한www.acmicpc.net같은 코드로 1014. 컨닝 도 풀린다.https://www.acmicpc.net/problem/1014 1014번: 컨닝최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한www.acmicpc.net- 함수 설명1. sol() : 내가 컨닝할 수 있거나, 컨닝당할 수 있는 위치에,.. 이전 1 2 다음