sh1mj1_log

BFS(Breadth-First Search) BFS(너비 우선 탐색)은 DFS 와 마찬가지로 그래프를 완전 탐색하는 방법 중 하나로 시작 노드에서 출발해서 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다. 기능 특징 시간복잡도 (V: 노드 수, E: 에지 수) 그래프 완전 탐색 FIFO 탐색 Queue 자료구조 이용 O(V+E) FIFO(선입선출 방식)으로 탐색하므로 큐를 이용하여 구현합니다. 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선시하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다. BFS 구현은 아래 3단계로 설명할 수 있습니다. 1. BFS 시작 노드를 정한 후 자료구조 초기화 BFS 도 DFS 처럼 방문했던 노드는 다시 방문하지 않습니다. 그래..

Comparable 이 인터페이스를 구현하는 각 클래스 개체에 순서를 지정합니다. 이 순서를 natural ordering(자연순서) 라고 하며 클래스의 compareTo 메서드를 자연 비교 메서드라고 합니다. 이 인터페이스를 구현하는 객체 List 나 Array 는 (이하 List) Collections.sort() 로 자동으로 정렬할 수 있습니다. 따로 comparator 을 지정하지 않아도 말이죠. compareTo 메소드 public int compareTo(T o); Comparable 은 compareTo 라는 메서드를 가지고 있습니다. 이 객체를 지정된 객체와 비교하여 순서를 지정하는 메소드입니다. 파라미터 o 는 nullable 입니다. compareTo 메서드를 호출하는 객체가 파라미터인..

바로 문제를 풀어봅시다. 백준 2164번 - 카드2 2164번: 카드2 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 분석하기 큐를 잘 이해하고 있는지를 묻는 문제입니다. 가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출이 떠오릅니다! 카드의 개수의 최대가 500,000 이므로 시간 복잡도의 제약도 크지 않습니다. 큐로 이 문제를 해결해봅시다. 손으로 풀어보기 poll 을 수행하여 맨 앞의 카드를 버립니다. 이어서 바로 add 을 수행해서 맨 앞에 있는 카드를 가장 아래로 옮..

코딩 테스트를 보다가 어떠한 문제의 답에서 Scanner 와 System.out.print 함수를 사용하지 않고 BufferedReader 와 BufferedWriter 을 사용하는 것을 발견했습니다. 그런데 왜 이 두 클래스를 사용해야 하는 것일까요? 그래서 InputStream 부터, InputStreamReader, BufferedReader 을 알아보려고 합니다. 물론 OutputStream, OutputSreamReader, BufferedWriter 도 알아보구요. 그리고 코딩테스트에서 BufferdReader 와 BufferedWriter 을 사용해야 하는 이유도 알아봅시다. InputStream / OutputStream 바이트 단위 입출력을 위한 최상위 입출력 스트림 클래스 InputSt..

프로그래밍을 할 때 "예외가 많이 발생할 것 같은 case 니까 예외 처리 잘 해야 될 것 같은데?" 라는 말을 자주 들은 적이 있다. 그래서 예외가 일어날 것 같은 상황에서 try - catch 문(java에서)으로 예외를 처리하고는 했는데 정작 이 경우 if 조건문으로 처리하는 것과 무엇이 다른지 정확히 알지 못하는 것 같았다. 그래서 자바 예외 처리를 자세히 공부하고 정리하려고 한다. 기본적인 내용은 "Do it! 자바 프로그래밍 입문" 교재를 참고하였습니다. 예외 클래스 시스템에서 오류는 보통 프로그래머가 코드 작성 실수로 인해 발생하는 'Compile Error' 와 프로그램이 실행되는 도중 의도하지 않은 동작을 하여 발생하는 'Runtime Error' 로 나뉜다. 그리고 RuntimeErro..