기록(記錄)

알고리즘

• 백준 문제 풀이 [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억이랑 헷갈려서 잘못된 ..

수학

• 컴퓨터 네트워크 1. Internet Architecture Part 1 이 글은 제가 개인적으로 컴퓨터 네트워크를 공부하기 위해 작성하는 일련의 글들로, 오류 사항이 존재할 수 있으며, 잘못된 개념이 작성될 수도 있습니다. 또한 GPT를 적극적으로 사용하여 글을 작성하고 있으며, 글이 많이 정돈된 형태가 아닙니다. 이 글의 목적은 지극히 저의 공부에 있으며, 누구를 이해시키기 위해 작성하는 글이 아니므로, 참고하시면 좋을 것 같습니다. 혹시 이 글을 읽고 있는 독자 분들이 만약 이 글들에서 오류를 발견한다면, 댓글을 남겨주세요. 글에 반영하도록 하겠습니다.  Q. DARPA Internet Protocol이 뭐야? GPT Says:DARPA Internet Protocol(DARPA IP)는 인터넷의 기본 프로토콜인 TCP/IP(Transmission Control Prot..
• 공부 기록 [조합론] 린드스트롬-게셀-비엔노 보조정리(LGV Lemma) 이 글은 가환환(Commutative Ring)에 관한 설명과 대칭군(Symmetric group)에 대한 설명, 어떤 순열 $\sigma$의 부호 함수, 대합(involution)을 따로 설명하지 않았습니다. 이에 대한 설명은 따로 찾아보시는 것을 권장합니다. Motivation Lindström–Gessel–Viennot Lemma(LGV lemma)의 증명과 적용에 들어가기에 앞서, 간단한 예시를 통해 Motivation을 잡고자 합니다. 다음과 같은 Integer lattice $\mathbb{Z}^2$를 생각해봅시다. $\mathbf{DEF)}$ 정점 $u$에서 정점 $v$로 향하는 북동 격자 경로(North-East Lattice Path)(또는 편의 상 격자 경로(Lattice Path)라고..
• 딥러닝의 수학 [딥러닝의 수학] 5. Stochastic Gradient Descent 2023.08.05 - [수학 공부 기록] - [딥러닝의 수학] 4. Cost, Gradient Descent [딥러닝의 수학] 4. Cost, Gradient Descent 2023.07.31 - [수학 공부 기록] - [딥러닝의 수학] 3. DNN, Forward Pass [딥러닝의 수학] 3. DNN, Forward Pass 2023.07.30 - [수학 공부 기록] - [딥러닝의 수학] 2. Perceptron, MLP [딥러닝의 수학] 2. Perceptron, MLP 2023.07.28 - lighter.tistory.com 딥러닝 시리즈의 다섯 번째 글입니다. 이 글은 고려대학교 수학과 오승상 교수님의 딥러닝 강좌를 참고자료로 하여 쓰임을 밝힙니다. 또한, 이 글의 목적은 이 강좌를 듣고 저..

회고록

감상록