기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [Python] 2533번 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 24/03/30 예전에 해결했던 문제인데, 복습하는 겸 글을 적어본다. 문제 접근 방식: 문제의 요구사항은 트리가 주어질 때 얼리 어답터의 수를 최소화하는 문제다. 얼리 어답터가 아닌 사람들은 주변의 모든 사람들이 얼리어답터인 경우에 아이디어를 수용한다. 목표는 모든 사람이 아이디어를 수용하도록 하고 싶을 때, 얼리 어답터의 수를 최소화하는 것이다. 전형적인 트리 DP로 해결할 수 있는데, 다음과 같이 DP테이블을 정의하자. $DP[i][0]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$번째 노드가 얼리 어답터가 아닐 때 서브 트리 전체의 최소 얼리 어답터 수$DP[i][1]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$..
백준 문제 풀이 [C++] 7118번 Ones https://www.acmicpc.net/problem/7118 25/02/26 예전에 문제를 보고 잘 안풀려서 북마크에 넣어두고 나중에 풀어봐야지 했던 문제인데, 오랜만에 다시 꺼내서 태그를 까고 해결했다. 지수승강 보조정리(LTE Lemma)의 기초를 배울 수 있었던 좋은 문제였다. 문제 접근 방식: 문제는 다음과 같다. $a = \underbrace{111 \ \dots \ 111_{(t)}}_{n}$ $n$개의 $1$로 구성된 $t$진수로 표현된 수 $a$가 주어진다고 하자.이때, $2^{u}, 3^{v}$가 각각 $a$를 나눈다고 하면 그때의 $u$와 $v$의 최댓값을 구하자. $t$와 $n$의 제한은 각각 $10^9$임을 생각해보면, 나이브하게 곱하면 숫자가 너무 커질 것이라는 생각이 들..
SWEA [C++] 5658번 [모의 SW 역량테스트] 보물상자 비밀번호 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo 25/02/07 16진수 변환을 곁들인 귀찮은 구현문제다. 문제 접근 방식: 주어진 숫자들이 16진수로 주어진 수들이기 때문에, 16진수로 주어진 수를 10진수로 변경하는 함수를 구현하는 것이 핵심이다. 이 문제에서 유의할 점은, 범위가 int범위를 넘어갈 수도 있다는 점이다. $N$이 최대 28까지이고, 그 말은 최악의 경우 FFFFFFF라는 16진수 수를 10진수로 변경해야하는 일이 있을 수 있다. 실제로 10진수로 변경해보면 int범위를 조금 넘어가기 때문에 long long으로 받아야 한다.(2억이랑 21억이랑 헷갈려서 잘못된 ..

수학

회고록

감상록

티스토리툴바