공부하자

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS의 구현을 묻는 아주 간단한 문제이다. 우선, DFS와 BFS의 의미는 다음과 같다. DFS : Depth-First Search (깊이 우선 탐색) / BFS : Breadth-First Search (너비 우선 탐색) DFS는 함수의 재귀 호출을 이용하여 소스코드로 구현하게 되지만, BFS의 경우엔 자료구조 Queue를 사용하여 소스코드로 구현하는것이 일..

Vector 란? Vector는 C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너로, 사용자가 손쉽게 사용하기 위해 정의된 class이다. Vector는 쉽게 말해 크기가 가변적으로 변하는 배열이라고 할 수 있다. 속도적인 측면에서는 배열에 비해 떨어지지만 메모리를 효율적으로 관리할 수 있다는 장점이 있어 굉장히 많이 사용한다. vector는 배열과 마찬가지로 원소들이 하나의 메모리 블록에 연속하게 저장된다. 그렇기에 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 부하가 발생하게 된다는 점은 단점으로 꼽히고 있다. Vector의 구조 Vector를 생성하면 메모리 heap에 생성되며 동적할당된다. front() : 첫번째 원소 back() : 마..

STL : 표준 템플릿 라이브러리 (Standard Template Library) C++를 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. C++ 표준 라이브러리 (C++ Standard Library) C++과 C++ ISO 표준 자체로 쓰여진 클래스들과 함수들의 집합이다. C++ 표준 라이브러리는 여러 Generic 컨테이너들, 그리고 이러한 컨테이너들과 함수 객체, Generic 문자열, stream, 몇몇 언어 특징 그리고 power 연산 같은 작업을 위한 함수들을 제공한다. C++ 표준 라이브러리의 특징은 namespace 내에 선언된다는 것이다. (.h 헤더가 아님) C++ 표준 라이브러리와 STL이 많은 특징들을 공유하지만, 둘 중 어느것도 다른 하나의 상위 집합은..

배열 (Array) : 여러 데이터를 하나의 이름으로 그룹핑하여 관리하기 위한 자료구조 배열의 장점 배열의 단점 크기가 정해져 있다. (이미 정해진 크기로 인해 작고 가벼우며, 메모리 또한 작음) 크기가 정해져 있다. (미리 크기 지정 필요, 크기보다 큰 인덱스에 접근하면 에러 발생) 기능이 없다. (단순함, 좋은 구성요소가 될 수 있음) 기능이 없다. (불편함, 데이터의 삭제, 추가 등이 불가능) 리스트 (List) : 순서가 있고, 값의 중복을 허용하는 자료구조 추가하는 경우 Array는 지정 인덱스에 추가할 경우, 크기가 제한되어 있어 데이터가 덮어 씌워진다. List는 지정 인덱스에 추가할 경우, 유동적으로 한칸 뒤로 밀고 끼어든다. 삭제하는 경우 Array는 지정 인덱스를 삭제할 경우, 그 인덱..

JAVA에서 기본적으로 입출력에 사용하는 Scanner는 사용이 편리하고 다양한 타입을 다룰 수 있지만, 속도가 느린 단점이 있다. 따라서, 구현한 프로그램의 시간 복잡도를 줄이기 위해서는 입출력에 Scanner 대신 BufferedReader와 BufferedWriter를 사용하는 것이 좋다. 사용 속도 Scanner - 사용이 편리 - 공백과 개행 문자를 경계로 입력 값을 인식 - 입력받을 수 있는 데이터 타입이 다양 느림 BufferedReader - 사용이 번거로움 - 개행 문자만을 경계로 입력 값을 인식 - 데이터 타입은 String으로 고정 => 필요한 데이터를 처리하기 위해서는 추가적인 가공 필요 - 예외처리 필요 (try&catch 혹은 throw 이용) 빠름 (입력된 데이터가 바로 전달되..