개발자 강화/코딩 테스트 (58) 썸네일형 리스트형 [백준] 10942 팰린드롬? / DP / Python / 골4 https://www.acmicpc.net/problem/10942 부제: 시간초과와의 싸움너무 정직하게 구현했더니 시간초과 뜸질문에 따라 주어진 배열을 list[s:e+1]로 끊어서그 배열을 for문 돌려서 팰린드롬인지 검증했는데, 이렇게 하니까 시간초과 뜸dp를 쓰는 방법을 고민하자 n = int(input())l = list(map(int, input().split()))l.insert(0,0)m = int(input())for i in range(m): s,e = map(int,input().split()) temp = l[s:e+1] leng = len(temp) if leng==1: print(1) continue for j in range(.. [백준] 9251 LCS / DP / Python / 골5 최장 공통 부분 수열 LCS를 구현하는 문제이다 LCS 개념은 이분이 굉장히 잘 설명해 두셨음https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest.. [백준] 1915 가장 큰 정사각형 DP / python 골4 https://xn--acmicpc-lw16a.net/problem/1915 DP를 이용 뭔가 BFS같이 생겼는데, 아니었다 처음에는 정사각형을 판별하려면 2차원 배열을 돌아가면서 뭘 봐야 할까...하다가현재 원소의 아래한칸 원소와 오른쪽한칸 원소를 보면 정사각형 여부를 알 수 있을까? 하면서 탐색했다하지만 정사각형을 판별하는 방법이 되지는 못했고... 알고보니 현재 원소의 위쪽 한칸 원소와 왼쪽 한칸 원소, 대각선 왼쪽 위 원소를 봐야했다 현재 원소가 0이 아니라면왼쪽, 대각선 왼쪽 위, 위쪽 원소 3개를 보고,세 값의 min 값을 현재 원소에 더해준다 일단 정사각형이 형성 가능하려면,현재 원소의 왼쪽, 왼쪽 위, 위쪽으로 같은 값만큼 확장이 되어야 하기 때문에최대값을 고려하면, 그게 정사각형이 아니.. [백준] 1로 2만들기 2 / DP python 실1 https://www.acmicpc.net/problem/12852 처음에 접근하려고 한 방법 일단 1,2,3인경우에는 답이 간단하게 나오니까각 경우는 직접 출력하고,그 이상의 값은 dp를 이용하도록 하려고 했다 for문으로 4부터 n+1까지 순회하면서현재 값이 2로 나누어 떨어지면 dp[i//2]를 temp 배열에 넣고현재 값이 3으로 나누어 떨어지면 dp[i//3]을 temp 배열에 넣고dp[i-1]값을 temp배열에 넣고 이 temp 배열에서 min값을 구해서 dp[i]에 min값+1을 넣었다 이와 같은 점화식을 세우게 된 이유는직접 그려봤을 때min 길이를 구하는 방법이 방금 설명한 방법과 같았기 때문 우선 이렇게 해서 1로 도달하는 최소 길이 구하는 것까지는 괜찮았는데,그 후 n에서 1로 도달하.. [백준] 2457 공주님의 정원 greedy python 골3 처음에는 아래와 같이 풀려고 했다 3월 1일보다 시작일이 같거나 작은 첫번째 꽃을 고르고(만약 종료일이 이전 꽃보다 길다면 그 꽃을 시작 꽃으로 지정) 그리고 그 외에 시작일이 3월 1일이 아닌 꽃들은 이전꽃의 종료일보다 현재 꽃의 시작일이 작거나 같으면 그 꽃으로 갱신만약 이전 꽃의 종료일보다 현재 꽃의 종료일이 늦으면 현재 꽃으로 갱신 이런식으로 풀어가려고 했다 그 이유는 예제로 시뮬레이션을 돌린 후 그 과정을 그대로 코드로 구현하고자 했기 때문.. 하지만 잘 작동하지 않앗다 n = int(input())flower=[]for i in range(n): a,b,c,d = map(int,input().split()) start = int(str(a)+str(format(b,'02'))) .. [백준] 11399 ATM / Greedy python 실4 대기 시간 순으로 sort각 순서의 사람은 이전 순서의 대기 시간과 본인의 대기 시간을 모두 합침 각 순서 사람의 대기 시간을 누적합으로 구하고이 결과를 total 합에 더하는 방식으로 구한다 n = int(input())a = list(map(int,input().split()))# p1=3# p2=1# pe=4# p4=3# p5=2# [1,2,3,4,5]# 3 3+1 3+1+4 3+1+4+3 3+1+4+3+2# [2,5,1,4,3]# 1 1+2 1+2+3 1+2+3+3 1+2+3+3+4a.sort()s=0t=0for i in a: s+=i t+=sprint(t)https://www.acmicpc.net/problem/11399 [백준] 1026 보물 Greedy python lv4 배열 a,b가 존재하고b의 순서는 바꾸지 않으면서, a의 순서만 바꿔서i번째 a,b 원소의 곱의 총 합이 최소가 되도록 만드는 것https://www.acmicpc.net/problem/1026 혹시 a와 b에 sort를 써도 정답 처리가 되나 궁금했는데그냥a.sort(reverse=Ture) b.sort()를 한 후 곱을 구해도 정답처리가 되긴 하더라 n = int(input())a = list(map(int,input().split()))b = list(map(int,input().split()))a.sort(reverse=True)b.sort()s=0for i in range(n): s+=a[i]*b[i]print(s) 근데 다른 사람들도 sort 써도 되는지 다 한번씩 해본게 좀 웃겼음 그.. [백준] 2217 로프 Greedy python 실4 로프가 k개면 각 로프에 w/k만큼 중량이 걸림 결국 물건 드는 데 쓰는 로프 중 가장 힘이 약한 로프*k개 만큼만 들 수 있음 그래서 로프를 힘 크기 오름차순으로 sort한 후에 첫번째 로프(가장 힘이 약한 로프)부터 보면첫번째 로프*n이 들 수 있는 최대무게 두 번째 로프*(n-1)이 최대 무게세 번째 로프*(n-2)가 최대 무게 따라서 i번째에는(i는 0부터 n-1까지)i번째 힘을 가진 로프*(n-i개)의 값을 구하면 n-i개의 로프를 사용했을 때 들 수 있는 최대 무게를 구할 수 있음 결국 이 값들을 다 dp에 저장한 후에max값을 구하면 됨 n = int(input())arr = [int(input()) for _ in range(n)]# 로프 k개이면, 각 로프에는 w/k 만큼 중량이 걸림ar.. [백준] 최대 공통 증가 수열(실패...) 7476 골1 오블챌을 위해 일단 풀 문제 선언만 하고 글 쓸게요...다시 돌아와서 풀고 수정하겠습니다 요즘 본인의 부분수열 실력 부족에 심각성을 느끼고... 부분 수열 좀 백준에서 찾아 풀겠습니다 https://www.acmicpc.net/problem/7476 풀이로 곧 돌아오겠습니다 커밍쑨 ---- 일단 풀면서 LCS LIS 관련 문제임을 알게 되었고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%E.. [백준] 11727 2*n 타일링2 / 실3 / DP 이거 문제가 왜 익숙한가 했는데이.취.코 파이썬 책 DP 챕터- 바닥공사랑 똑같은 문제였음 n = int(input())dp=[0]*(n+1)dp[0]=1dp[1]=1for i in range(2, n+1): dp[i] = (dp[i-1]+dp[i-2]*2)%10007print(dp[n]) dp의 각 칸이 타일의 가로 1칸이라고 생각한다 (세로는 어차피 2로 고정) 가로 길이가 1일때는이거 문제가 왜 익숙한가 했는데 이.취.코 파이썬 책 DP 챕터- 바닥공사랑 똑같은 문제였음 dp의 각 칸이 타일의 가로 1칸이라고 생각한다 (세로는 어차피 2로 고정) 가로 길이가 1일때는 1*2밖에 못넣으니까 1 가로 길이가 2일 때는 1*2 타일 2개 또는 2*2 타일 1개, 또는 2*1 타일 2개로 시작할 수.. 이전 1 2 3 4 5 6 다음
