코딩 테스트 이론 및 문제

서론

코딩 테스트는 보통 파이썬을 활용하는 경우가 많다.
자바스크립트나 파이썬을 사용하는 것이 좋아보이고 다른 언어를 사용하는 경우도 보았지만
보일러플레이트가 심해서 코딩 테스트로 활용하기에는 적합해보이지 않는다.
또한 절차 지향 패러다임으로 구성되는 것이 기본 단계이기로 적합해보인다.

복잡도

시간 복잡도

• 알고리즘을 위해 필요한 연산의 횟수
• O(N)으로 표기한다.
• 상수 시간, 로그시간, 선형시간, 이차 시간 등이 있다.

공간 복잡도

• 알고리즘을 위해 필요한 메모리의 양
• 메모리 사용량(MB)

유형 분석

• 이진 탐색
• 정렬
• 그리디
• 구현
• DFS/BFS
• 최단 경로
• 다이나믹 프로그래밍
• 기타 그래프 이론

오늘의 문제

카펫

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

나의 풀이

// 브라운은 테두리니까 갯수는 대각선의 4개를 제외하면 노란색의 가로 x 2 와 새로 x 2 로 구성된다.
// 4 + 2 + 4 = 10 
// 2 + 2 + 4 = 8
// 24가 6 x 4 일 때, 12 + 8 + 4 = 24
// 24로 만들 수 있는 경우는 1*24, 2*12, 4*6 6*4 8*3
function solution(brown, yellow) {
    let [cal, row] = [0, 0]
    while(1) {
        if(yellow % cal == 0) {
            row = yellow / cal
            if(brown == row * 2 + cal * 2 + 4)
                return [row + 2, cal + 2]
        }
        cal += 1
    }
}

• 노란색의 타일의 가로와 세로의 각각의 두배의 크기 + 대각선 4개의 블록이 브라운 타일임을 통해서 찾은 해법이다.
• 가장 인기 있던 풀이의 경우 근의 공식과 수학적인 개념을 이해해서 위의 문제를 풀어냈다.
• 수학과 과학에 관련된 지식도 공부가 필요할 것으로 보인다.