코딩테스트를 위한 좋은 습관
-
문제를 순서대로, 올바르게 이해해야한다
읽기
- 시간, 메모리 제한 체크
- 문제 전체를 꼼꼼히 파악한다
이해하기
- 제공되는 정보(변수) 정리 -> 내가 이 문제를 풀기 위해 필요한 정보는 무엇인가?
- 예제데이터를 통해 내가 옳게 이해했는지 테스트하기
파악하기
- 최대, 최소 정답에 맞는 데이터(타입)를 직접 생각해보기
- 키워드가 되는 단어들을 체크해보기
-
시간과 공간 복잡도를 계산한다
- 어떤 알고리즘에 시간복잡도와 공간복잡도가 어떠할지 미리 알아야한다 -> 만약 제한을 초과한다면 짤 가치가 없다
-
코드를 효율적으로 함수화해서 구현하기
-
부분점수를 챙긴다
완전탐색
- 완전탐색이란?
- 모든 코테 문제에서 기본적으로 시도해봐야하므로 많은 연습이 필요하다- 장점: 부분점수 얻기 좋다
- 단점: 시간복잡도가 높다
- 완전탐색종류
- N개 중 (1. 중복을 허용하거나 2. 중복 없이)
M 개를 (3. 순서있게 나열 4. 고르기)
- 완전탐색은 함수 정의가 반은 먹고 들어간다
- N개 중 (1. 중복을 허용해서) M 개를 (3. 순서있게 나열하기)
Boj15651
문제읽기
- 시간제한: 1초
- 메모리제한: 512MB
- 같은 수를 여러 번 골라도 된다 -> 중복허용
- (1 <= M <= N <= 7) -> 상한가는 7
- 수열은 사전 순으로 증가하는 순서로 출력한다
- 입력과 출력을 보며 내가 이해한 것과 일치하는지 확인
시간, 공간 복잡도 계산하기
- 시간복잡도: 상한선의 개수로 총 계산해야하는 경우의 수를 계산 -> M과 N이 7일 때, 7^7이 최대의 계산 수
- 공간복잡도: 최대한 표현하는 데이터의 갯수 -> 7개
구현 (함수)스케치
- 사용해야하는 변수의 개수와 타입은?
- 이전의 계산 이력을 저장하기 위한 변수필요
backend