알고리즘
-
[알고리즘] 이분 탐색(이진 탐색)STUDY/Algorithm 2021. 4. 14. 11:30
이분 탐색(이진 탐색) 이분 탐색은 탐색 범위를 두 부분으로 분할하여 해답을 찾는 방법이다. 이분 탐색을 진행하는 방식을 살펴보자. 1. 이분 탐색을 하고자 할 때는 이미 탐색 대상이 정렬되어있어야 한다. 2. left, right으로 중앙값을 잡아준다. 3. 중앙값과 구하고자하는 값을 비교한다. 4. 비교했을 때, 구하려고 하는 값이 중앙값 보다 큰 경우, left = mid + 1로 두고, 작은 경우는 right = mid - 1로 두고 left > right이 될때까지 계속 반복한다. 이진 탐색의 시간 복잡도 유한 정렬 배열의 크기를 N 배열 내 탐색 값이 없는 최악의 경우 N* 1/2 * 1/2 * 1/2... 범위 내 원소가 하나가 될 때까지 진행되므로 N * (1 / 2)K = 1 -> ..
-
[알고리즘] 분할 정복STUDY/Algorithm 2021. 4. 9. 14:51
분할정복 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각의 문제를 해결하고, 이를 다시 합쳐 문제의 답을 얻는 알고리즘이다. - 분할 정복의 설계 전략 1. Divide : 문제가 분할 가능한 경우, 2개 이상의 문제로 나눈다. 2. Conquer : 나누어진 문제가 여전히 분할 가능하면 다시 분할을 수행한다. 그렇지 않으면 문제를 해결한다. 3. Combine : Conquer 한 문제를 다시 통합하여 원래 문제의 답을 얻는다. 장점 : 문제를 나눔으로써 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결하는데 큰 장점이 있다. 단점 : 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생한다. 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나..
-
[자료구조] 큐와 덱STUDY/Algorithm 2021. 4. 7. 12:28
큐(Queue) 앞에서 배운 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO였다면, 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out, 선입선출)의 특성을 가진다. 예를 들어 큐는, 매표소에 표를 사기 위해 줄을 선 사람들이라고 생각하면 된다. 줄의 맨 앞에 서있는 사람(=먼저온 사람)이 먼저 표를 사게 된다. 이것이 FIFO(First In First Out, 선입선출)이다. 큐는 뒤에서 새로운 데이터가 추가되고, 앞에서 데이터가 하나씩 삭제되는 구조를 가진다. 스택과의 차이점은, 스택은 데이터의 추가와 삭제가 같은 쪽에서 일어나지만, 큐는 데이터의 추가와 삭제가 다른 쪽에서 일어난다. 추가는 후단(Rear)에서, 삭제는 전단(front)에서 일어난다. 큐는 ..
-
[자료구조] 스택STUDY/Algorithm 2021. 4. 5. 10:41
스택이란? 스택(Stack)은 컴퓨터에서 굉장히 많이 사용되는 자료구조이다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책 등이 스택의 전형적인 예이다. 책상에 쌓여있는 책들을 이용하여 스택을 설명해보자. 책상에 새로운 책을 쌓을 때는, 책 더미의 맨 윗부분에 놓는다. 책이 필요하게 되면, 맨 위에 있는 책을 꺼낸다. 중간이나 맨 밑의 책부터 뽑아 사용한다면, 책 더미는 무너져버릴 것이다. 그렇기 때문에, 가장 최근에 들어온 책이 제일 위에 있고, 먼저 나간다. 이러한 입출력 형태를 LIFO(Last In First Out, 후입 선출)라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고, 스택의 중간에서는 데이터를 삭제할 수 없다. 스택의 입출력이 일어나는 부분을 스택 상단(Stack Top)이라고 ..
-
[알고리즘] 그리디 알고리즘(Greedy Algorithms)STUDY/Algorithm 2021. 4. 1. 11:08
그리디 알고리즘(Greedy Algorithms) 그리디 알고리즘은 문제 해결과정에서 순간순간마다 최적이라고 생각되는 해를 선택하여, 최종 해답에 도달하는 문제 해결 방식이다. 위의 그림은, 선택을 해야하는 순간에 가장 최선이라고 생각되는 해를 선택하는 동작방식을 보여준다. 최대 값을 구할때, 1과 9 중 하나를 골라야할때, 그 뒤의 값들은 전혀 고려하지 않고, 당장의 1과 9만 두고 어떤 것을 선택할지 고른다. 1과 9 중에는 당연히 9가 크기 때문에 9를 고르고, 3과 12 중에는 12를 고르게 된다. 이런 식으로 구한 최대 값은 12이다. 하지만 그림을 보면 알 수 있듯 이 이진 트리에서 최대 값은 99이다. 이렇듯 그리디 알고리즘과 같이 순간순간 최선의 결정을 선택하는 것이 항상 문제의 최선의 해..
-
[알고리즘] 백트래킹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는 버퍼를 사용하여 읽기와 쓰기를 하는 함수이다. 버퍼를 사용하지 않는 입력은, 키보드의 입력이 키를 누르는 즉시 바로 프로그램에 전달된다. 반면 버퍼를 사용하는 입력은, 키보드의 입력이 있을 때마다 한 문자씩 버퍼로 전송한다. 버퍼가 가득 차거나 혹은 개행 문자가 나타나면 버퍼의 내용을 한 번에 프로그램에 전달한다. 한번 버퍼를 거쳐 출력되는 것보다, 키보드의 입력을 받는 즉시 출력하는 것이 더 빠른 것이 아닌가 생각할수 있다. 하드디스크는 속도가 느리다. 그리고 외부 장치(키보드, 모니터 등)와 데이터 입출력도 생각보다 시간이 오래 걸린다. 그렇기 때문에 키보드의 입력이 있을 때마다 바로 이동..