Programmers[weekly3]

개요

Programmers 위클리 3주차를 풀었는데 , 내 기준에선 상당히 어려웠다. 내가 약점인 부분이 문제로 나왔다고 생각해서 자세하게 보게 되었다. 이건 아카이브 용으로 작성한 자기회고글이다. 남을 이해시킬려 작성한 글이 아니기 때문에 전문성이나 정확성이 떨어질 수 있다.

잘못된 점이 있는거같으면 깃허브나 이메일로 문의를 부탁합니다.

문제

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

코딩테스트 연습 - 퍼즐 조각 채우기 | 프로그래머스 (programmers.co.kr) 자세한 사항은 위 링크로 가면 알 수 있습니다.

\(6^n\) vs \(6 * n^2\)

나는 처음에 이 문제의 Time Complexity 가 Big O 표기법으로 \(O(6^n)\) 이라고 생각했다. table의 모든 퍼즐에 대한 모든 경우를 search를 해야 한다고 생각 했다. Tree형태의 search를 한다고 생각했다.

※ 위 문제와 아무상관 없다. 그냥 tree그림을 표현하기 위해 첨부한 것이다.

문제는 이렇게 로직을 짤 경우 runtime은 초과 된다는 점이다. 지수함수는 쓰면 안된다..

Boostcamp aitech에서 다른 캠퍼분한테 질문을 드렸을때 \(O(n^2)\) 의 BigO complexity 가 된다고 설명을 들었다. 솔직히 , 첫날에는 잘 이해가 되질 않았다. 내가 무언가 기본적인 부분을 잘못 이해하고 있음에 틀림이 없었다. 이러한 BigO가 지수함수가 되는 경우를 나는 자주 생각했었고, 그러한 문제를 풀지 못한적이 많았기 때문에 이 부분에 대해서는 시간이 얼마가 걸리든지 고민할 필요가 있다고 느꼇다. 앉은 자리에서 무조건 끝내야 겠다는 생각보다는 천천히 다른것들을 하면서 생각해보았다.

시간이 조금 지나고 , 오늘 다시 보니까, 어처구니 없는 실수를 저질렀다는 것을 느꼇다.

문제의 요구 사항을 전혀 이해하지 못했던 것이다. 문제의 요구사항은 최대 합 을 구하는 것이다. 어떤 블록인지는 중요하지 않다.

즉, 문제의 요구사항은 \((a_1 , a_2 , a_3, a_4, a_5, ..a_n )\) 의 개수를 구하는 것이 아니다. \(max(a_1 + a_2 + a_3+ a_4+ a_5 .. +a_n )\) 를 구하는 것이다.

단순히 exahustive search를 해야겠네 , search tree 처럼 엄청난 가지 수로 뻗어나가겟네 , factorial을 사용해야 겠네 라고 생각했던 것이다. 이 문제를 분해(decomposition) 해서 생각했더라면 , exhaustive search를 단순히 tree search로 통으로 이해하지 않고 case별로 나누어서 생각을 하였더라면, 고민을 하지 않았을 것이다. 라는 생각을 한다.

컴퓨터 과학쪽은 case에 따라 optimal 한 solution이 달라지는 재밌는 과목이라는걸 다시금 깨닫는다.

연립방정식 , 행렬

제목은 거창한데 별 대단한 내용은 아니다. 내가 이 문제를 풀다가 꽤 긴 시간 삽질 한 부분이 있어서 , 기록을 남기고자 한다.

코딩테스트 문제들을 풀다 보면 여러 개의 값을 input으로 받고 변환된 값을 반환 함수를 작성해야 하는 상황이 생긴다. 항상 똑같이 동작하는 함수들은 연립방정식을 세워서 풀 수 있는 경우가 있다. 이런 경우 , linear algebra를 배웠다면 각 column이 basis vector임을 인지한다면 쉽게 구할 수 있다. 보통, 코딩테스트를 풀 때는 내장 라이브러리를 제외한 라이브러리를 쓸 수 없다. 나는 여기서 , 머릿속에서 이것이 회전변환임을 알고 이 회전변환 행렬을유도할줄 안다. 하지만, 알고리즘 테스트니까 for문을 이용해서 예쁘게 할 수 있지 않을까 에 집착을 했다.

이런 경우 , 그냥 연립방정식을 풀어서 나온 그 결과 값을 계산해서 리턴해주면 빠르게 할 수 있다. 예를들어, 회전변환의 경우 그냥 행렬을 곱한 값을 계산해서 리턴해주면 쉽다.