본문 바로가기

Problem Solving12

ㅇㅅㅇ ㅡㅅㅡ myCPP #include #define X first #define Y second using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const ll INF = 1e18; const int inf = 2e9; const int SIZE = 1 0) return 1; else if (ret == 0) return 0; else return -1; } bool isIntersect(pll a, pll b, pll c, pll d) { ll ab = ccw(a, b, c) * ccw(a, b, d); ll cd = ccw(c, d, a) * ccw(c, d, b); if (ab == 0 && cd == 0) { // .. 2022. 10. 6.
백준 13511번 | 트리와 쿼리 2 (C++ 풀이) 문제 https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 풀이 사용 알고리즘 : LCA, Sparse Table 시간 복잡도 : O(M * logN) LCA를 이용하여 풀 수 있는 문제입니다. 주의점은 N, M의 상한이 10만이므로, Naive LCA는 O(NM)이 되어 TLE를 피할 수 없습니다. 따라서 Sparse Table을 정의해서 LCA를 O(M logN)으로 최적화해주면 됩니다. 이제 문제의 두 가지 쿼리에 대해 어떤 방식으로.. 2022. 10. 2.
백준 16234번 | 인구 이동 (C++ 풀이) 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 사용 알고리즘 : BFS 시간 복잡도 : O(ans * N3) BFS를 통해 그래프 연결 요소(connected components)를 구하고, 적절히 시뮬레이션을 돌려주어 풀었던 문제입니다. 먼저 인접한 각 나라들의 인구수 차이가 L 이상 R 이하라면 국경선이 열리면서 하나의 연합이 형성됩니다. 이 문제를 풀려면 어떤 나라들이 어떻게 연합을 이루는지를 알 필요가 있습니다.. 2022. 10. 2.
백준 1966번 | 프린터 큐 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 사용 알고리즘 : 구현 사용 자료구조: 큐, 우선순위 큐 큐를 활용하는 문제입니다. 이 문제에는 중요한 조건이 있습니다. 인쇄할 차례가 온 어떤 문서를 K라고 할 때, K의 중요도보다 더 높은 중요도를 가진 다른 문서가 있다면, K를 인쇄하지 않고 맨 뒷 순서로 보낸다는 것이죠. 따라서, 이 문제를 풀기 위해선 현재 남은 문서들 중 가장 높은 중요도의 값을 관리해주어야 합니다. 이제 저 색.. 2022. 10. 2.
백준 15686번 | 치킨 배달 (C++ 풀이) 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 사용 알고리즘 : 완전 탐색 + 백트래킹 삼성 SW역량테스트 문제였네요. 저는 일단 완전탐색 + 백트래킹 + 약간의 그리디한 생각으로 풀었습니다. ​ 먼저 문제 해석을 잘 해야 합니다. 주어진 치킨집 중에서 최대 M개를 선택하고, 도시의 치킨 거리의 최소를 구하라고 합니다. 여기서 생각해볼만 한 것은, 치킨집을 최대 M개 선택하라 하였으니, 1개부터 M개까지 고를 .. 2022. 10. 1.

티스토리툴바