개발자 강화/코딩 테스트 (60) 썸네일형 리스트형 [백준/이취코] 정수삼각형 1932 / DP / Python 실1 (개발자 강화/코딩 테스트) 2024. 11. 21. 16:59 내가 이걸 1년 전에 왜 풀었을까...? 그땐 실력이 별로라서 독자적으로 풀진 않았을 듯 한데오늘은 거의 뭐 15분컷? 했습니다너무 자명한 문제죠그림에 써진 웨에엑 신경쓰지 마세요 무튼 이런 트리 구조의 정수 값을 입력 받고,각 수들은 왼쪽 또는 오른쪽 대각선 값만 접근할 수 있습니다 이걸 다 입력받고 다시 처리할까?하다가 문득 실시간 처리가 가능하다는 생각이 들었어요그래서 그림으로 그려봤습니다 누적 dp 배열과현재 입력받은 배열 a가 존재한다고 생각해봅시다 일단 첫번재 배열 a에는 원소 하나만 있고, dp도 빈 상태니까dp.append(a) 해주고 넘깁니다 그 다음부터 dp 점화식을 세워봅시다 배열 a의 가장 첫 번째 원소는 dp의 첫번째 원소와 더한 값이고배열 a의 가장 마지막 원소는 dp의 가장 마.. [백준] 1520 내리막길 / DP / Python / 골3 (개발자 강화/코딩 테스트) 2024. 11. 21. 13:03 부제: 무한 런타임 에러 해결하기 처음에 접근하려고 했던건 일단 현재 위치가 0이 아니어야 어딘가로부터 이동경로를 받을 수 있다는 뜻그래서 0이 아닌 경우에만 탐색함 상하좌우에서 현재 위치로 이동하는 경우에상하좌우에서 받을 수 있는 max값을 현재 위치의 이동 가능 경로로 세팅해둠 그리고 현재 위치에서 상,하,좌,우로 이동할 때 현재 수보다 이동한 위치의 수가 작으면 내리막길이니까이동 가능 경로 개수를 업데이트 해주고 싶음각 상하좌우로 이동했을 때 위치에다가현재 위치의 이동 경로 개수를 그대로 받는 경우 또는... 이동한 위치의 이동 경로 개수+1 값을 비교해서max값으로 업데이트를 해줬음 m,n = map(int,input().split())arr = [list(map(int,input().spl.. [백준] 10942 팰린드롬? / DP / Python / 골4 (개발자 강화/코딩 테스트) 2024. 11. 20. 23:10 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 (개발자 강화/코딩 테스트) 2024. 11. 20. 22:03 최장 공통 부분 수열 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 (개발자 강화/코딩 테스트) 2024. 11. 20. 15:44 https://xn--acmicpc-lw16a.net/problem/1915 DP를 이용 뭔가 BFS같이 생겼는데, 아니었다 처음에는 정사각형을 판별하려면 2차원 배열을 돌아가면서 뭘 봐야 할까...하다가현재 원소의 아래한칸 원소와 오른쪽한칸 원소를 보면 정사각형 여부를 알 수 있을까? 하면서 탐색했다하지만 정사각형을 판별하는 방법이 되지는 못했고... 알고보니 현재 원소의 위쪽 한칸 원소와 왼쪽 한칸 원소, 대각선 왼쪽 위 원소를 봐야했다 현재 원소가 0이 아니라면왼쪽, 대각선 왼쪽 위, 위쪽 원소 3개를 보고,세 값의 min 값을 현재 원소에 더해준다 일단 정사각형이 형성 가능하려면,현재 원소의 왼쪽, 왼쪽 위, 위쪽으로 같은 값만큼 확장이 되어야 하기 때문에최대값을 고려하면, 그게 정사각형이 아니.. [백준] 1로 2만들기 2 / DP python 실1 (개발자 강화/코딩 테스트) 2024. 11. 19. 16:11 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 (개발자 강화/코딩 테스트) 2024. 11. 18. 21:26 처음에는 아래와 같이 풀려고 했다 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 (개발자 강화/코딩 테스트) 2024. 11. 18. 19:45 대기 시간 순으로 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 (개발자 강화/코딩 테스트) 2024. 11. 18. 19:24 배열 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 (개발자 강화/코딩 테스트) 2024. 11. 18. 19:00 로프가 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.. 이전 1 2 3 4 5 6 다음 목록 더보기
