본문 바로가기

Algorithm/백준

 (16)
[Java] 백준 1114번 - 통나무 자르기 통나무 최대 c번 자를 수 있고, 자르는 위치는 정해져 있다. 통나무를 잘라서 만들 수 있는 길이의 최대값의 최소값을 구하는 문제이다. 최대값의 최소값이라는 문구가 주어지면 이분 탐색의 방법을 사용하는 것이 가능하다. 이분 탐색은 주어진 조건을 만족하는 최소값이나 최대값을 log(n)의 시간 복잡도에 찾을 수 있기 때문이다. 잘리는 위치는 정해져있으므로 누적합을 이용해서 통나무의 길이를 더하고, 만약 누적합이 허용되는 길이보다 길다면, 이전의 위치에서 통나무를 잘라준다. 자르지 못하는 상황에서 길이를 초과한 경우에는 break를 이용해 통나무 탐색을 빠져나와서 left와 right의 값을 변경해준다. 첫번째 통나무의 길이를 최소로 하라는 조건이 주어져 있기 때문에, 뒤에서부터 통나무를 자른다. 만약 통나..
백준 2251번 물통(Java) A, B, C 세개의 물통이 있고, 처음에는 A와 B물통에는 물이 비어 있고 C물통에만 물이 차있다. 물통의 최대 용량이 input으로 주어지고, 어떤 물통에서 다른 물통으로 물을 따를 때는 다른 물통이 가득 찰 때까지 혹은, 따르는 물통의 물이 빌 때까지 따를 수 있다. A물통이 비어 있을 때, C의 물통에 차있는 물의 양으로 가능한 것을 오름차순으로 출력해야한다. 물을 따르는 경우는 A->B, A->C, B->A, B->C, C->A, C->B 총 6가지 경우가 있다. 이 때, 현재 물통에 담긴 물의 양을 상태로 저장하여 한번 방문한 상태의 경우는 재방문 하지 않도록 BFS를 구현하여 문제를 풀어주면 된다. 나는 물의 양을 "-"로 연결하여 Key를 만들었고, Set을 이용해서 방문 여부를 체크했다...
백준 1027번 고층 건물 (c++) 중학교 1학년 때 배우는 함수를 이용하면 된다. 볼 수 있는 최소 건물의 높이를 구하는 함수는 f(x) = ax + b 가 된다. 처음에는 모든 건물을 볼 수 있으므로 a = - 999999999 모든 건물을 볼 수 있는 최소값을 잡고, b는 현재 건물의 높이가 들어가되면 된다. 각 건물들을의 왼쪽과 오른쪽을 확인하면서 볼 수 있는 건물의 최소 높이 보다 높다면 num ++ 를 하고, 기울기 a 값을 업데이트 한다. 각 건물별로 볼 수 있는 건물들을 확인하고 최대값을 출력하면 된다. #include using namespace std; int main() { double building[50]; int n; cin >> n; for (int i = 0; i > buildin..
백준 1022번 소용돌이 예쁘게 출력하기 (c++) 소용돌이는 여러개의 정사각형들이 둘러쌓여 있는 것으로 볼 수 있다. 정사각형의 각변에서 숫자가 어떻게 늘어가는지 규칙을 찾아서 출력해주면 된다. 1. 정사각형의 오른쪽 변 행이 위로 올라갈수록 숫자가 증가한다. 행은 변수 i 로 받아서 관리하고, 위로 올라가는 것은 i가 감소하는 것을 의미한다. 그래서 startNum -i 임을 알 수 있고 -i , -i + 1, -i +2 ,..., i 를 0,1,2,3,... i *2 로 바꾸기 위해서 j 를 더해준다. 오른쪽 변이 j이므로 j는 항상 고정된 값이다. 그래서 startNum - i + j 가 오른쪽 변의 숫자 공식이 된다. 2. 정사각형의 위쪽 변, 왼쪽, 아래쪽 변도 동일한 방법으로 수식을 적을 수 있다. 숫자의 최대값을 구하고, 최대값의 길이만큼 ..
백준 2075번 N번째 큰 수 (c++) N*N (N > n; for (int i = 0; i > arr[i]; } sort(arr, arr + n * n); cout > n; // 2. priority queue 풀이 priority_queue pq; for (int i = 0; i > input; pq.push(input); } //상위 n개만 남긴다. while (pq.size() > n) { pq.pop(); } } cout
백준 1774번 우주신과의 교감 (c++) 모든 우주신들을 연결하는데, 연결하는 통로의 길이를 최소로하는 문제이다. 모든 우주신들을 각각 vertex로 보고, 모든 우주신들을 연결하는 Edge를 만들면, Minimun Spanning Tree를 찾는 문제로 해석할 수 있다. MST는 Union and Find를 이용한 크루스칼 알고리즘을 이용하여 해결할 수 있다. 크루스칼 알고리즘의 시간 복잡도는 O(elog(e)) 인데, 우리는 모든 우주신들이 연결되어 있다고 가정하므로 e = (n -1)n / 2 이 된다. n의 범위는 n x = x; this->y = y; this->dis = dis; } }; struct cmp { bool operator()(Edge &t, Edge &u) { return t.dis > u.dis; } }; double..
백준 2638번 치즈 (c++) 외부 공기와 2칸이상 접속한 치즈는 다음 시간에 사라지게 된다. 내부 공기와 외부공기를 구분하는 코드를 짜주어야한다. 문제의 조건에서 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다고 주어졌다. 이 말은 외부의 공기는 가장자리를 시작으로 모두 연결되어 있다고 생각할 수 있다. 그래서 (0,0)에서 DFS를 실행하여, 외부 공기를 모두 방문하고 이를 구분할 수 있는 값으로 바꿔준다. 그런 후에 모든 치즈를 확인하면서 외부 공기와 맞닿아 있는 치즈를 지워주면 된다. 현재의 모눈종이 상태를 map[110][110] 에 저장하여 관리하고, 다음 모눈종이의 상태를 nMap[110][110]에 저장하여 계속 업데이트 하는 과정을 치즈가 없어질 때까지 반복한 후에 얼마나 시간이 걸렸는지 출력하면 된다. #includ..
백준 1967번 트리의 지름 (c++) 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제이다. 다익스트라를 2번 사용하면 지름을 구할 수 있다. #include #include using namespace std; #define MAX_NODE 10010 #define MAX_NUM 10000000 int dist[MAX_NODE]; vector node[MAX_NODE]; int n; void dij(int start) { priority_queue pq; pq.push({0, start}); for (int i = 0; i < MAX_NODE; i++) { dist[i] = MAX_NUM; } dist[start] = 0; while (!pq.empty()) { pair top = pq.top(); pq.pop(); int cost = -t..

티스토리툴바