[Etc] 코딩 테스트 팁
📝 코딩 테스트
코딩 테스트란?
말 그대로 특정 상황에 대한 문제를 내고, 이를 정해진 프로그래밍 언어로 구현하는 테스트이다. 요즘의 IT 회사에서는 거의 필수적인 입사 절차로 활용되고 있으며, 나의 가장 큰 약점이기도 하다. 따라서 이번 기회로 코딩 테스트에 대한 각종 팁을 정리해보고자 한다.
💡 팁
코딩 테스트를 위한 공부를 할 떄 도움이 되는 각종 팁들이 존재한다. 여기부터 그 팁들을 나열해보겠다.
📌 문제 선택
백준, 프로그래머스, LeetCode 등 코딩 테스트를 위한 각종 문제들이 존재하는 사이트들이 있다. 하지만 그 수많은 문제들 중에 어떤 문제를 풀어야할지 감이 잡히지 않을 때가 많다. 이럴 때 도움이 되는 방법들이 몇가지 존재한다.
1. 백준
- 단계별 풀이
백준에서는 단계별로 문제들을 정리해 놓은 페이지가 있다.
여기서 단계별로 문제들을 푸는 방식이다. 특히 초반에 코딩 테스트에 대한 감을 잡을 때 좋다.
- 강의
백준에서는 코딩 테스트에 대한 강의를 제공한다.
하지만 강의는 유로라서 돈을 내야 한다. 내가 추천하는 방법은 강의를 듣는게 아니라 각 강의 페이지로 들어가서 나와 있는 알고리즘 별 문제들을 푸는 것이다. 초급부터 고급까지 알고리즘별로 추천 문제들이 있어서 알고리즘 공부에 아주 좋다.
2. 프로그래머스
- 알고리즘 고득점 Kit
프로그래머스에서는 알고리즘 고득점 Kit이란 페이지가 따로 존재한다.
여기서 프로그래머스 사이트에서 직접 분석해서 자주 나오는 알고리즘 유형, 사람들이 많이 틀리는 유형들을 분류해 놓았다. 문제수가 그리 많지 않으니 다 풀어보면 좋을 것 같다.
- AI 추천 문제
프로그래머스에서는 직접 내가 푼 문제들의 유형과 성공 여부를 토대로 AI가 직접 문제를 추천해주는 시스템이 있다.
도저히 뭘 풀어야할지 모를 때 이용하면 소소하게 도움이 된다.
3. 코드 업
코드 업에서는 문제집을 제공한다.
여기에서는 기초 입출력부터 Union-Find 같은 고급 알고리즘까지 각 알고리즘별 추천 문제들이 모여 있다.
4. solved.ac
- Class 단계별 풀이
solved.ac에서는 Class 단계별 풀이 페이지가 있다.
여기서 Class 내의 문제를 모두 풀고 다음 Class로 넘어가는 방식으로 단계별 풀이를 할 수 있다.
- 태그 활용
solved.ac의 내 프로필에 들어가보면 각 문제별 태그에 대한 나의 레이팅을 볼 수 있다.
여기서 낮은 레이팅 순서로 태그를 찾아서 우선적으로 풀면 나의 약한 알고리즘에 대한 보충을 하기에 좋다. 태그 페이지는 밑의 링크로 가면 된다.
5. 랜덤 문제
이 외에도 정말 어떤 문제를 풀어야 좋을지 모르겠다면 랜덤 문제를 뽑는 방식도 존재한다. 상기한 프로그래머스의 AI 추천 문제 뿐만이 아니라, solved.ac의 검색을 활용하는 방법도 있다.
solved.ac의 상단 메뉴 중 돋보기 메뉴를 누르면 위의 창이 뜨는데, 여기에 정해진 문법대로 검색을 하면 된다. 검색법은 다음과 같다.
이 외에도 프로그래머스에서 원하는 난이도를 선택하고 아무 문제나 골라 풀거나, 백준의 고급 검색을 활용하는 방법도 있다.
❓ 티어, 알고리즘 숨기기
백준이나 solved.ac를 사용한다면 알고리즘 분류나 티어에 대해 OnOff 기능을 설정에서 제공한다.
알고리즘이나 티어를 끄거나 어려운 문제만 경고하도록 설정하는 것을 추천한다. 실제 코딩 테스트에서는 알고리즘이나 난이도를 알려주지 않는다.
⏳ 시간 분배
실제 코딩 테스트에서는 시간 제한이 주어지는데, 대부분 한 문제당 30분 ~ 1시간 정도의 시간이 주어지게 된다. 따라서 실전에 대비해서 개인 코딩 테스트 공부를 할 때도, 시간 제한을 놓고 적절한 시간 분배를 하는 것이 좋다.
1. ~ 20분
감이 잡히는 경우 :
- 어떤
알고리즘을 써서 어떻게 풀어야 하는지 감이 잡힌다면 그대로 풀어 본다.
그렇지 않은 경우 :
- 알고리즘 분류를 확인한다.
- 아는 알고리즘이었던 경우, 같은 알고리즘의 다른 문제들을 풀며 연습.
- 모르는 알고리즘인 경우, 구글링 등을 통해 해당 알고리즘을 공부.
2. ~ 40분
풀었으나 틀린 경우 :
- 문제를 다시 읽어보거나, 미처 고려하지 못한
예외 케이스가 있는지 확인. - 시간 혹은 메모리 초과인 경우는 사용 중인
STL이나자료구조를 바꿔보거나코드 최적화시도.
풀었는데 비효율적인 경우 :
- 더 효율적인
STL이나자료구조가 있을지 고민. - 내 코드의 알고리즘의
시간복잡도를 생각해보자. - 더 이상 최적화가 떠오르지 않을 경우 다른 사람의 풀이를 참고.
3. ~60분
틀렸거나 여전히 비효율적인 풀이인 경우 :
- 다른 사람의 풀이를 보거나 AI를 활용해보자.
- 그리고 일주일 정도 후에 다시 스스로 문제를 풀어보자.
4. 이후
다른 사람의 풀이나 AI를 활용한 풀이를 참고해서 더 효율적인 풀이나 다른 방식의 풀이가 있는지 확인하는 것이 좋다. 내가 생각치 못한 풀이가 가장 내 맘에 드는 풀이일 수도 있다.
🔍 조건 확인
주어지는 케이스의 수나 예외 조건 등을 확인하는 것은 당연하다. 추가적으로 생각해보면 좋을 것은 시간 복잡도와 공간 복잡도이다.
1. 시간 복잡도
컴퓨터는 간단한 동작을 1초에 약 1억 번 수행한다.
이 사실을 활용하면, 다음과 같은 사고가 가능하다.
- 시간 제한이 1초일 때, N = 5,000 이라면 O(N²) 라면 25,000,000 번이므로 1초 1억 번에 비해 널널하네!
- N = 100,000 이라면 O(NlogN) 이나 O(N√N) 으로 가능!
물론 입출력, 문자열 처리, map, 정렬 같은 연산 1번은 더 무겁기 때문에 어느 정도의 오차는 있지만, 대략 위 같은 방법으로 계산해도 무방하다.
2. 공간 복잡도
수많은 자료형들은 각각 차지하는 메모리 크기가 다르다.
예를 들어 int 자료형은 4바이트, char 자료형은 1바이트 등등…
이를 활용하면, 다음과 같이 생각할 수 있다.
- 메모리 제한이 256MB라면, int a[1000000]은 4,000,000B == 4MB이므로 통과!
- 메모리 제한이 10MB라면, int char[100000000]은 100,000,000B = 10MB이므로 다른 방법을 써볼까?
실제로는 함수 콜스택, 각종 STL, 라이브러리 등의 내부 버퍼도 사용하기 때문에 아슬아슬하다 싶은 경우는 다른 방법을 생각하는 것이 좋다.
🔖 기타 팁
1. 헤더 파일
코딩 테스트를 풀다 보면 어떤 STL, 기능, 함수 등을 사용하기 위해 특정 헤더 파일을 포함해야 하고, 가끔을 어떤 헤더 파일이 필요한지 헷갈릴 때가 종종 있다. 이럴 때 "bits/stdc++.h"라는 헤더파일만 있으면 대부분의 문제는 해결된다.
"bits/stdc++.h" 헤더 파일은 우리가 자주 쓸만한 헤더 파일들을 대부분 include 해놓은 파일이다. 구글링하면 금방 찾아서 다운로드 할 수 있는데, 이를 자신의 Visual Studio의 “include” 폴더 내에 넣으면 된다. 그리고 사용할 때는 이 헤더 파일만 include 해주면 끝!
#include "bits/stdcn++.h"
이지만, 나는 개인적으로 사용을 꺼리는 편이다. 일단 나에게 필요 없는 헤더 파일도 강제로 포함시켜야 되는 것도 있고, 남용하면 이 파일 없이는 어떤 헤더 파일이 필요한지 까먹게 되기 때문이다.
2. 입출력 최적화
코테에서 항상 유용하게 쓰일 수 있는 입출력 최적화 방법이 두 가지 존재한다. 이를 main 함수의 최상단에 포함해주면 굉장히 도움이 된다.
- ios::sync_with_stdio(false)
이 코드의 역할은 C++의 iostream(cin/cout)과 C의 stdio(scanf/prinf)의 동기화를 끊어주는 것이다.
기본적으로 C++의 cin/cout은 C의 scanf/prinf와 내부 버퍼를 동기화해서 사용한다. 그 이유는 C++의 초창기에는 C 라이브러리와 iostream을 같이 쓸 일이 많았기 때문에, 동일한 버퍼를 사용함으로써 줄 바꿈이나 순서가 꼬이는 것을 방지할 수 있기 때문이다.
하지만 이로 인해 매 입출력 연산마다 버퍼를 동기화해야 하기 때문에 입출력이 느려진다. 따라서 저 코드는 동기화를 끊어줌으로써 입출력의 속도를 향상시킨다.
이 코드를 포함시키면 cin/cout과 scanf/prinf를 섞어쓰는 것을 지양해야 한다. (버퍼 순서가 뒤죽박죽 될 수 있기 때문)
- cin.tie(nullptr)
이 코드의 역할은 cin과 cout의 자동 flush (출력 버퍼 지우기) 연결을 끊어주는 것이다.
기본적으로 cin은 입력받기 전에 cout을 자동으로 flush 한다. 왜냐하면 다음 같은 상황에서 사용자에게 출력이 먼저 보이게 하기 위해서이다.
cout << "입력하세요: "; // flush됨
cin >> x; // input
하지만 코딩 테스트에서는 사람이 직접 데이터를 입력하는게 아니라, 컴퓨터가 데이터를 제공하기 때문에 자동 flush는 불필요한 오버헤드가 된다. 따라서 이 코드를 포함시킴으로써 cin와 cout의 연결을 끊고, 입출력의 속도가 빨라진다.
3. 파일로 입력 받기
코테를 하다 보면 가장 귀찮은 것 중 하나가 바로 테스트 케이스이다. 이를 제공해 주는 것은 좋지만, 코드를 실행할 때마다 따로 복사 붙여넣기를 해줘야 한다는 것 때문에 귀찮을 때가 상당히 많다. 이를 해결하기 위해, 매번 복사 붙여넣기를 하는 것 대신에 파일 하나로 입력을 받게 해주는 방법이 있다.
일단 프로젝트 디렉토리에 "Input.txt" 파일을 하나 만들어 준다.
참고로 이 경로는 실제로 파일이 인식되는 곳에 만들어야 한다. 나 같은 경우는 실행 파일이 만들어지는 Debug 폴더 안쪽에 넣어줬다.
그리고 이 파일을 읽어주기 위해 다음과 같은 코드를 추가해준다.
freopen("Input.txt", "r", stdin);
이는 입출력을 내가 만들어준 "Input.txt" 파일로 해주라는 코드이다. 이렇게 하면 내가 직접 테스트 케이스를 입력하는 것이 아니라, 컴파일러가 알아서 파일을 읽어서 결과만을 출력해준다.
※ 주의 사항
참고로 저 코드는 답안을 제출하기 전에는 꼭 주석 처리를 하거나 지워줘야 한다. 개인적으로는 "CMakeLists.txt" 파일에 LOCAL 매크로를 추가하고 #ifdef 문 안에 코드를 넣어줌으로써 해결했다.
- 예시 :
#ifdef LOCAL
freopen("Input.txt", "r", stdin);
#endif
💭 그 외
이는 내가 지금까지 얻은 정보를 바탕으로 작성한 게시물이므로, 기타 다른 팁들이 많이 존재할 수도 있다. 코딩 테스트는 유용하게 활용할 수 있는 팁들이 많이 존재하니, 한 번 찾아보길 바란다!
Comments