백준
-
[알고리즘] 백트래킹STUDY/Algorithm 2021. 3. 17. 12:01
백트래킹 백트래킹이란, 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다. 백트래킹의 목적은 해가 될 조건을 만족시키는 "진짜 해"를 효율적으로 찾는것이 백트래킹의 목적이다. 백트래킹은 탐색을 진행하다가 더 갈 수 없게되면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었고, 주로 재귀적으로 구현한다. '모든 해'란, 예를 들어 탈출로가 두개인 미로 문제를 생각해보자. 이러한 미로에서 탈출할 수 있는 최단 경로는 2개가 존재한다. 이 2개 해를 일컬어 '모든 해'라고 한다. '후보 해' 란, 해가 될 수 있는 가능성을 가진 부분해의 조합이다. 백트래킹은 DFS를 빼고 이야기 할 수 없는 알고리즘이다. DFS는 백트래킹의 골격을 이루는 알고리즘이다. 백트래킹은 DFS 방식으로..
-
[Java] 빠른 입출력을 위한 BufferedReader, BufferedWriter, StringTokenizer, StringBuilderSTUDY/Algorithm 2021. 3. 16. 13:55
BufferedReader / BufferedWriter BufferedReader와 BufferdWriter는 버퍼를 사용하여 읽기와 쓰기를 하는 함수이다. 버퍼를 사용하지 않는 입력은, 키보드의 입력이 키를 누르는 즉시 바로 프로그램에 전달된다. 반면 버퍼를 사용하는 입력은, 키보드의 입력이 있을 때마다 한 문자씩 버퍼로 전송한다. 버퍼가 가득 차거나 혹은 개행 문자가 나타나면 버퍼의 내용을 한 번에 프로그램에 전달한다. 한번 버퍼를 거쳐 출력되는 것보다, 키보드의 입력을 받는 즉시 출력하는 것이 더 빠른 것이 아닌가 생각할수 있다. 하드디스크는 속도가 느리다. 그리고 외부 장치(키보드, 모니터 등)와 데이터 입출력도 생각보다 시간이 오래 걸린다. 그렇기 때문에 키보드의 입력이 있을 때마다 바로 이동..