expert 제목 및 팁

개인적인 사정으로

2015년 8월에 지금과 같이 Ex, Pro, Ad 시험이 나뉜후로 계속 봤었는데,

처음으로 시험을 못보게 되었네요. 아쉽습니다 ㅠ

돌이켜보면

어셈 커맨드 문제, 암수퍼즐나사 맞추기 문제, 블럭에 그림그리고 반전시키던 문제

강아지 분양 문제, 다이아불순물제거 문제, sort 문제, edge 퍼즐문제, 노이즈제거 문제, 대피소 문제

중고차판매문제, 큐브퍼즐문제, 곱셈문제...

이번에 어떤 문제일까요?

개인적으로는 작년 10월 노이즈제거문제가 제일 기발했던 기억이 나네요. 피출리아님의 솔루션도 참 멋졌구요..

(저는 못풀었지만 ㅋㅋ)

이번 문제가 궁금한데 아직 안올라와서 먼저 중얼거려봅니다.

이번엔 Ex 시험은 못봤지만 궁금하네요.

• • 디모
  • 2017-08-21
  • 조회 : 2827

Rubato 2017-06-01 14:11:53 좋아요 9 댓글 수정 삭제 expert 시험은 pro 시험 유형이 바뀌기 전부터 main.cpp 와 solution.cpp 로 파일을 구분하고 main.cpp 를 수정할 수 없도록 출제가 되어왔습니다. 그래서 제출 방식에 대한 부분은 최근 pro 시험을 보신 분이라면 쉽게 적응하실 수 있을 것 같습니다. * pro 시험과 다른점 1. input 파일이 별도로 제공되지 않고, main.cpp 에서 랜덤으로 생성 - 코너케이스의 발생확률이 낮고, main.cpp에서 랜덤값을 다루는 코드를 분석하면 실제 input이 어떠한 경향으로 생성되는 지 파악하고 공략할 수 있습니다. 2. user API의 호출에 걸린 시간을 측정하여 performance 점수로 반영 - 정확한 구현이 우선이지만, 그 이후에도 사소한 부분까지 최적화 하는 것이 중요한 문제가 많았습니다. * exp 시험의 유형들 1. 모든 TC에서 정답을 내야하고, 정답을 내는 데 걸리는 시간에 따라 당락이 결정되는 문제 2. 정답이 존재하지 않고, 최대한 높은 점수를 받아야 하는 문제(동점이더라도 performance 점수에 따라 점수가 달라짐) 3. 정해진 시간 안에 최대한 많은 TC를 해결해야 하는 문제 제가 풀어본 문제들 유형은 요정도네요. expert 시험은 pro 시험 유형이 바뀌기 전부터 main.cpp 와 solution.cpp 로 파일을 구분하고 main.cpp 를 수정할 수 없도록 출제가 되어왔습니다. 그래서 제출 방식에 대한 부분은 최근 pro 시험을 보신 분이라면 쉽게 적응하실 수 있을 것 같습니다. * pro 시험과 다른점 1. input 파일이 별도로 제공되지 않고, main.cpp 에서 랜덤으로 생성 - 코너케이스의 발생확률이 낮고, main.cpp에서 랜덤값을 다루는 코드를 분석하면 실제 input이 어떠한 경향으로 생성되는 지 파악하고 공략할 수 있습니다. 2. user API의 호출에 걸린 시간을 측정하여 performance 점수로 반영 - 정확한 구현이 우선이지만, 그 이후에도 사소한 부분까지 최적화 하는 것이 중요한 문제가 많았습니다. * exp 시험의 유형들 1. 모든 TC에서 정답을 내야하고, 정답을 내는 데 걸리는 시간에 따라 당락이 결정되는 문제 2. 정답이 존재하지 않고, 최대한 높은 점수를 받아야 하는 문제(동점이더라도 performance 점수에 따라 점수가 달라짐) 3. 정해진 시간 안에 최대한 많은 TC를 해결해야 하는 문제 제가 풀어본 문제들 유형은 요정도네요.

루빅스 큐브 https://swexpertacademy.samsung.com/common/swea/solvingPractice/discussionBoardView.do?commuId=AVuc8sSf5xEAAAE1&searchClsftn=&searchCondition=COMMU_DETAIL-COMMU_TITLE&searchKeyword=&startDate=&endDate=&pageIndex=23&sortingType= 1. bfs를 양쪽에서 돌립니다. -> 한쪽은 넘겨받은 섞인 큐브, 다른쪽은 모든면이 맞춰져 있는 큐브 -> 문제에서는 10번 섞기 때문에 양쪽으로 5번씩 내로 무조건 답이 나오게 되어있습니다. -> 12^10 은 약 400억이상 이지만, 12^5 은 24만개입니다. 양쪽으로 24만개씩 bfs data를 만든후에 서로 일치하는것을 찾으면 됩니다. -> 관련해서 구종만 알고리즘 문제해결전략 책에, bfs를 양쪽으로 돌리는 문제가 있으니 찾아서 연습해보시기를 추천드립니다. 2. 그렇다고 해도 24만개에서 일치하는것을 찾으려면 24만^2 입니다. 정렬을 한후에 순차적으로 비교하면 M과 N 길이의 배열에서 일치하는것을 찾는것은 MLgM + NLgN + (M + N)의 시간복잡도로 가능합니다. 관련 문제로 KOI의 사냥꾼 문제 한번 풀어보시면 이해가 빠르실겁니다. 이 2가지만 캐취하시면 시간은 엄청나게 줄어듭니다. data는 cube의 raw data를 쓰던, bitmask로 6 int로 압축을 하던, 더 쿨하게 hash를 멋있게 짜서 64bit int 한개로 압축을 하는것은 개인의 선택입니다만, 저는 hash는 조금 생각하다 포기했고, 6개의 int로 썼습니다. 수행시간은 2초 안되게 나오더라구요. 문제자체가 시간은 10초에 1점이고 이동횟수는 1회에 1점이기때문에, timeout만 안나면 무조건 짧게 치는것이 유리합니다. 고로 bfs가 이 문제에서는 최고의 솔루션입니다. bfs를 돌리면 예외처리할게 없이 양쪽으로 한번씩 bfs 돌리면서 일치하는것이 있는지 찾으면 됩니다. 4회까지는 2만개밖에 안되기때문에, 정렬비교 시간이 얼마 안듭니다. 확률적으로 10번 섞는 과정에서 최소 9/12 의 확률로 같은 면의 clockwise만 반대로 해서 섞는 경우가 발생합니다. 고로 왠만한건 8번이고.. 혹시 모르지만 출제자분께서 4번만에 답이나오는 rand seed를 찾는다해도 bfs는 그런것들을 고려할 필요가 없죠...

4/22 ex 후기 BingBong 2017-04-24 조회 : 3140 좋아요 4 수정 삭제 목록 루빅스 큐브를 잘 맞춰진 초기 상태 (A) 에서 10번 랜덤으로 돌려서, 섞인 상태 (B)를 주어주고, 원래대로 돌리는 함수를 작성하는 문제인데, 풀지는 못했는데,  시험이 끝나고, 생각해본 방법은, 1) 초기 (A) 부터 6번을 돌렸을 때의 모든 조합의 상태를 만들어 보고, 패턴을 Hashing 하여 6번 돌리는 모든 경우의 History DB 를 만들고, (경우의 수 = 12^6 = 2,985,984) 2) 최종 섞인 상태 (B) 부터 4번을 돌리는 모든 조합으로 돌려서 위 History DB 의 상태와 맞는 것을 찾음. (경우의 수 12^4 = 20,736) --- 여기까지하면 원래의 10번을 복기 가능하여 200.xxx 대 가능 3) 이후 헛바퀴 도는 것을 제외 해주면 200 점 이하로 가능함.    예를 들어 같은 면을 시계방향으로 돌렸다가 다시 반시계방향으로 돌리는 경우가 매번 1/12 확률로 발생하므로,    10회 돌릴때     2바퀴가 헛바퀴 도는 것은 9/12 (=0.75) 확률로 발생 가능하므로, 이것을 빼주면, 2바퀴 x 0.75 = 1.5회,  10회-1.5회 = 8.5회, 8.5회 x 20TCs = 170점     4바퀴가 헛바퀴 도는 확률까지 빼주면,166 점대 가 나올수 있을 것 같습니다.

2/18 ex 시험 후기 곰도리파파 2017-02-18 조회 : 3299 좋아요 2 수정 삭제 목록 다들 이번 문제 어떠셨나요...? 이번 문제의 관건은 Sell 시간을 얼마나 줄이느냐 였던거 같네요. 전 시간초과로 제출도 못했는데, 어떻게 좀 더 해볼까 하다가 아예 방향을 잘못 잡은거 같아서 나왔습니다. 나와서 생각해보니 전체 리스트가 아니라 안팔린 리스트만 관리해서 했으면 좀 빨라졌으려나 하네요. 제가 12시쯤 나올때는 2600대 분들이 계셨는데.. 어떻게 풀었는지 힌트좀 부탁드립니다.