반응형 알고리즘2 자바 코딩테스트를 위한 정리 - 입출력2 (EOF 처리) EOF란 End of File의 줄임말로 파일의 끝을 뜻합니다. 알고리즘 테스트에선 일반적으로 테스트 케이스의 수를 따로 명시해주지 않고 입력을 가변적으로 받을때 사용하게 됩니다. 예로 '4375번 문제 (문제 제목: 1)'이 있습니다. 이와 같이 문제에서 테스트케이스의 개수 혹은 끝을 명시해주지 않을때 어떻게 처리해야하는지 알아보도록 하겠습니다. 자바의 대표적인 두가지 입력 클래스인 아래 2가지 기준으로 설명하겠습니다. 1. Scanner 2. BufferedReader 1. Scanner Scanner에서 EOF를 처리하는 방법은 hasNext()메소드를 사용해서 처리하는 방법입니다. 해당 메소드는 다음 입력이 있으면 true 없으면 false를 반환합니다. 이를 사용해서 EOF여부를 확인할 수 있습.. 2022. 12. 21. 정렬 알고리즘 3 : 계수 정렬(Counting sort) 세 번째로 알아볼 정렬 알고리즘은 바로 계수 정렬! 계수 정렬은 수의 범위가 적을 때 사용하면 좋은 정렬 알고리즘으로 배열의 가장 큰 값에 따라 시간 복잡도가 달라진다. 배열의 가장 큰 값이 k라고 한다면 O(n+k)의 시간 복잡도를 갖는다. 즉, 입력에 비해서 원소들의 값의 범위가 적다면 계수정렬을 사용하는 것이 효율적인 방법이 될 수 있다! 방법 1. 입력된 배열중 가장 큰 값(k) 찾기 2. k+1 크기의 0으로 초기화된 배열 생성한다. 이는 입력된 배열의 원소가 각각 몇 개가 있는지 셀 배열이다. 3. 배열의 원소를 하나씩 검사하여 2번에서 생성한 배열의 인덱스에 해당하는 값을 1씩 올려준다. (즉, 각 값이 몇 개가 나왔는지 카운팅 해준다.) 4. 각 인덱스를 값만큼 반복하여 출력한다. 예시 배.. 2022. 1. 31. 이전 1 다음 반응형