작성 : 2020.08.10.
-
Advanced
-
Expert
시험 시간 및 문제 수 : 4시간 1문제
Professional 단계부터는 라이브러리를 사용할 수 없다.
C/Cpp 경우, 동적할당 라이브러리인
malloc.h까지만 허용
또한 전체적인 로직은 구현이 되어있는 상태이며, 사용자가 필수적으로 구현해야 할 메소드 부분이 빈칸으로 제공된다. (main.cpp와 user.cpp가 주어지며, 우리는 user.cpp를 구현하면 된다)
크게 두 가지 유형으로 출제되고 있다.
- 실행 시간을 최대한 감소시켜 문제를 해결하라
- 쿼리 함수를 최소한 실행시켜 문제를 해결하라
결국, 최대한 효율적인 코드를 작성하여 시간, 메모리를 절약하는 것이 Professinal 등급의 핵심이다.
Professional 등급 문제를 해결하기 위해 필수적으로 알아야 할 것(직접 구현할 수 있어야하는) 들
- 큐, 스택
- 정렬
- 힙
- 해싱
- 연결리스트
- 트리
- 메모이제이션
- 비트마스킹
- 이분탐색
- 분할정복
추가 : 트라이, LCA, BST, 세그먼트 트리 등
60분 - 설계
120분 - 구현
60분 - 디버깅 및 최적화
-
시험 문제는 상세한 예제를 통해 충분히 이해할 수 있도록 제공된다. 따라서 우선 읽으면서 전체적으로 어떤 문제인지 전체적인 틀을 파악하자
-
문제에 사용자가 구현해야 할 함수가 제공된다. 특히 필요한 파라미터와 리턴 타입을 알려주므로, 어떤 방식으로 인풋과 아웃풋이 이뤄질 지 함수를 통해 파악하자
-
문제의 전체적인 곳에서, 범위 값이 작성되어 있을 것이다. 또한 문제의 마지막에는 제약 조건이 있다. 이 조건들은 문제를 풀 때 핵심이 되는 부분이다. 반드시 체크를 해두고, 설계 시 하나라도 빼먹지 않도록 주의하자
-
문제 이해와 구현 함수 파악이 끝났다면, 어떤 방식으로 해결할 것인지 작성해보자.
전체적인 프로세스를 전개하고, 이때 필요한 자료구조, 구조체 등 설계의 큰 틀부터 그려나간다.
최대값으로 문제에 주어졌을 때 필요한 사이즈가 얼마인 지, 어떤 타입의 변수들을 갖추고 있어야 하는 지부터 해시나 연결리스트를 사용할 자료구조에 대해 미리 파악 후 작성해두도록 한다.
-
각 프로세스 별로, 필요한 로직에 대해 간단히 수도 코드를 작성해두자. 특히 제약 조건이나 놓치기 쉬운 것들은 미리 체크해두고, 작성해두면 구현으로 옮길 때 실수를 줄일 수 있다.
높은 확률로 main.cpp에서 답을 찾을 수 있다. 문제 이해가 잘 되지 않을 때는, main.cpp와 user.cpp 사이에 어떻게 연결되는 지 main.cpp 코드를 뜯어보고 이해해보자.
-
내가 해결할 방향에 대해 먼저 코드 안에 주석으로 핵심만 담아둔다. 이 주석을 보고 필요한 부분을 구현해나가면 설계를 완벽히 옮기는 데 큰 도움이 된다.
-
소스 코드 내 전체적으로 활용될 구조체 및 전역 변수들에 대한 부분부터 구현을 시작한다. 이때
#define와 같은 전처리기를 적극 활용하여 선언에 필요한 값들을 미리 지정해두자
-
문자열 복사, 비교 등 모두 직접 구현해야 하므로, 혹시 실수를 대비하여 함수를 만들었을 때 제대로 동작하는 지 체크하자. 이때 실수한 걸 넘어가면, 디버깅 때 찾기 위해서 엄청난 고생을 할 수도 있다.
-
결국 디버깅에서 문제가 되는 건 제약 조건을 제대로 지키지 않았을 경우가 다반사다. 코드 내에서 제약 조건을 모두 체크하여 잘 구현했는 지 확인해보자
-
input 데이터가 text 파일로 주어진다. 물론 방대한 데이터의 양이라 디버깅을 하려면 매우 까다롭다. 보통 1~2번 테스트케이스는 작은 데이터 값이므로, 이 값들을 활용해 문제점을 찾아낼 수도 있다.
-
문제가 발생했을 때, main.cpp를 활용하여 디버깅을 할 수도 있다. 문제가 될만한 부분에 출력값을 찍어보면서 도움이 될만한 부분을 찾아보자. 문제에 따라 다르겠지만, 생각보다 main.cpp 안의 코드에서 중요한 정보들을 깨달을 수도 있다.
-
어쩌면 가장 중요한 함수이기도 하다. 이 초기화 함수를 얼마나 효율적으로 구현하느냐에 따라 합격 유무가 달라진다. 최대한 매 테스트케이스마다 초기화하는 변수들이나 공간을 줄여야 실행 시간을 줄일 수 있다. 따라서 인덱스를 잘 관리하여 init 함수를 잘 짜보는 연습을 해보자
-
이 밖에도 실행 시간을 줄이기 위한 고민을 끝까지 해야하는 것이 중요하다. 문제를 accept 했다고 해서 합격을 하는 시험이 아니다. 다른 지원자들보다 효율적이고 빠른 시간으로 문제를 풀어야 pass할 수 있다. 내가 작성한 자료구조보다 더 빠른 해결 방법이 생각났다면, 수정 과정을 거쳐보기도 하고, 많이 활용되는 변수에는 register를 적용하는 등 최대한 실행 시간을 감소시킬 수 있는 방안을 생각하여 적용하는 시도를 해야한다.
-
임직원들만 이용할 수 있는 사내 SWEA 사이트에서 기출과 유사한 유형의 문제들을 제공해준다. 특히 시험 환경과 똑같이 이뤄지기 때문에 연습해보기 좋다. 많은 문제들을 풀어보면서 유형에 익숙해지는 것이 가장 중요할 것 같다.
-
이게 개인적으로 핵심인 것 같다. 1번에서 말한 사이트에서 기출 유형 문제들을 해결한 사람들의 코드를 볼 수 있도록 제공되어 있다. 특히 해결된 코드의 실행 시간이나 사용 메모리도 볼 수 있다는 점이 좋다. 따라서 문제 해결에 어려움이 있거나, 더 나은 코드를 배우기 위해 적극적으로 활용해야 한다.
올해 안에 꼭 합격하자! (2021.05 합격)