말하는 컴공감자의 텃밭

정점과 가중치가 존재하는 간선이 주어진 상태에서 우리는 모든 정점을 가장 적은 비용으로 연결한 그래프를 최소 신장 트리라고 말한다. MST(Minimum Spanning Tree) 라고 말하며 이러한 문제에서 사용되는 알고리즘이 바로 프림과 크루스칼 알고리즘이다. 같은 목적을 지니고 있지만 접근방식이 조금 다른데 유념해서 알아보자 프림 알고리즘한 정점에서 시작해서 연결된 간선들 중 가장 가중치가 낮은 간선을 선택하며 트리를 확장하는 방식이다.시작점에서 점진적으로 최소 스패닝 트리를 완성해 나가는 그리디한 방식인데 순서는 다음과 같다.  초기화:임의의 정점을 선택해 시작한다.선택한 정점을 기준으로 연결된 간선 중 가중치가 가장 작은 간선을 선택한다.트리 확장:선택된 간선에 연결된 정점을 트리에 추가한다.이..

우리는 문제를 풀면서 알고리즘 문제가 어떤 유형의 문제인지 판단해야한다.그 중 한가지 팁인데 시간제한을 보는것이다. 인풋에 대한 적절한 시간 복잡도N의 범위가 500: 시간 복잡도 O(N^3) 이하N의 범위가 2,000: 시간 복잡도 O(N^2) 이하N의 범위가 100,000: 시간 복잡도 O(N log N) 이하N의 범위가 10,000,000: 시간 복잡도 O(N) 이하N의 범위가 10,000,000,000: 시간 복잡도 O(log N) 이하 N의 범위가 500 : 시간 복잡도: O(N^3) 이하500^3 = 125,000,000 예시 알고리즘: 플로이드-워셜, 3중 for 문을 사용하는 알고리즘N의 범위가 2,000 : 시간 복잡도: O(N^2) 이하2,000^2 = 4,000,000 예시 알고리즘:..

1. Optional이란 무엇인가? Optional은 Java 8에서 추가된 클래스다.이 클래스는 null이 들어올 수 있는 값을 감싸는 컨테이너 역할을 한다.Optional을 사용하면 null 값을 직접 다루지 않고도 null 처리를 할 수 있다. 예를 들어, 다음과 같은 JPA 메서드에서 Optional을 사용할 수 있다. Optional findByMemberAndStudy(Member member, Study study); 현재 개발중인 프로젝트에서 Jpa 메서드를 작성할때도 사용했었다. 2. 왜 Optional을 사용하는가?2.1 NullPointerException 방지 일명 "NPE"Optional을 사용하면 null 값을 직접 다루지 않기 때문에 NullPointerException을 방지..

Clone 인스턴스가 스스로를 복사하기 위해 사용. Cloneable 인터페이스 구현 권장. 깊은 복사는 직접 오버라이드하여 구현해야 함. 👀 얕은 복사와 깊은 복사가 존재하는데 간단하게 설명 후 예시를 통해 코드로 확인해보자. 얕은 복사는 객체의 필드 값을 새 객체로 복사하는 과정에서, 기본 타입의 필드는 그 값이 직접 복사되지만, 참조 타입의 필드는 메모리 주소(참조)만 복사된다. 이는 참조 타입의 필드가 가리키는 객체는 복사되지 않고, 원본 객체와 복사된 객체가 같은 객체를 참조하게 된다. 결과적으로, 얕은 복사를 통해 생성된 객체에서 참조 타입의 필드를 수정하면, 그 변경사항이 원본 객체에도 영향을 미친다. 두 객체가 동일한 참조 타입의 인스턴스를 공유하기 때문이다. 깊은 복사는 객체를 복사할 때..

BufferedReader, StringTokenizer, BufferedWriter 코테 준비하면서 자바 기본 I/O인 Scanner 만 사용했었다. 스캐너는 데이터 유형을 유연하게 선택할 수 있지만 속도가 느리다는 단점이 존재했다. 메모리와 속도적으로 알고리즘 문제 풀이에서 제한이 생기는 경우가 존재해서 방식을 바꾸려고한다. 백준 입력 속도 비교 https://www.acmicpc.net/blog/view/56 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 걸리는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김 버퍼 크기 실행 속도(백준 참고) BufferedReader 8KB 0.6585 sec Sc..