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=",")