코딩하는 미소지기

이모티콘(https://www.acmicpc.net/problem/14226) 문제를 풀며 느낀 점이다.

런타임 에러와 메모리 초과는 왜 발생하는 것일까?

이 문제는 3가지의 연산(클립보드 저장, 클립보드 붙여넣기, 이모티콘 삭제)을 적절하게 섞을 시에 몇초만에 S개의 이모티콘을 만들 수 있는가를 물어보는 문제이다. 아래의 그림처럼 도식도를 나타내어 BFS를 사용하면 최소임이 보장되므로 해결 할 수 있다. 

하지만 BFS를 사용 할 때 고려해야 할 문제점은 [런타임 에러] 와 [메모리 초과] 이다.

Q. 메모리 초과의 원인

 - 무한대로 퍼져나가는 노드들을 모두 큐에 넣는 과정에서 큐의 사이즈가 너무 커져서 스택 오버플로가 남

 - 문제에서 지정한 메모리 제한을 넘겨버림

A. 수많은 노드들 중 문제에 조건에 해당하는 노드만 선별하여 큐에 넣을 수 있도록 조건을 지정하는 것이다.

 - 어떻게? : check 배열을 문제의 조건에 맞게 잘 선별하는 것이 포인트이다.

 - 이 문제에서는 check[화면에 표시된 이모티콘의 개수][클립보드에 표시된 이모티콘의 개수] 로 나타내었다.

 - 화면과 클립보드의 이모티콘의 개수가 같다면, depth가 달라졌을 때 최단거리의 depth로 접근할 수 있기 때문이다.

A. check 배열을 만들 때 check 배열의 자료형 역시 중요하다.

  ex) int check[1000][1000][1000]의 경우 : int는 4비트이므로 4*1000*1000*1000 = 대략 480Mb이다.

      bool check[1000][1000][1000]의 경우 : bool은 1비트이므로 1*1000*1000*1000 = 대략 120Mb이다.

  문제의 조건이 512Mb이므로, 체크 배열의 자료형을 어떻게 선언해 주냐에 따라 합,불이 나뉠 수 있다.

Q. 런타임 에러의 원인

 - 90% 이상이 배열의 인덱스를 벗어났을 때 일어난다.

 - 런타임 에러의 발생 유무는 이곳(https://ideone.com/)에서 코드와 input 값을 넣고 체킹 해 볼 수 있다.

A. 문제를 풀 때 내가 만든 check 배열의 최악의 경우를 가정하고 scope를 잘 만들 줄 알아야 한다.

 - 이 문제에서는 만들어야 하는 최대 이모티콘의 수가 1000개이다.

 - 그럼 [그림]에서 맨 왼쪽 트리를 중심으로 가장 많이 이모티콘을 만들기 위해선

   [클립보드 저장] → [클립보드 붙여넣기] → 저장 → 붙여넣기 → ... 의 순서로 진행 될 것이다.

 - [1개 클립보드 저장] → [1개 화면에 붙여넣기] 를 하면 총 2개의 이모티콘이 완성이 된다.

 - [2개 클립보드 저장] → [2개 화면에 붙여넣기] 를 하면 총 4개의 이모티콘이 완성이 된다.

 - [4개 클립보드 저장] → [4개 화면에 붙여넣기] 를 하면 총 8개의 이모티콘이 완성이 된다.

 - 이와 같은 형식으로 2, 4, 8, ... 512, 1024의 이모티콘이 완성이 될 수 있고,

   화면과 클립보드 둘 다 maximum 값인 1000개가 있었다고 한다면 최대 화면에 표시될 수 있는 값은 2000인 것이다.