leesche blog

백준 문제를 풀다가 Buffer로 입출력 부분에서 막혀서 따로 공부를 한다. [Java 자바 입출력] BufferedReader/BufferedWriter [자바 입출력 함수] BufferedReader / BufferWriter BufferedReader/BufferedWriter은 이름처럼 버퍼를 이용해서 읽고 쓰는 함수입니다. 이 함수는 버퍼를 이용하기 때문에 이 함수를 이용하면 입출력의 효율이.. jhnyang.tistory.com [Java] BufferedReader, BufferedWriter를 활용한 빠른 입출력 BufferedReader/BufferedWriter는 Buffer에 있는 IO 클래스입니다. 입력된 데이터가 바로 전달되지 않고 중간에 버퍼링이 된 후에 전달되됩니다. 출력도 마..

문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를..

이진 검색 이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 방법 (정렬된) 배열의 중앙에 위치한 요소를 검색하여 원래 검색하려는 값과 크기를 비교한다. 만약 값이 크다면, 중앙값 다음 순서부터 끝까지 배열의 중앙 값을 찾는다. 그리고 원래 검색하려는 값과 비교한다. 그렇게 검색 범위를 한 번에 절반씩 좁혀나간다. 중앙값이 검색하려는 값과 일치하거나 검색 범위가 더 이상 없는 경우 알고리즘을 종료한다. 이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다. 복잡도 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다. 복잡도는 아래의 두 가지 요소를 가지고 있다. 시간 복잡도:..

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..

좋은 알고리즘의 특징 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. 타당성 : 구현할 수 있고 실용적이어야 한다. 입력 : 정의된 입력을 받아들일 수 있어야 한다. 출력 : 답으로 출력을 내보낼 수 있어야 한다. 유한성 : 특정 수의 작업 이후에 정지해야 한다. 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다. 알고리즘 개발의 정형적인 단계 문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화 분류 구현 : 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등. 설계 : 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한..

해시는 Key-Value 쌍으로 데이터를 저장하는 자료구조입니다. 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 parti..

데이터 집합에서 원하는 값을 가진 요소를 찾아내려면 어떻게 해야 할까? 검색과 키 주소록에서 원하는 사람을 검색한다고 가정했을 때, '키'를 사용해 사람을 찾는다. '키(key)'는 형이 여러 개다. 예를 들어 (국가, 나이, 이름 등 ...) 키 값과 일치하거나, 키 값의 구간을 지정하거나, 키 값과 비슷하도록 지정해서 검색할 수 있다. 배열에서 검색하기 배열 검색의 경우 다음의 알고리즘을 활용한다. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다. 해시법: 추가,삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다. 체인법: 같은 해시 값의 데이터를 선형 리스트로 연..

클래스 클래스는 임의의 데이터형을 자유로이 조합하여 만들 수 있는 자료구조이다. 자바의 클래스란, 노션에서는 템플릿, PPT에서는 슬라이드 마스터, 티스토리 블로그에서는 서식 같은 존재가 아닐까. 클래스는 클래스 이름, 데이터 요소(필드)로 구성된다. 필드는 임의의 데이터형이 될 수 있다. 클래스형 변수를 사용할 때는 먼저 클래스형 변수(실체를 참조하는 변수)를 만들고, 그리고 실체인 클래스 인스턴스를 생성해야 한다. // 클래스 XYZ class XYZ { int x; // int형 필드 long y; // long형 필드 double z; // double형 필드 } XYZ a; // XYZ형의 클래스형 변수 a 선언 a = new XYZ(); // XYZ형의 클래스 인스턴스(실체를 생성) 클래스의 ..

간단하게 2차원 배열을 선언하자면, int[][] x = new int[2][4] 과 같다. Java는 엄밀한 의미에서 다차원 배열이 없다. 2차원 배열을 '배열의 배열'로 생각하고 3차원을 '배열의 배열의 배열'로 생각하기 때문이다. 따라서 배열 x의 형은 아래와 같다. int 형을 구성 자료형으로 하는 배열"을 구성 자료형으로 하는 배열 다차원 배열 개념을 연습해보기 위해 예시를 들어보자. 한 해의 경과 일 수를 나타내는 프로그램 package chap02; import java.util.Scanner; // 그 해 경과 일수를 구함 class DayOfYear { // 각 달의 일 수 static int[][] mdays = { {31, 28, 31, 30, 31, 30, 31, 31, 30, 31..

어떤 정수 n에 대하여 아래의 조건을 만족하면 소수임을 알 수 있다. 2부터 n-1 까지의 어떤 정수로도 나누어 떨어지지 않는다. 그래서 처음 아래와 같은 프로그램을 작성한다면, 나눗셈을 하는 횟수가 너무 많아진다. 책에서는 위와 같은 문제를 해결하기 위해 아래와 같은 코드를 제시했다. 아래 알고리즘은 배열을 이용했고, 정수 n 이 소수이려면, 2부터 n-1 까지의 어떤 소수로도 나누어 떨어지지 않는다. 는 조건을 만족해야 한다는 아이디어를 바탕으로 하고 있습니다. package chap02; // 1,000 이하의 소수를 열거(버전 2) class PrimeNumber2 { public static void main(String[] args) { int counter = 0; // 나눗셈의 횟수 int..