DP
-
[코드트리 챌린지] 정수 사각형 최대 합코딩테스트/코드트리_Java 2023. 9. 16. 22:03
문제 : 정수 사각형 최대 합 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최대로 하는 프로그램을 작성해보세요.3 ≤ n ≤ 100,000 -1,000 ≤ 주어지는 수 ≤ 1,000 사실 실력진단에서 유사한 문제가 나왔는데 DFS 방식으로 풀려다가 시간이 부족했고, 이 문제는 BFS 방식으로 풀었다. 풀이는 아래와 같다. 1. DP테이블에 초기 좌표 0, 0에는 입력된 0,0의 값을 넣어준다. 2..
-
Q. 5642. 합(D3)코딩테스트/SWEA_Java 2023. 5. 17. 12:22
Q. 5642. 합(D3) 0. 문제 D3 난이도의 문제이고, DP를 이용한 문제이다. 수열이 주어지고 연속해서 원소를 골라 합을 구할 때, 그 합의 최대가 몇인지 구하는 프로그램을 작성하는 문제이다 1. 풀이 두 가지의 풀이 방법이 생각났다. 첫번재는 DP를 이용한 풀이이고, 두 번째는 투 포인터를 이용한 풀이이다. 1-1 DP를 이용한 풀이 DP인 경우 보통 정답이 dp[N - 1]인데, 이 문제의 경우는 그렇게는 정답을 구할 수 없어서 조금 시간이 걸렸다. 아래와 같은 방식으로 풀었다. 1) 반복문을 N-1까지 돌면서, 현재 인덱스의 숫자와 이전에 저장된dp + 현재 인덱스의 숫자를 비교해 큰 값을 dp에 저장한다. 2) dp 배열에 저장된 값 중 최대값을 저장한다. 코드는 아래와 같다. impor..
-
Q. 3316 자바 : 동아리실 관리하기(D4)코딩테스트/SWEA_Java 2023. 1. 22. 22:52
문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBnFuhqxE8DFAWr D4 난이도의 문제이고, DP, 메모제이션을 이용한 문제이다. 최근에 DP 알고리즘을 공부중이긴 하지만, 문제를 보고 A, B, C, D를 비트로 변경해서 저장하는 방법까지는 접근을 했지만 이후 꽤 오랜 시간동안 고민했지만 푸는 방법을 모르겠어서 다른분들의 코드를 참고해서 내 방식으로 바꿔서 풀었다. 먼저 A, B, C, D의 포함 여부를 4개의 비트로 쪼개서 생각한다. 만약 A만 동아리 활동에 참여할 경우 0001(2), D와 A가 참여할 경우 1001(2) = 9(10)으로 생각하면 된다. 이런식으로 데이터를 다룬다고 생각한 다..