[Algorithm] 미생물 격리 (SW Expert Academy – 2382)

By | 2018-07-15

문제 출처

  • https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

난이도

  • 하 – (중) – 상 – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

  • N x N Matrix에 미생물 집단이 있다. 각 미생물 집단은 상, 하, 좌, 우로만 움직일 수 있고, Matrix 끝에 도달하게 되면 절반의 미생물이 죽고 이동 방향을 반대로 바꾸게 된다. 그리고 여러 집단의 미생물이 한 위치에서 만나게 되면 큰 집단에 흡수되어 버린다. 특정 시간이 흐른 후 남아 있는 미생물의 수를 계산하는 문제이다. SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 더 상세히 문제를 작성하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

  • 미생물 문제는 아주 어렵다고 판단되지는 않는다. 대학원을 다니면서 Computer Architecture Simulator를 사용해 보았는데, 본 문제는 같은 방법을 사용하여 해결 가능한 문제이다. 하지만, 코딩을 하면서 한 가지 정도의 실수가 있었다.
  • 미생물 집단이 한 곳에서 만나는 부분을 계산하기 위해서 History 정보를 저장하는 부분을 만들어서 문제를 해결하였다. 매시간 연산이 끝난 후 History 정보를 초기화해야 하는데 중간에 초기화를 하도록 만들어서 다른 미생물 집단의 수를 계산하는데 연산 에러가 발생하였다. 항상 History 정보를 초기화하는 시점을 명확하게 정하고 코딩을 시작할 필요가 있다.

코드

  • 매시간 미생물 이동 방향을 계산하여 총 미생물 수 계산하는 부분
  • 실행 시간: 90ms (제일 빠른 코드 대비 30배(3ms) 느림)

 

Leave a Reply

Your email address will not be published. Required fields are marked *