Minhee Lee

랩실에서 과제 하려다가 초급 스터디를 들었는데 많은 걸 배웠고 재밌었다. 끝나고 스터디에서 다룬 문제들 풀다가 기록하고 싶은 것들 * Bit Masking * BOJ 15661 링크와 스타트 한 팀을 기준으로 그 팀에 속해 있는 사람들을 비트로 관리할 때 두 사람 (i, j)이 같은 팀에 속해 있는지는 둘 다 비트가 켜져 있거나 꺼져 있는지로 확인할 수 있다. int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector arr(n, vector(n)); for (int i = 0; i > arr[i][j]; } } int ans..

https://www.acmicpc.net/problem/24545 24545번: Y 첫째 줄에 트리의 정점 개수를 의미하는 정수 $N$이 주어진다. ($2 \leq N \leq 100\,000$) 둘째 줄부터 $N-1$개 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 $u$, $v$가 주어진다. 이는 $u$번 정 www.acmicpc.net 리쓴 투 마 와....아 SUAPC에서 푼 문제 중 기록해두고 싶은 문제다. 대회 때 내가 1인분을 하는 데 기여해줬다. 대회 중에 더 이상 문제가 안 풀려서 한참 진전이 없었을 때 팀원들과 셋이 의논하면서 솔루션을 도출해냈다. 이야기하다가 내가 문득 트리의 지름이 떠올렸고, 트리의 지름에 있는 노드들을 보면서 리프 노드까지의 개수가 최대인 걸 구하면 되..

https://www.acmicpc.net/problem/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 스위핑 공부하면서 풀었다. 아주 오래전에 세그먼트 트리 공부하면서 풀었는데 오랜만에 다시 푸니까 재밌었다. struct Point { int x, y; }; bool sortby(Point a, Point b) { if (a.x == b.x) { return a.y b.x; } class SegmentTree { public: SegmentTree() {} SegmentTree(int n) { for (base = 1; base < n; base *= 2); tree...

https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 오... 신기하다 스위핑 공부 중 풀이 보고 공부했다. 포인트는 1. x 좌표 기준으로 스위핑, 그러므로 y 좌표에 대한 건 범위와 관계없이 모두 다 저장해둬야 한다. 지금은 범위에 포함되지 않아도 나중에는 포함될 수 있기 때문에. 2. set은 y 좌표 기준으로 오름차순 정렬되어 있으므로, set에 있는 점의 x 좌표가 범위 안에 있는 점인지를 확인하는 게 필요하..

https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 21.05.14 기준 문제 난이도 실버3 난이도는 실버3인게 맞는데 학회 슬랙에 올라온 질문 덕분에 고민을 많이 했다.. 애초에 그 질문 덕분에 문제를 풀게 된 것이긴 하지만 우선 내 풀이는 배열 b를 이용해 배열 a의 내용을 최대한 구하고, 값이 구해지지 않은 부분은 또 구해주는 방법인데 int main() { ios::sync_with_stdio(0); ..

(2021년 3월 4일에 작성한 글입니다.) 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net 처음에는 O(n^2) 풀이밖에 안 떠올랐는데 어떻게 하는거지? 하다가 신촌 연합 캠프 초급 스터디 멘토 할 때 효규가 강의자료 만든 거 보고 그리디구나! 했다 ​ 근데 처음에 제출할 때 틀렸는데, 그 이유는 맨 마지막 결과에 대한 업데이트를 해줘야 하기 때문이다 ​ 예를 들어 5 5 4 3 2 1 이런 인풋이 들어오면 처음에 제출한 코드에서는 답이 0이 될 것이다 ​ 이를 해결하는..

(2021년 2월 24일에 작성한 글입니다) 20927번: Degree Bounded Minimum Spanning Tree 제약에 맞는 Spanning Tree가 존재한다면 첫 번째 줄에 YES를 출력하여라. 이후 해당 Spanning Tree 의 간선을 $N-1$개의 줄에 걸쳐 출력한다. 간선을 출력하는 순서는 상관없으며, 각 간선을 출력할 때는 www.acmicpc.net N, M 크기가 작아서 Brute Force인가? 생각했지만 일단 원래 MST 방법대로 구함 WA ​ 그래서 Brute Force로 짰다 근데 시간초과 났어 그래서 일단 미뤄두고 있다가 효규가 맞왜틀이라고 해서 코드 봤는데 비트마스킹으로 했더라 우왕 ​ 효규가 모든 노드가 하나 이상의 간선과 연결되어 있고 전체 간선 개수가 N-1..

(2021년 1월 24일에 작성한 글입니다.) 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net (20.08.09) c부터 v까지 DFS를 계속 돌면서 체크하도록 했더니 시간초과. 경로가 존재하는지만 확인을 하면 되기 때문에 Union-Find(DST)를 사용하면 훨씬 간단하다!!! 우왕 짱 신기 그리고!! structure를 이용해서 푼 첫 문제인거 같다 아마 짱신기!!!!! 이제 앞으로 벡터 쓸때 pair를 여러개 하지 않아도 된다...ㅋㅋㅋㅋㅋ 앞으로 st..

(2021년 1월 21일에 작성한 글입니다.) 19580번: 마스크가 필요해 첫 번째 줄에는 A도시의 시민 수인 N과 A도시의 상점 수인 M이 주어진다. (1 ≤ N, M ≤ 500,000) 두 번째 줄부터 N + 1번째 줄까지는 A도시의 각 시민이 마스크에 소비할 수 있는 돈의 범위인 Li, Ri가 www.acmicpc.net 20 Summer SUAPC Div 2에서 이 문제 처음 봤는데 범위가 최대 10^18인걸 보고 대회때는 그냥 패쓰했다 그때 당시에는 수 범위가 큰 거는 그냥 패스하자는 마인드가 있었어서 패쓰했는데 ​ 두 달쯤 전에 이거 다시 풀었었는데 잘 모르겠어서 결국 풀이를 봤고, 풀이대로 했는데도 계속 틀려서 미뤄뒀던 문제 ​ 근데 다시 보니까 두 달 전에 틀렸던 이유는 내가 multim..

(2021년 1월 16일에 작성한 글입니다.) 20548번: 칠리소스 용광이는 72칠리 소스를 좋아한다. 용광이는 어떤 칠리 소스를 살지 고민중이다. 이 칠리 소스는 1단계부터 727,272단계까지의 매운맛이 있다. 72칠리 소스는 인하대학교 72호관에 있는 공장에서 제 www.acmicpc.net 문제를 정리하면 가능한 칠리 소스의 맵기를 오름차순으로 나열 한 후 앞에서부터 1단계부터 차례로 번호를 매길 때 내가 고른 소스는 몇 단계인가? 이다. ​ 처음에 메모리 초과로 틀렸는데 int 형을 사용해서 오버플로우가 나와 while문이 계속 돌아서 그랬다. long long으로 바꾸니까 맞았다. ​ chilli 라는 벡터를 만들어줘서 처음에 0을 넣고 n은 1부터 시작해서 매번 7배가 된다. 그리고 기존에..