프로그래밍 문제 연습 - 2

프로그래밍 문제 연습 - 2

2015 10

http://m.mt.co.kr/renew/view.html?no=2015103009483323499

코딩 시험은 두 문제로 이루어져 있고 총 120분의 시간이 주어질꺼야.

그런데 예상보다 문제가 어려웠습니다. 첫 번째 문제는 matrix transformation, 즉 행렬을 변환하는 문제였습니다.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

이렇게 생긴 행렬을 시계방향으로 한칸씩, 모든 겹마다 다 회전시키는 문제였습니다. 위에 있는 행렬을 회전시키면 다음과 같습니다.

5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12


보통 이런 행렬 변환 문제가 나오면 가장 좋은 방법은 선형대수에서 나오는 간단한 공식들을 적용시키는 것이지만
제가 알고있는 모든 행렬 변환 공식 중 저런 식으로 변환시키는 공식은 없었습니다.

그래서 그냥 일일이 겹겹마다 for 루프를 돌리면서 O(N^2)의 알고리즘을 썼습니다.

=> 이 사람이 어떻게 풀었는지 모르겠지만 input 값이 이미 4*4 = 16의 1차원 배열화 시키면 연산이 16번 일어나니 O(N)이다. 

그런데 입력을 4로본다면 On2일수 있으니 확인 필요 

언어 제약이 없을 경우 파이썬이나 루비같은 scripting(스크립팅) 언어를 쓰는게 편할 것 같습니다.
특히 C++보다는 파이썬에서 지원하는 문자열 함수들이 훨씬 편하다고 생각합니다.
저도 다시 테스트를 본다면 둘 중 하나로 볼 것 같습니다.

첫번째 문제에 시간을 너무 빼앗긴 나머지 두번째 문제를 풀 시간이 거의 없었습니다.

두번째 문제는 다음과 같습니다.

N개의 박스가 주어지고, 그 박스들은 높이, 너비, 길이가 다 다릅니다.
어떤 박스 A를 다른 박스 B에 집어넣으려면 B의 높이, 길이, 너비가 각각 A의 높이, 길이, 너비보다 길어야 합니다.
그리고 박스는 돌려서 넣을 수 없습니다. 최대한 많은 박스를 한꺼번에 가져가고 싶은데 그 갯수는 몇 개일까요?

모든 박스끼리 서로 비교하는 식으로 모든 경우의 수를 구하는 가장 단순한 알고리즘으로 풀면 경우의 수가 엄청나게 늘어납니다. Polynomial Runtime(다항식 실시기간)안에 풀수 없죠.

그래서 저는 dynamic programming(동적 계획법)을 써서 O(N^2)로 풀었습니다.

푼 다음에 시계를 보니 2분 정도밖에 남지 않아서 돌려보니 한방에 테스트를 패스했습니다.

2015년 6월 경

첫번째는 이진트리 관련문제
두번째는 성적 평균인가? 상위점수 구하는 문제였던듯 (교수가 학생들 성적구하는)

2014년 11월 중순 코딩 시험 예시이다

문제는 주차장 시스템을 구현하라는 것이었다. 주차장에 n개의 주차 공간이 있고, 입구로부터의 거리가 주어져 있다. 주차장에 차가 들어오면 입구에서 가장 가까운 빈 공간을 알려 주면 된다. 차량이 주차장을 빠져나가면 해당 차량이 주차했던 자리는 빈 공간으로 할당된다. 주요 클래스(Car, Space)의 멤버 변수 및 인터페이스는 예시로 제공되어 있다. 핵심은 어떤 자료구조 및 알고리즘으로 주차 공간을 할당/반납하는가이다.

CareerCup 중

완료 및 괜찮은것 모음

https://www.careercup.com/question?id=5679778427305984

https://www.careercup.com/question?id=5120301346062336

https://www.careercup.com/question?id=5106425965576192

https://www.careercup.com/question?id=5761473844346880