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는 사이클이 존재하지 않기 때문에 그래프와 트리 모두 해당된다. 또 그래프는 다른 정점들과 떨어진 정점들..

이 문제는 설명자체는 간단한데, 트리가 주어지고 1번 쿼리는 트리의 노드를 바꾸는 거고, 2번 쿼리는 현재 만들어진 트리에서 1번 노드에서 v 노드로 가는 길에 1번 노드와 가장 가까운 검정 노드의 번호를 출력하는 문제이다. 이 문제도 여러 가지 풀이 방법이 있는 걸로 알고 있고 가장 대표적인 풀이가 HLD(Heavy heavy Light Decomposition)으로 알고 있는데, 그 풀이가 아닌 ETT(오일러 투어 테크닉) 와 lazy 세그 (느리게 갱신되는 세그먼트 트리), sparse table(희소 배열)을 이용한 풀이를 작성하겠다. 이 문제의 핵심은 2번 쿼리니 1번 쿼리는 2번쿼리의 구조 내에서 구현해 줘야 된다. 그러므로 2번 쿼리부터 설명하겠다. 1부터 v 로 가는 길에서 1에 가장 가까..

이 문제는 초기 문자열과 만들어야하는 문자열이 주어질 때, 각 위치의 스티커를 떼고 붙이고, 구매 등의 방법을 사용해 만들어야하는 문자열이 초기 문자열의 부분 문자열이 되도록 하는 최소값을 구하는 문제이다. 문제 설명만 봤을 때는 어려워 보일 수도 있지만 문자열의 길이가 500이 안되기 때문에 모든 경우를 탐색하면서 최소값을 계산해주면 된다. 부분 문자열을 만들 수 없는 경우 -1을 출력하라고 되어있는데, 이는 구매할 수 있는 스티커 중에 부분 문자열에 필요한 스티커가 없을 때 -1을 출력해주면 된다. 부분 문자열을 만들기 위해서 부분 문자열에 해당될 부분 중, 바꿔야 될 부분의 스티커를 모두 떼준다. 그후 뗀 스티커와 다른 범위에 있는 스티커까지 고려해서 어느걸 고르는 것이 최소값이 되는지 판단해주면 ..

이 문제는 입력된 9개의 숫자 중 합이 100이 되는 7개의 숫자를 고르면 되는 문제인데, 이를 다시 생각해보면 나머지 두명의 값을 제외했을 때 100이 되는 경우를 고르는 문제로 바꿀 수 있다. 이 경우 2중 반복문을 통해 두 수의 합을 전체 합에서 뺀 값이 100이 된다면 해당 두값을 제외한 나머지 값들을 출력해주면 된다. 문제가 스페셜 저지이므로 답이 여러개가 될 수 있기 때문에 여러가지 답이 나올 수 있지만 맨처음에 나온 값을 출력해주면 된다. n=9 l=[int(input())for i in range(n)] l.sort() s=sum(l) nanjaeng=[0,0] for i in range(n): for g in range(n): if i!=g and s-100==l[i]+l[g]: nanj..

완전 탐색 또는 브루트 포스라고 불리는 이 알고리즘은 이름 그대로 모든 경우의 수를 다 탐색해 보는 것을 말한다. 예를 들어 입력으로 들어온 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)에 계산하는 방법이 존재하는데, 이..