220416 토 Algorithms TIL

백준 21606번 아침 산책 골드5

• 문제
• 코드-파이썬
  https://kth990303.tistory.com/141 이 블로그와 조원의 설명으로 풀었다.
• 트리이므로 두 실내 사이에는 유일한 경로 밖에 없다. 연결된 실외들의 덩어리에 붙어 있는 실내들의 수를 구하고, 양방향은 다른 경로로 치므로 ans * (ans -1) 을 한다.

백준 14888번 연산자 끼워넣기 실버1

https://velog.io/@bongf/220315-Algorithms-TIL 에 업데이트

백준 2573번 빙산 골드4

• 문제
• 코드-파이썬
• 핵심은 빙하가 몇 개인지 체크할 때 녹일 것도 count 해줘서 두 번 그래프를 안돌도록 하는 것이었다
• 구현하면서 틀린점
  • 빙산만 따로 관리해주는 배열을 만들었는데 그것이 오히려 update 등 관리가 복잡해짐
  • 자주 바뀌는 정보는 굳이 저장할 필요 없다.

  • map이면 관련 정보도 map으로 저장하는 것이 용이하다

백준 2617번 구슬 찾기 골드5

• 문제
• 코드-파이썬
  https://velog.io/@bongf/211220-Algorithms-TIL
• 조원의 도움으로 이해.
• 처음에 heavy 부분과 light 부분의 visited 그래프를 따로 만들어 준 풀이를 했다가 시간초과가 났는데 예를 들어 4에서 방문한 애가 자기보다 무거운 애들을 탐색했다면 4에서 자기보다 가벼운 애들 탐색할 때 방문했던 애들은 탐색할 필요가 없으므로 visited 그래프를 같이 써야 하는 것이었다