본문 바로가기

Algorithm22

BOJ 1725 히스토그램 문제 링크 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 요약 히스토그램 안에서 색칠할 수 있는 직사각형의 최대 크기를 구하는 문제(한 막대그래프의 가로길이는 1로 봄) 풀이 BOJ 2104 부분배열 고르기 문제와 유사한 문제다. 분할 정복으로 해결할 수 있으며 부분 히스토그램의 시작점을 s, 끝점을 e, 그 중간값을 mid로 두었을 때 최대 넓이는 세 가지 중에 있다. s~mid 부분 배열중 최대 넓이, mi.. 2022. 3. 14.
BOJ 2104 부분배열 고르기 문제링크 : https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 요약 크기가 N의 1차워 배열의 부분배열의 합과 부분배열에서의 최솟값의 곱의 최대값을 구하는 문제 풀이 완전 탐색으로 해결하기에는 시간초과가 우려된다. 분할정복을 통해 해결해보았다. 두 부분으로 나눠서 왼쪽에서 가장 큰 점수를 갖는 부분 배열과 오른쪽에서 가장 큰 점수를 갖는 부분배열을 비교해준.. 2022. 3. 12.
BOJ 1629 곱셈 문제링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 요약 (A^B)%C를 구하는 문제 풀이 주어지는 세 수의 최댓값이 2,147,483,647이다. 지수값이 저렇게 큰수면 곱하다가 시간초과 나버린다. 시간복잡도를 줄이기 위해서 분할정복으로 해결하여야 한다. 지수 B가 짝수인 경우에는 A^B=(A^(B/2))^2 이고 홀수인 경우엔 A^B = A*(A^((B-1)/2))^2이다. 이렇게 연산을 logB개로 줄일수 있게 되고 시간복잡도도 즉 O(logB)가 된다. 숫자가 매우 크기 때문에 long lon.. 2022. 3. 12.
너비 우선 탐색(bfs) bfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32를 참고 하자. 너비 우선 탐색(bfs) BFS(Breadth First Search) 이름 뜻 그대로 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 장점 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다. 단점 재귀 호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색할 노드들을.. 2022. 3. 11.

티스토리툴바