220210.md

지난 과제 리뷰

• 백준 14503 로봇 청소기

  • Problem: 주어진 2차원 배열(map)에 대하여 주어진 조건에 맞게 로봇 청소기가 갈 수 있는 곳을 확인하고 청소한다.
  • Conditions
    • 현재 위치를 청소한다
    • 바라보는 방향을 기준으로 왼쪽을 탐색하며 청소하지 않은 곳이라면 전진 후 위 과정을 반복한다.
    • 탐색한 곳이 방문한 곳이거나 벽인 경우에는 다음 방향을 탐색
    • 갈 수도 없고 4방향을 다 탐색한 경우에는 한 칸 뒤로
    • 뒤로 갈 수 없는 경우에 작동 중지
  • Solution: 주어진 조건에 맞게 BFS를 사용하거나 재귀(recursive)를 사용하여 방문 및 청소 operation 실행
  • Code: 기탁 성범 수진

• 백준 3687 성냥개비

  • Problem: 주어진 성냥개비로 만들 수 있는 수 중 최소값과 최대값을 반환하는 문제!
  • Solution: 동적 프로그래밍(DP)을 활용하여 해결
    • 한자리 수는 기본 숫자에 필요한 성냥개비 수와 동일하므로 dp에 그대로 저장
    • 두자리 수부터의 최소값은 이전 dp 값을 활용 및 동일 성냥개비로 만들 수 있는 수 중 작은 값을 선택해야 한다.(ex. 6, 0)
    • 두자리 수부터의 최대값은 주어진 성냥개비의 수가 짝수이냐 홀수이냐에 따라 7(3)과 1(2)을 조합하여 반환하면 된다.
  • Code: 기탁 성범 수진

• 백준 1700 멀티탭 스케쥴링

  • Problem: 사용할 전자장비에 대해 멀티탭에 플러그인(plug-in)할 때, 그 횟수의 최소값을 반환하는 문제
  • Solution: 이번 문제의 가장 유사한 개념은 운영체제 스케줄링에서 최적화 스케줄링이다. 앞으로의 사용할 장비 중 가장 나중에 사용할 장비를 찾아 대치하는 문제
    • 현재 멀티탭에 꽂혀있는 장비들을 체크
    • 후에 장착할 장비들을 체크
    • 후에 장착될 장비들 리스트 중 현재 멀티탭에 꽂혀있는 장비에 없으면 대치(나중에 사용하지 않는 장비를 새로운 장비와 대치)
    • Set, List 등을 사용하여 우선순위를 계속 체크하여 장비 대치
  • Code: 기탁 성범 수진

다음주 일정 및 문제

• 2월 16일 (수) - 오전 11시 - 신촌에서 봐요!
• 과제 문제 : 백준 ZOAS 그룹 - 연습 -> 2월 3주차에 아카이빙