📃 요약
코딩테스트는 IT 회사에 들어가기 위한 보편적인 평가방법이 되고 있습니다.
아직 포트폴리오 및 기술면접으로 치루는 회사도 있으나, 점차 코딩테스트로 서류전형 전/후에 코딩의 기본 기술이 있는지
확인하는 전형으로 많이 채택되고 있습니다.
코딩테스트 연습 사이트의 대표적으로는 백준, 프로그래머스, 코드업 등이 있습니다.
요소 기술은 아래와 같습니다.
요소 기술 :
– 프로젝트 키워드 : 코딩테스트
– 언어 : 자바 & 알고리즘
백준 기초 문제 :
코딩테스트를 위한 기초 문제 : 기본적으로 언어 사용법는 기초 문제 해결능력을 체크하고, 대체로 쉬운문제로 이루어져 있음
백준 등급 : 브론즈 < 실버 < 골드 < 플래티넘 < 다이아 < 루비
( 브론즈 : 제일 쉬움 ~ 루비 : 제일 어려움 )
- IT 회사는 대체로 골드 수준까지의 문제가 골고루 출제됨, 그 이상은 알고리즘 대회 수준이므로 준비할 필요 없음 ( 플래티넘, 다이아 , 루비 )
골드 이상 : 대기업 위주 코딩테스트 문제들, 아주 어려움 예) 카카오, 네이버 등
골드 미만 : 중소기업 , 스타트업 위주 코딩테스트 문제들
📃 기술 구현
스펙 :
- jdk 17 - 알고리즘
백준 기초 문제 : 100문제 (Simple 문제집)
- 주요 알고리즘 종류 : 코딩테스트에서는 주로 구현/시뮬레이션 문제가 자주 등장함
- 구현 : 익히 아는 알고리즘 또는 풀이를 코딩으로 변환하는 것
- 시뮬레이션 : 문제에 지시된 규칙을 토대로 코딩을 하는 것
- 누적합 : 이전 합계를 계속 새로운 값과 더해서 누적시켜 현재합계를 구하는 것
재귀 함수 소개
- 함수자신을 계속 호출하는 함수를 재귀 함수 또는 순환 함수라고 함
- 자기자신을 너무많이 호출하면 성능이 매우 나빠지거나 스택 오버플로우 에러가 발생할 수 있으므로
항상 그 이전에 답을 곧장 반환하는 조건문을 최소 1개 포함해야함(재귀함수 종료조건)
public class ReFunction{
//1부터 n까지의 합을 계산하는 재귀함수
public static int reSum(int n){
if(n==1) return 1; //답을 곧장 반환하는 조건문(이것을 만나면 보류된 재귀함수가 모두 계산되어 종료됨)
// (reSum(3-1) + 3)
// => (reSum(1) + 2) + 3 : reSum(1) 일때 n==1 이므로 값 1를 return
// => (1 + 2) + 3
return reSum(n-1)+n;
}
public static void main(String[] args){
int n=3;
System.out.println("1부터 3까지의 합(재귀함수) : "+ reSum(n));
}
}
//출력결과
1부터 3까지의 합(재귀함수) : 6
정렬 알고리즘 소개
구현 간단, 성능 낮음 : 시간복잡도 (n^2)
- 선택정렬
(1) 주어진 배열에서 최소값을 찾는다
(2) 그값을 맨앞의 값과 교환한다.
(3) 맨 처음 위치를 뺀 나머지 배열을 (1) ~ (2) 를 반복한다.
- 선택정렬
2) 삽입정렬
- 손안의 카드를 정렬하는 방법과 유사하다
- 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입하는 방법
(1) 2번째 숫자를 첫번째 숫자와 비교해서 작으면 그 숫자 앞에 끼워넣음
(2) 3번째 숫자를 이전 배열과 하나씩 비교해서 작으면 그 숫자 앞에 끼워넣음
(3) … 배열의 끝까지 (1) ~ (2) 를 반복한다.
3) 버블정렬
- 인접한 2개의 숫자를 비교하여 크기가 정렬되지 않으면 오름차순 정렬하면서 배열의 끝까지 이동시키는 알고리즘
(1) 배열의 인접한 숫자를 비교하여 작은수를 앞으로 교환한다.
(2) 위와 같은 방식을 모두 진행하면 가장 큰수가 제일 뒤로 가게된다.(최대값이 가장 맨뒤에 있음)
(3) (1) ~ (2) 과정을 배열이 오름차순으로 정렬될때까지 계속 반복한다.
- 인접한 2개의 숫자를 비교하여 크기가 정렬되지 않으면 오름차순 정렬하면서 배열의 끝까지 이동시키는 알고리즘
구현 복잡, 성능 높음 : NLogN, (몇번 재귀호출하는가? LogN), (몇번 비교/교환하는가? N)
1) 합병정렬
- 1개의 리스트를 2개의 균등한 크기로 분할하고 분할된 리스트를 정렬한다음, 2개의 정렬된 부분을 합쳐서 전체가 정렬되게 하는 방법
- 주로 배열보다 링크드 리스트를 사용한다.(휠신빠름)
(1) 입력 리스트를 같은 크기의 2개의 부분 배열로 분할한다.
(2) 부분 리스트을를 정렬한다. 부분 리스트의 크기가 충분히 작지 않으면 순환 호출을(재귀호출) 이용해서 다시 정렬한다.
(3) 정렬된 부분리스트들을 하나씩 합병한다.
- 퀵정렬
- 합병정렬을 개량한 방법, 자바에서 구현되어 있으면 Arrays.sort 가 퀵정렬 좀더 향상시킨 듀얼피봇 퀵정렬임
- 장점 : 가장 빠른 알고리즘임
- 단점 : 만약 정렬되어 있으면 성능이 대폭 낮아짐
- 삽입 + 합병정렬 = 타임정렬
- 속도가 빠름
결론 : 코딩 테스트 정렬문제를 풀때 Arrays.sort 또는 Collecitons.sort 2개 중에 1개를 선택해서 해결할것 : 상황에 따라 시간초과가 발생할 수 있음
정렬알고리즘 샘플 예제 : 2751번 수 정렬하기 2(실버 5)
시간초과로 인한 : stringBuilder.append() 함수 사용해서 정렬된 문자열을 완성한 후 마지막에 sout 로 출력할 것
반복문안에 System.out.println(); 사용하면 시간초과 발생함(출력함수는 느림)
public class Main {
public static void main(String[] args) {
// 알고리즘 정의 : 문제 해결 절차 / 순서
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt(); // 반복 횟수
StringBuilder stringBuilder = new StringBuilder(); // 시간초과 때문에 사용
ArrayList<Integer> list = new ArrayList<>(); // 숫자배열 :
for (int i = 0; i < num; i++) {
int score = scanner.nextInt(); // 점수 배열
list.add(score);
}
Collections.sort(list); // Arrays.sort (퀵정렬 : 시간초과) , 이것 쓸것: 합병 + 버블 : 팀정렬
// 결과 출력
for (int i = 0; i < list.size(); i++) {
// stringBuilder.append(list.get(i));
stringBuilder.append(list.get(i)); // 시간초과 때문에 출력함수 못씀, 한번에 다붙여서 출력함수 1번만 사용
stringBuilder.append("\n");
}
System.out.println(stringBuilder);
}
}
수학 알고리즘
약수 : 1부터 n까지 1씩 증가하는 수로 반복해서 어떤수를 나누었을때 0 이 되는 수들을 약수라고 함
배수 : 어떤 수 n부터 1씩 증가하는 수를 n 으로 나누었을때 0 이 되는 수들을 배수라고 함
두수 또는 세수의 공통된 약수 : 공약수
두수 또는 세수의 공통된 배수 : 공배수
유클리드 호제법 : 최대공약수 , 최소공배수를 빠르게 구하는 알고리즘
(1) 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
=> a % b = r
=> b % r = r'
...
=> r'%r'' = 0 => r'' 최대공약수임
(2) 최소공배수 : a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다
- 예제) 8, 4 의 최대공약수, 최소공배수 구하기
- 일반 풀이 :
예) 8 4 최대공약수 :
- 8 : 1, 2, 4, 8
- 4 : 1, 2, 4
- 최대공약수 : 4
- 8 : 8, 16, 32 ...
- 4 : 4, 8, 12 ...
- 최소공배수 : 8
- 유클리드 호제법 풀이 :
예) a%b = 0 이면 b 가 최대공약수
- 8 4 최대공약수 : 8 % 4 = 0 => 나누는값 4 : 최대공약수
예) a*b/최대공약수
- 32 / 4 = 8 (최소공배수)
8, 4 의 최대공약수 , 최소공배수를 구하기, 유클리드 호제법을 사용하세요
public class Main {
public static int gcd(int a, int b) { //유클리드 호제법으로 최대공약수를 구함
int r = a % b; // 최초 1번 나머지 구하기
while(r > 0) { //mod가 0이 될 때 b의 값이 최대 공약수
a = b; // 나머지 구하기
b = r; // 다시 계산하기 위해 a 를 b 의 값으로 수정함
r = a % b; // 다시 계산하기 위해 b 를 r 의 값으로 수정함 (2nd 반복문이 실행되면 재계산된 값이 계산됨)
}
return b;
}
public static void main(String[] args) {
int gcdVal = gcd(8, 4); // 최대공약수
int lcmVal = (a * b) / gcdVal; // 최소공배수
System.out.println(gcdVal + " " + lcmVal);
}
}
에라토스테네스의 체 : 1) 1개의 숫자가 소수인지 빠르게 판단하거나 또는 2) 2 ~ n 까지 숫자중 대량의 수들에 대해 소수를 빠르게 판별하는 알고리즘
소수 : 1 과 자기자신으로만 나누어 지는 수
에라토스테네스의 체 알고리즘
- 1) 1개의 어떤 숫자가 소수인지 아닌지 빠르게 판단 : 2 ~ 어떤수의 제곱근까지 반복하면서 나누어 떨어지는 지 검사하면 검사할 숫자를 대폭 줄일수 있다.
어떤 수 n이 1과 자신이 아닌 두 수의 곱으로 되어 있다고 생각해봅시다. (즉, 소수가 아님)
n = a*b 이고 n' 은 n 의 제곱근이라고 표현합시다.
여기서 만약,
a >= n' 이면, a*b = n = n'*n' 이므로 b<=n' 가 됩니다.
따라서 n' 까지만 검사를 하면 합성수를 이루는 a, b 중 작은 수(위에서는 b)까지는 충분히 체크할 수 있고,
합성수가 존재하지 않으면 소수라고 할 수 있습니다.
- 2) 2 ~ n 까지 숫자중 대량의 수들에 대해 소수를 빠르게 판별하는 알고리즘
(1) 1~ n 까지 저장된 이차원 배열을 생성함
(2) 2의배수 지움 : 단, 자기자신은 제외하고 지움 (배수들은 제일 작은수를 최소 1개 약수로 가지므로 소수가 아님)
(3) 3의배수 지움 : 단, 자기자신은 제외하고 지움 (배수들은 제일 작은수를 최소 1개 약수로 가지므로 소수가 아님)
(4) 순차적으로 증가시키면서 n의 배수를 지움. : 단, 자기자신 및 이미 지워진 수는 제외함
(5) 남은 숫자가 소수임 : 배열의 남은 숫자를 모두 지움
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* packageName : algorithm
* fileName : Simple001_10828
* author : kangtaegyung
* date : 2/4/24
* description : 1929 소수 구하기
* 요약 :
* <p>
* ===========================================================
* DATE AUTHOR NOTE
* -----------------------------------------------------------
* 2/4/24 kangtaegyung 최초 생성
*/
public class Main {
public static void main(String[] args) throws IOException {
// 알고리즘 :
// 0) 소수 : 1, 자기자신 이외의 수로 나누어 떨어지지 않으면 소수임
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" "); // 3 16
int start = Integer.parseInt(str[0]); // 3
int end = Integer.parseInt(str[1]); // 16
StringBuilder stringBuilder = new StringBuilder();
int[] arr = new int[1000001];
// 배열 초기화
for (int i = 2; i <= 1000000; i++) {
arr[i] = i; // 2 ~ 1000000 까지 배열에 값 넣기, arr[0] == arr[1] == 0 (소수 아님으로 넣기)
}
// 에라토스테네스의 체 배열 만들기
for (int i = 2; i <= 1000000; i++) {
for(int j = 2*i; j <= 1000000; j += i) { // 반복시 (2~1000000)배수만 반복하기
if(arr[j] == 0) continue;
if(j % i == 0) arr[j] = 0; // 배수는 소수 아님 : 0 저장(소수 아님 표시)
}
}
for (int i = start; i <= end; i++) {
// 소수 아니면 0 맞으면 0보다 큼 : 큰수는 stringBuilder 에 저장해 둔다.
if(arr[i] > 0) stringBuilder.append(i + "\n");
}
System.out.println(stringBuilder);
}
}