https://www.acmicpc.net/problem/5557 [초기 접근 방법(o)] 1. 먼저 dp 메모제이션 할 배열을 정의하자 2. dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수 - 0

[초기 접근 방법(x)] 1. 직행 다리가 감당이 가능하면, 가능한 중량을 올린다. 2. 직행 다리가 감당이 불가능하면, 경유 다리를 탐색하자 1) 경유 다리가 감당이 불가능한 경우, 가능한 중량을 내린다. 2) 경유 다리가 감당이 가능한 경우, 가능한 중량을 올린다. [생각] 위와 같이 접근을 하게 되면 감당 가능한 무게가 작은, 쓸데없는 다리가 있을 경우에 목적지까지 갈 수 있음에도 판단하지 못한다. - search 함수를 다음과 같이 작성하면 틀린다. 왜?? def search(start, end): while start < end: mid = (start + end) // 2 # 다리들이 현재 mid 무게를 감당 가능하면, 더 중량을 올려도 됨 if bfs(mid): start = mid + 1 ..

https://www.acmicpc.net/problem/17626 [초기 접근 방법] - dp[n] = min(dp[n], dp[n-제곱수] + 1 (n >= 제곱수) [생각] dp[n]를 문제에서 정의해줘서 쉬운 문제였다. 점화식 또한 쉽게 생각할 수 있는 로직이여서 금방 풀었던 것 같다.. 아.. 입력 범위 끝인 '50000'을 넣었는데 1-2초? 정도 걸리길래 시간초과 뜨나 해서 시간복잡도 상수 계산까지 했던.. 에피소드가 있다;; [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N*sqrt(N)) → 1100만? # 공간복잡도 : O(n) # 참고 : - import math import sys input = sys.stdin.readline N = int(input()) # dp[i] ..

https://www.acmicpc.net/problem/1300[초기 접근 방법(X)]1. N^2의 [i][j] 값을 모두 lst에 넣으려면 시간복잡도가 이미 O(N^2)으로 시간초과이다.2. 그러면? 시간복잡도를 줄일 수 있는 방법은, 처음부터 [i][j] 값을 lst에 넣지 않는 것3. 그런 [i][j] 값을 전부 넣지않고, 어떤 값을 lst에 넣어야 하는가? 에서 시작했다. 대각선을 기준으로 중앙값이 가장 크므로,이분탐색을 하여 몇번째 대각선인지 찾고 남은 인덱스만큼 이동탐색하면 K번째 수를 찾으려고 했다.   [생각]위 방식대로 로직을 짜고 풀었지만 결과는 "틀렸습니다"저 로직을 생각하는데도 시간을 많이 썼던 문제라서, 미련없이 정답 코드를 참고했다...일단 K번째 수는 '1행의 원소들'이 존재..

1. 진행하면서 맞닥뜨린 문제 (@ResponseBody), 검증 1) Post 요청으로 클라이언트의 데이터를 CreateMemberRequest(DTO) 타입의 request 객체에 매핑을 해준다. 2) 이 때, HTTP 요청의 본문(Member)과 request가 매핑이 되는데, 이 때 반드시 필드의 이름이 일치해야 한다. public class Member { private String username; } @RestController @RequiredArgsConstructor public class MemberApiController { @PostMapping("/api/v2/members") public CreateMemberResponse saveMemberV2(@RequestBody @Va..

https://www.acmicpc.net/problem/2422 [초기 접근 방법(X)] 1. 주어진 아이스크림에서 3가지 조합을 모두 구한다. 2. 모든 조합 경우에서, 금지된 조합(x, y)가 포함될 시 총 count(nC3)에서 -1을 한다. 3. 가능한 조합 count를 출력한다. [생각] 위 접근 방법대로 풀면 시간복잡도가 O(M * nC3)이다. (M : 금지된 조합, N : 아이스크림 갯수) 금지된 조합에 대해 (x, y) (y, x) 에 대한 boolean 처리를 해주고, nC3 조합에 대해 금지된 조합이 있는지 여부를 판단하는 것이 효율적이다.. *어려운 문제는 아니였지만, 시간복잡도의 최적화에 대해서 고민한 문제였다. [코드] # 풀이 시간 : 20분 + 10분 # 시간복잡도 : O(..