SWEA 2112 [모의 SW 역량테스트] 보호 필름

목표: SWexpert Academy 2112 보호 필름 문제 풀기

환경: mac OS High Sierra 10.13.4, CLion

이 문제 또한 완전탐색으로 풀려고 합니다. 완전탐색이란 문제의 답을 찾는 것인데, 가능한 경우를 모두 나열하고, 각각이 해가 될 수 있는지 확인하는 방법입니다.

우선 완전탐색의 장단점을 얘기해보자면 장점으로는 어떻게든 답을 구해낼 수 있다는 것이에요. 모든 경우를 다 살펴보고 해를 구하는 것이니까요. 단점은 문제의 조건에 따라 오래 걸린다는 것인데, 이것을 최적화 하는 방법들이 있어요. 가지치기라든지 백트래킹이라든지

[제약사항]

  1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 5초

  2. 보호 필름의 두께 D는 3이상 13이하의 정수이다. (3≤D≤13)

  3. 보호 필름의 가로크기 W는 1이상 20이하의 정수이다. (1≤W≤20)

  4. 합격기준 K는 1이상 D이하의 정수이다. (1≤K≤D)

  5. 셀이 가질 수 있는 특성은 A, B 두 개만 존재한다.

치킨배달문제와 굉장히 비슷한 개념을 물어보는 문제인데요.

이 문제에서는 D층에 시료를 추가해서 안전한 보호필름을 만드는 것이 중요한데, 이 문제에서는 몇개의 시료를 추가해야하는지 주어지지 않았습니다. 그 말은 0개부터 D개까지 다 넣어보면서 안전한 보호필름인지 체크하라는 것인데요.

크게 두가지 로직으로 나뉠 수 있는데,

몇개의 시료를 추가할거냐?와 몇개의 시료를 추가할거냐는 치킨배달 문제에서 n개의 체인점 중에서 m개를 구하는 방법과 똑같은데, 거기에 플러스 m개가 주어지지 않았기 때문에 0~D개까지 다해보는겁니다.

약품검사를 어떻게 할것인가?로 나뉘는데요. 약품검사는 재귀를 돌면서 계속해서 해야하는 체크로직이기 때문에 효율적이여야합니다. 약품검사의 경우는 문제의 정의대로 보면 약품검사를 하다가 안전하지 않은 열을 찾았으면 그 뒤에 있는 열을 계속 검사할 필요가 없습니다. 약품검사를 그만두는 코드가 꼭 필요합니다.

여기서 중요하게 완전탐색은 그러면 인간의 논리를 넣지않고, 컴퓨터의 연산능력을 이용해 가능한 모든 경우의수를 탐색하되,

재귀함수도 마찬가지고 구현문제도 마찬가지고 더이상 안돌아봐야할 경우가 매우 확실해 지잖아요? 그건 돌아보면 안됩니다. 절대로

추가내용: 새로 짠 코드인데, 50개 테스트케이스중 49개에서 fail한 코드를 수정해서 PASS 됐습니다.

이것이 가능했던 이유는 시간복잡도를 계산했기 때문입니다. (다행히 SWEA에서는 실행 시간을 참고할 수 있기 때문에 어떻게 수정해야될지 고민할 기회가 있었습니다.)

이전에 한번에 성공한 코드와 다른점은 choice배열을 통해 어떤 행에 시약을 투약할지 정하고

시약개수 == 투입시켜야하는 시약 개수 조건에서 2차원 배열을 통째로 복사해서 했습니다.

그전에는 시약을 투약하는 행만 바꾸는 백트래킹 로직이 O(N)의 시간복잡도로 수행되지만, 이 코드에서는 투약을 할때 기존 맵을 복사하는 과정인 O(N^2)이 되기 때문에 시간초과가 나왔습니다.

그렇다면 최적화할 방법이 필요했는데, 현재 로직에선 합격이 되었더라도 현재 시약개수를 다 쓰는 모든 경우의 수를 계속해서 탐색하기 때문에,

필릅검사가 합격했다면 더이상 모든 경우의 수를 탐색할 필요가 없습니다. 여기서 if문을 추가해서 재귀를 돌때 만약 답을 찾았다면 return을 시켜 함수를 종료해버리는 것입니다.

사실 이 방법보다 문제의 원리대로 한 행만 바꿔주는 O(N) 방법이 더 효율적이고 코드가 더 깔끔하니, 이 방법을 사용할 필요는 없을 것 같습니다.

하지만 이런 문제를 고민해봄으로써 재귀과정을 좀더 이해하게 되는 시간이었습니다.

보호 필름

code 백트래킹 과정에 상태를 복사하는 과정이 O(N^2) 인 코드

이전code 백트래킹 과정에 상태를 복사하는 과정이 O(N) 인 코드 <- 이 코드가 명확하게는 문제의 원리대로 구현한 코드이기 떄문에 더 좋은 코드라고 생각합니다.