코딩테스트구현 문제 접근 정리

일반 코테 수준에서는 제한된 메모리 사용량 보다 더 적은 크기의 메모리를 사용해야한다!

 

구현 문제의 유형, 고려해야할 점들을 정리하고 가야겠다라는 생각이 들었다.

 

일단 구현문제는 풀이를 생각하는 것이 쉽지만 소스 코드로 구현하는 것이 어려운 문제라고 한다.

 

구현 문제를 풀기 위한 선행 조건
1.  프로그래밍 문법 정확한 숙지
2. 라이브러리 많은 사용 경험

 

유형
완전탐색 : 모든경우의 수를 다 계산하는 문제
시뮬레이션 : 제시한 알고리즘을 차례대로 수행하는 문제 (삼성공채빈출유형)

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제
• 2차원 배열에서의 이동, 회전 등 까다로운 문제

 

예시
: 탐색할 전체 데이터 갯수가 100만개 이하 일때  -> 완전 탐색 이용

구현 문제에 접근하는 방법

· 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시하여 문제의 길이가 꽤 긴 편이다.

   - 하지만, 고차원적 사료적을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하면 오히려 쉽게 풀 수 있다.

 

·  C/C++/Java에서 구현 유형 문제가 더 어렵게 다가온다.

   - 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데 C/C++/JAVA에서는

     문자열 처리가 파이썬에 비하여 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용하기 때문이다.

   - 자신만의 코드 노트를 잘 활용하여 이를 보완할 수 있다.

 

 

구현 시 고려해야할 메모리 제약 사항

정수형Integer표현 시 int 자료형

   :  크기가 4바이트 int 자료형의 표현 범위: -2,147,483,648 ~ 2,147,438,647

 

정수형보다 더 큰 수를 처리할 경우 long long자료형 사용

 : · 크기가 8바이트 long long형의 표현 범위 :

                                               9,224,372,036,854,775,808 ~ 9,224,372,036,854,775,807(약 92경)까지 표현 가능

 

그보다 더 큰 수를 처리할때는 자료형 범위 제한 없는  BigInteger클래스(표준 라이브러리)를 구현하거나 이용한다. 

​

코딩테스트에서는 검색과 외부 라이브러리를 사용이 가능한 환경일 때만 사용하고, 

대체로 long long 에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 출제되지 않는다. 

 

파이썬의 경우는  표현범위에 대해 굳이 알 필요없음(따로 선언x,매우 큰수를 지원하기때문)