문제 풀이 과정
문제 파악
정해진 조건에서 총 몇개의 경우의 수가 나올 수 있는지 구하는 문제이다. 문제의 입력도 크지 않아서 시간 제한은 고려할 필요가 없으며 한 쌍의 짝을 구하면 나머지 인원들에 대한 접근은 원래 문제의 부분 문제이므로 재귀함수를 통해 접근하는 문제임도 명확하다. 아마 가장 많은 고민을 필요로 하는 부분은 중복을 피하는 부분일 것이다.
접근법
나는 두 가지 방식으로 접근했다. 첫 번째는 모든 인원을 컨테이너에 담고 짝이 된 인원이 발생했을 때 컨테이너에서 그 인원을 빼서 그 인원이 다시 매칭되는 상황을 막는 것이다. 두 번째방식은 각 인원들 간의 친구 관계를 나타내는 이차원 배열의 값을 짝이 된 경우 0으로 바꿔주어 그 인원들이 다시 짝이 되는 경우를 아예 막는 것이다.
이 두가지 방식을 구현하기 위해서는 모두 재귀 함수의 매개 변수를 통해 정보를 전달해서 재귀 함수가 호출될 때마다 항상 업데이트된 정보가 전달되는 것이 필수적이다.실패 이유
첫 번째 접근 방식에서 어려움을 겪은 것은 자료구조이다. 첫 번째 방식이 유효하게 구현되기 위해서는 컨테이너의 어떤 위치에 있는 원소든 제거할 수 있고 컨테이너의 크기는 작아져야 되는데, 이를 위해서는 연결리스트가 필요한데, 연결 리스트를 바로 구현할 수 있는 구현 능력이 갖추어지지 않아서 어려움을 겪었다.
두 번째 방식은 함수의 인자로 이차원 배열을 매번 전달해 줘야하며, 이차원 배열의 값이 재귀 호출된 함수 밖에서 바뀌어서는 안된다. 그러나 구현해본 결과 재귀함수 바깥의 배열까지 바뀌어버려서 내가 생각하는 방식대로 작동하는 것이 불가능했다. 아마 함수의 매개 변수로 배열의 포인터 값이 전달되서 그런것 같은데 이에 대해서는 추가적인 학습이 필요할 것 같다.
또한 잘못 생각한 부분 중 하나가 왜 이런식으로 생각했는지 모르겠지만, 재귀 호출된 함수가 리턴 되지 않아도 그 다음 부분이 계속 실행된다고 생각을 했다. 함수를 호출 하면 그 함수가 리턴 되기까지 기다린다는 것이 당연한데 그것을 놓지고 코딩하게 되었다.
올바른 풀이, 느낀점
책에 있는 풀이는 배열 세마포어를 이용해 중복을 방지하는 방식으로 접근했다. 또한 배열을 함수의 파라미터로 전달할 때 변경된 정보가 다른 재귀 함수에 영향을 끼치는 것을 막기 위해 재귀 함수 호출 이후 변경된 정보를 다시 원래데로 돌려놓는 작업을 하였는데, 이는 재귀 함수를 이용하는 대부분의 문제에서 필수적으로 사용해야 하는것 같다. 중복을 방지하기 위한 다른 방식으로는, 연결 리스트를 이용해 현재 사용되지 않는 원소를 저장해 놓는 방법이 있는데, 자료 구조만 다를 뿐이지 본질적으로 같은 방식임을 알게 되었다.
문제에 본격적으로 접근하기 전에 사용하게 될 함수와 파라미터, 변수와 변수의 자료 구조 등을 확실하게 설계하고 구현을 시작하는 습관을 가지려고 한다.
