최선을다하는

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 N(2 ≤ N ≤ 50,000) 개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그다음 줄..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 수 N개 A1, A2,..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j)의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느 날 커피숍의 손님 A 씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그..

SWEA의 5번째 내용은 그래프 탐색에 관한 내용이었다. 그래프 탐색에는 여러 가지 이론들이 있지만 강의에서는 대표적인 DFS와 BFS에 관한 내용이 나왔다. 강의는 너무 쉬운 내용이라 금방 넘겼고 바로 문제 풀이에 들어갔다. 기초 DFS와 BFS라는 제목을 가진 문제 두 개를 풀었는데 DFS와 BFS를 활용하는 문제였는데 문제가 굉장히 불친절했다. 입력값도 트리를 파악할 수 없게 만들어 직접 출력해보아야 했고 입력값에 쓰레기 값도 들어있어서 문제 풀이에 굉장히 난항이 있었다. BFS 문제는 그보다 나았지만 행과 열 순서로 주지 않고 열 과 행 순서로 좌표를 주고 인덱스는 (0,0)부터 주지만 실제 좌표는 (1,1)부터 시작하여 굉장히 혼란스러웠다. 그리고 난 후 기본문제를 풀기 시작했는데 프로세서 연결..

https://www.acmicpc.net/problem/1091 1091번: 카드 섞기 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0 www.acmicpc.net 문제 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있..

https://www.acmicpc.net/problem/24041 24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net 문제 인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다! 이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고..

이번 내용은 분할 정복에 관한 내용이었다. 분할 정복의 대표적인 문제로 머지 소트, 퀵 소트, 그리고 이진 탐색을 공부하였다. 특별히 어려운 내용은 없었다. 저번 학기에 알고리즘 수업에서 되게 자세히 배운 내용이라 친숙하였다. 대부분의 내용이 수업 때 배운 내용보다 깊지 않은 내용이었는데 임인성 교수님이 굉장히 잘 가르쳐 주시고 시험 문제도 시간 복잡도와 다양한 코드를 접할 수 있게 출제하셔서인지 기본적인 알고리즘에 대한 이해도가 굉장히 높아졌다는 것을 느낄 수 있었다! 주어진 문제를 보니 바로 vector를 이용한 쉬운 풀이와 오늘 배운 분할정복으로 직접 정렬하여 문제를 풀 수 있겠다. 하지만 두 문제 다 50개의 테스트 케이스 중 0개 성공, 즉 다 실패해버렸다. 2시간을 고민하고 답을 뒤지던 중 정..

https://www.acmicpc.net/problem/24268 24268번: 2022는 무엇이 특별할까? 백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다. 그렇 www.acmicpc.net 백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다. 그렇다. 2022를 5진법으로 표현하면 31042(5)로, 5진법의 각 숫자인 0, 1, 2, 3, 4가 모두 한 번씩 나타난다. 다음에 이런 년도가 오..

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 문제 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들..

3번째 강의는 그리디, 완전 탐색, DP에 관한 내용이었다. 대부분은 친숙한 내용이었지만 visited를 비트 마스킹으로 배열이 아닌 int로 사용한다는 것이 신기했다. 이러한 비트 연산을 통해 재귀와 DP를 같이 사용할 때에도 [N][1