1. Java 코딩 테스트 유형

코딩 테스트 유형

1. 정렬 : 버블 정렬 .퀵 정렬
2. 탐색 : 완전 탐색 /이진 탐색
3. 부분 문제의 합 : 분할 정복 /다이나믹 프로그래밍
4. 최적 선택 : 그리디
5. 기타 시뮬레이션 

정렬

• 예시 ) 1,5,3,2,4를 오름차순 또는 내림차순으로 정렬
• 정렬 문제 단독으로 나오는 경우 거의 없음
• 풀이를 위한 사전과정 
• 알고리즘 : 버블정렬, 선택 정렬, 퀵 정렬, 합병 정렬, // 우선순위 큐(들어온 순서대로 내보내는 것)...

탐색

• 예시) 주어진 데이터에서 특정 값 찾기
• 2차원/3차원 데이터에서 인접한 경로 / 가능한 경로 찾기
• 탐색에 사용할 수 있는 자료구조/ 알고리즘에 대한 이해 필요
• 단순 풀이로 접근 시 대부분 시간초과로 실패
• 알고리즘 : 완전탐색, 이진 탐색, 투 포인터 ,BFS, DFS...

부분 문제의 합

• 예시) 최대 값 찾기/ 부분 수열의 최대 길이/ 0-1 Knapsack
• 단순 반복, 조건문의 나열로는 풀기 복잡한 문제
• 재귀 함수를 통한 작은 문제의 반복적 해결 구조 또는 계산 결과의 재사용
• 알고리즘 : 분할 정복, 다이나믹 프로그래밍

 

최적 선택

• 예시) Activity Selection /거스름돈
• 특정 조건 만족 시 빠르게 문제를 해결할 수 있는 방법
• 최적해가 아닌 근사치를 얻을 수도 있으므로 사용 시 주의 필요
• 알고리즘 : 그리디 

시뮬레이션 

• 예시) 조건에 따른 문자열 입력/삭제/수정 문제
• 문제의 요구사항을 잘 읽고 해결하는 문제
• 특정 알고리즘 분류로 매핑 되지 않은 경우 많음