[ 2021.06.22 ] 하루 세 문제 ( 4일차 )

정유택·2021년 6월 29일
0

everyday_algorithm

목록 보기
5/8

매일 3개의 주제를 골라 문제를 풀어봅시다.

  • 트리
  • 구현
  • 다이나믹 프로그래밍
  • 다익스트라

오늘은 랜덤으로 문제를 뽑는 코드가 계속해서 3일차까지 뽑은 주제중 중복인 주제를 많이 뽑아서 2번 돌려 얻은 4개의 주제를 골랐습니다.

트리

  • 문제 : 트리의 높이와 너비
  • 난이도 : Gold 2
  • 해설
    • 하나의 사실만 알게된다면 해당 문제는 껌입니다.
    • 그 하나의 사실이란 문제의 예제 그림을 통해 알 수 있습니다.
    • 그림에서 x축의 숫자들을 보면 트리를 중위 순회했을 때 순회 순서임을 알 수 있습니다. ( 앞으로는 순회와 관련이 없어보이더라도 대입이라도 한번씩 해봐야겠습니다. )
    • 중위 순회 순서임을 알게 되었다면 해당 문제는 그냥 풀 수 있습니다.
    • 소스코드 : https://www.acmicpc.net/source/30312359

구현

  • 문제 : 주사위 굴리기
  • 난이도 : Gold 5
  • 해설
    • 문제를 제대로 읽어보아야 합니다.
    • 평소대로 입력을 받아 배열의 세로 및 가로의 값을 정한다면 예제를 실행하는데는 문제가 없으나 실제 답안을 제출하면 틀렸습니다가 나옵니다.
    • 문제에서는 x를 세로, y를 가로로 봤기 때문에 입력에 주의를 해야합니다.
    • 나머지는 단순하게 주사위 굴리는 것을 구현하면 됩니다.
    • 소스코드 : https://www.acmicpc.net/source/30316564

다이나믹 프로그래밍

  • 문제 : ACM Craft
  • 난이도 : Gold 3
  • 해설
    • 다이나믹 프로그래밍과 위상정렬을 같이 사용하는 문제입니다.
    • 기본적인 위상정렬에서 건물이 다 지어지는데 걸리는 시간을 같이 구하면 됩니다. 하지만 여기서 특정 건물이 지어지기 위해서는 그 전까지 지어야하는 모든 건물을 지어야 하기때문에 걸리는 시간 중 최대 시간을 저장하고 있어야 합니다.
    • 소스코드 : https://www.acmicpc.net/source/20208334

다익스트라

0개의 댓글