sh1mj1_log

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

DFS(Depth-First Search) 깊이 우선 탐색은 DFS(Depth-First Search). 그래프 완전 탐색 기법 중 하나입니다. 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다. 기능 특징 시간 복잡도 (V: 노드 수, E: 에지수) 그래프 완전 탐색 재귀함수로 구현 스택 자료 구조 이용 O(V+E) DFS 는 실제 구현 시 재귀함수를 이용하므로 Stack Overflow 에 유의해야 합니다. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬이 있습니다. DFS 는 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이..

알고리즘에서의 정렬은 크게 아래와 같습니다. 버블(bubble) 정렬: 데이터의 인접 요소끼리 비교하고 swap 연산을 수행하며 정렬 선택(selection) 정렬: 대상에서 가장 크거나 작은 데이터를 찾아가 반복하면서 정렬 삽입(insertion)정렬: 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬 퀵(quick) 정렬: pivot 값을 선정해 해당 값을 기준으로 정렬 병합(merge) 정렬: 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬 기수(radix) 정렬: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬 이 중에서 버블 정렬을 알아보고 문제를 풀어봅시다. 버블 정렬 버블 정렬(bubble sort) 는 두 인접한 데이터의 크기를 비교해 정렬합니다. 매..

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

자바 코딩테스트 공부 중 백준 11286 절댓값 힙 문제를 푸는 중에 Priority Queue 을 사용하는 방법에 대해 간단하게 정리해보려고 합니다. 이 포스팅에서는 매우 간단한 사용 방법을 설명합니다. 추가로 PriorityQueue 의 인자로 comparator 을 가질 수 있는데 이 부분은 오른쪽 링크 https://sh1mj1-log.tistory.com/122 포스팅하단에서 확인할 수 있습니다. Priority Queue(우선순위 큐)? Priority Queue 는 Queue 와 구조가 비슷합니다. Queue 는 FIFO(First In First Out) 구조로 먼저 들어온 순서대로 데이터가 나가는 것인 반면에 Priority Queue 는 데이터의 우선순위를 정해 우선순위가 높은 순서대로..

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

1.6 Storage Devices From a Hierarchy 실제로는 많은 computer systems 의 저장 장치는 Memory hierarchy(메모리 계층 구조) 로 구성되어 있습니다. 성능을 향상시키기 위해 여러 cache 을 활용하는 것처럼 전체 메모리 구조의 대한 이해를 활용할 수 있습니다. 1.7 The OS(Operating System) Manages the Hardware 운영체제는 하드웨어를 관리합니다. 이전의 hello 프로그램을 예로 들어보면 shell 에서 키보드로 입력하면 알아서 disk → 메인 메모리 → display 로 접근하여 출력을 수행합니다. 우리가 직접 키보드, disk, 메인 메모리에 접근하지 않았는데도 말이죠. 이러한 기능들은 OS 에서 제공되는 서비스..

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

Stack 스택은 삽입과 삭제가 LIFO(Last-in First-out = 후입선출) 로 이루어지는 자료구조입니다. LIFO 는 삽입과 삭제가 한쪽에서 만 일어나는 특징이 있습니다. top: 삽입과 삭제가 일어나는 위치 push: top 위치에 새로운 데이터를 삽입하는 연산 pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산. Stack 은 DFS(Depth First Search = 깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 합니다. LIFO 는 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문입니다. Queue 큐는 삽입과 삭제 연산이 FIFO(First-in First-out ..

Chap 01. A tour of computer system. 먼저 computer system 은 Hardware 와 System Software 로 이루어져 있으며 이 두 개가 같이 작동하여 application program 을 실행시킵니다. 시스템 구현 방식은 계속해서 변화했지만 이러한 근본적인 개념은 변하지 않습니다. 이 책을 통해 code 최적화, 보안 문제 해결, error 해결, 동시성 문제 등을 배울 것입니다. 1.1 Information is Bits + Context 정보는 비트와 컨텍스트입니다. 텍스트 문자는 ASCII 표준을 사용하여 표현할 수 있습니다. 각 문자를 바이트 길이 값으로 표현하면 연속된 바이트 파일에 저장할 수 있지요. ASCII 문자로 구성된 파일은 text fi..