[백준] 6549 - 히스토그램에서 가장 큰 사각형 접근 두 가지 풀이법이 있다. 첫째는 스택을 이용한 풀이법, 둘째는 세그먼트 트리를 이용한 풀이법이다. 나는 스택을 사용해 풀었다. 스택을 사용한 경우 쉽게 표현하자면, ‘현재 위치에서 얼마나 갈 수 있는지’를 따지는 것이다. 예를들어 현재 높이에서 오른쪽으로 당긴다고 하면, 오른쪽으로 한 칸씩 ...

[백준] 2098 - 외판원 순회 접근 외판원 순회 2문제에서 약간의 응용을 끼얹으면 된다. 완전탐색을 하는 과정에서 메모이제이션을 끼얹으면 된다! 그런데 메모이제이션을 하려고 하니 사소한 문제가 생겼다. 현재 위치는 이전까지 방문했던 도시들에 의해 결정되는데 이것을 어떻게 표시해야 하지? 이 때 사용할 수 있는 것이 바로 비트마스킹이다. 비트마스킹...

[백준] 10971 - 외판원 순회 2 접근 완전탐색으로 모든 경우의 수를 다 돌아보고 최솟값을 갱신하면 된당. 소스코드 #include <iostream> #include <algorithm> #define INF 987654321 using namespace std; int dist[15][15...

[백준] 12852 - 1로 만들기 2 접근 가장 간단하고 무식한 방법으로 풀 수 있는 방법을 생각해본다. 현재 위치에서 갈 수 있는 모든 선택지를 돌아보면서 BFS를 돌고 1에 도달했을 때 최솟값을 갱신하면 된다(1로 만들기 문제를 이렇게 풀었다) 이것을 반대로 뒤집으면, 1에서 시작해 갈 수 있는 선택지 3개를 현재와 이미 가지고 있던 값 중의 ...

[백준] 15812 - 침략자 진아 접근 가장 단순하고 무식한 방법을 생각해보자. 두 개의 폭탄을 설치할 수 있는 모든 경우에 대해 BFS를 돌려보면서 최소시간을 갱신하면 되지 않을까? 맞다! N, M 이 최대 20으로 가능한 칸의 수는 400이고 두 개의 폭탄을 설치하는 경우의 수는 160,000 즉, 105정도이다. 또한 한 번 BFS를 도는데 ...

[백준] 1027 - 고층 건물 접근 가장 무식한 방법을 생각해보자. 각 건물에서 해당 건물이 보이는지 알아보기 위해 모든 건물에 대해 완전탐색을 실시해 내가 보려는 건물과 이어진 선분에 걸리는 건물이 있는지 확인하면 된다. 따라서 N x N x N=N3의 시간복잡도를 가질 것이다. 지금 다시 보니 이렇게 풀어도.. 풀릴 것 같은데.. 아무튼 조금만...

[백준] 3671 - 산업 스파이의 편지 충분히 큰 수까지의(여기서는 7자릿수까지 가능하므로 10,000,000까지 구해본다) 소수를 미리 구해놓는다. 이후 매 수를 입력받을 때 마다 모든 경우의 수를 돌려보며 소수일 경우 카운트해준다. 소스코드 #include <string> #include <vecto...

[백준] 14618 - 총깡총깡 문제 이해에 가장 노력을 쏟아야 하는 문제다. 풀이 다익스트라로 진서네 집에서 출발해 다른 집들까지 도달하는 거리를 모두 구하고, A그룹과 B그룹의 합을 각각 구해 최솟값을 출력한다. 소스코드 import heapq INF = 999999999 n, m = map(int, input(...

[백준] 1572 - 중앙값 예전에 풀었다가 틀린 뒤로 한동안 잡지 않았던 문제다.(TMI) 이게 대체 왜 펜윅트리인지 엄청 고민하다가 팍 하고 해결책이 떠오른걸 보아 아무래도 헛공부를 했던 것은 아니었던 걸로.. 각설하고, 문제를 풀어보자. 접근 중앙값을 구하려면 우선 주어진 배열을 정렬해야 한다. 하지만 주어진 배열을 정렬하고, 매번 값을 찾아...

[백준] 14950 - 정복자 기본적인 MST문제다. 딱히 주의할 사항도 없다. 소스코드 import heapq n, m, t = map(int, input().split()) parent = [i for i in range(n+5)] pq = [] def find(x): if parent[x] == x: ...