joseph0528 코딩 블로그

이분 탐색이란 이름 그대로 두 개로 나누어 탐색을 한다는 것이다. 기본적인 구조는 분할정복과 유사하지만, 반을 나누고 둘 중 한쪽으로만 탐색을 진행한다는 점에서 차이가 있다. 그럼 이분탐색은 어떻게 진행하는지 알아보자. 이분 탐색의 가장 대표적인 예로 Up, Down 게임이 있다. Up, Down 게임은 상대방이 어떤 숫자를 생각하면, 도전자가 숫자를 예측하며, 상대방은 그 숫자에 대해 Up, Down을 말한다. 그럼 이 방법에서 최소한의 횟수로 정답을 맞추는 방법은 뭘까 바로 내가 말할 수 있는 숫자의 범위 중, 정확히 반에 해당하는 숫자를 말하는 것이다. 게임을 통해 예시를 들어보자. 해당 게임에서는 상대방이 77이라는 숫자를 생각하였고, 우리는 그 숫자를 맞추기 위해 숫자를 부를 것이다. 일단 우리..

깊이 우선 탐색(DFS) 란 그래프를 탐색하는 방법 중 하나이다. 그림 1을 예시로 들어보자. DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법인데 탐색을 시작할 정점을 A라고 정해보자. A에서 시작했을 때, A와 연결되어 있는 정점은 B, C이다. 이때 DFS는 자신과 연결되어 있는 정점을 먼저 탐색한다. 일단 B부터 탐색해 보겠다. 여기서 초록색은 이미 탐색한 정점, 파란색은 현재 도달한 정점이다. 여기서 B는 D와 E 를 갈 수 있다. A 도 갈 수 있지만 이미 탐색을 했기 때문에 D 와 E 중 하나를 탐색해 준다. 이번엔 D에서 탐색할 수 있는 정점을 보면 H밖에 없다. 그러므로 H를 탐색해 준다. H에 도달했을 때, H에서 갈 수 있는 정점은 E다. 만약 이 그래프에 방향이 있다면, 방향에 따..

그래프(Graph) 그래프란 정점과 간선으로 이루어진 집합을 말한다. 이런 이미지가 있다고 할 때 숫자가 쓰여있는 원을 정점 정점 사이를 잇는 선을 간선 이라고 한다. 이때 간선은 두 정점 사이 여러 개 있을 수 있으며, 방향이 존재하거나 가중치가 존재하는 등 여러 형태가 있으며, 이를 이용한 다양한 그래프가 존재한다. 트리(Tree) 트리란 그래프의 종류 중 하나로 나무처럼 생겼다고 해서 붙여진 그래프의 하위분류이다. 트리는 그래프와 비슷하게 생겼지만 방향을 제외했을 때, 사이클이 존재하면 안 된다. 그림 1은 그래프는 될 수 있지만 2-3-4-5의 사이클이 존재하기 때문에 트리일 수 없다. 그림 2는 사이클이 존재하지 않기 때문에 그래프와 트리 모두 해당된다. 또 그래프는 다른 정점들과 떨어진 정점들..

완전 탐색 또는 브루트 포스라고 불리는 이 알고리즘은 이름 그대로 모든 경우의 수를 다 탐색해 보는 것을 말한다. 예를 들어 입력으로 들어온 N 개의 수 중, 서로 다른 숫자를 더했을 때 짝수가 되게 하는 경우의 수를 구하는 코드를 작성해야 될 때 완전 탐색을 이용하면 이렇게 작성할 수 있다. n=int(input()) l=list(map(int,input().split())) cnt=0 for i in range(n): for g in range(n): if i!=g and (l[i]+l[g])%2==0: cnt+=1 print(cnt) 이렇게 작성하면 위 문제에서 원하는 답을 구할 수 있고, 해당 코드의 시간복잡도는 O(N^2)가 된다. 해당 문제 같은 경우 O(N)에 계산하는 방법이 존재하는데, 이..