220418 월 Algorithms TIL
백준 2294번 동전 2 실버1
- 문제
- 코드-파이썬
- 코드-자바
- 핵심 로직은 자기 자신에 동전 단위만큼 뺀 금액 + 1 한 값들을 비교해서 그 중 가장 작은 것을 하는 것
- 해당하는 값을 dp에 저장하지 않고 매번 조회하면 시간 초과가 난다
- 이부분
if coin_cnt[amount] != MAX: return coin_cnt[amount]
추가
- 자바는 dp랑 bfs로 풀어봤다. bfs 풀이는 이블로그를 참고했다. 계속 동전 단위만큼 추가해가면서 최솟값을 입력한다. BFS이기 때문에 레벨별로 동전 수가 증가하므로 앞서 방문했다면 해당 방문의 동전 수가 더 적을 수밖에 없다.
백준 2252번 줄 세우기 골드3
백준 2637번 장난감조립 골드2
- 문제
- 코드-파이썬
- 그냥 풀었을 때 메모리 초과가 났고, 메모리 해결을 위해 위상정렬로 풀기 위해선 부품에 제품을 저장해야 했고, 그러나 제품에 대해서 가각각 어떤 부품이 필요한지 저장해야 했다.
- 나는 딕셔너리를 두고 풀었다.
- 다른 풀이를 보니 그래프 자체는 재퓸애 부품을 저장하고 기본부품은 따로 저장한다. 그리고 각 부품에 대해서 for문을 전체를 돌면서 해당 부품을 갖는 제품을 찾는 식으로 했다.
백준 1948번 임계경로 플래5
- 문제
- 코드-파이썬
- 경로 구하는 부분은 다른 코드를 참고했다.
- 최대 거리를 갱신하면서 경로를 계속 들고가니까 시간 초과 발생했다.
- 경로는 최대 거리만 일단 구하고, 거꾸로 가면서 이전 노드와 현재노드의 거리의 차를 구한 값이 현재 노드에 저장한 거리의 최댓값과 이전 노드의 저장한 거리의 최댓값의 차와 같을 때 cnt를 +1 해준다. 경로로 안하고 cnt를 +1 해도 되는 이유는 어차피 방문한 노드는 visited로 체크해서 다시 방문 안할 것이기 때문이다.
스터디하면서 배운 파이썬 문법
sep 파라미터
https://www.geeksforgeeks.org/python-sep-parameter-print/
print(인자들, set=구분자)
a = [1, 2, 3]
print(*a, sep=",")
Author And Source
이 문제에 관하여(220418 월 Algorithms TIL), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bongf/220418-Algorithms-TIL저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)