Joonas' Note

링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_문제경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.항상 위쪽 또는 왼쪽까지 도착..

이진 트리 중에서도 힙.힙 중에서도 최소힙을 구현한 코드C++에서 대소비교에 기본값인 less than(

문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 문자열을 정수형 변수 하나에 담는 것을 말합니다.왜?보통 해싱은 작은 크기로 우겨넣기 때문에 데이터 손실이 일어나는 형태가 많습니다. 그래서 그대로 저장하면 충돌 해결 이슈가 따라오죠. (resolving collisions in hash tables) 정수로 바꾸어서 다룬다면 문자열 비교를 길이만큼인 \(O(|s|)\) 가 아닌 정수 비교 시간인 \(O(1)\) 으로 줄일 수 있습니다. 조건만 가능하다면 데이터의 손실 없이 그대로 담을 수도 있죠.26진법소문자 26개 혹은 대문자 26개만 사용하..

2018년 말에, Semantic-UI 에서 제공하는 progress bar를 살짝 바꾸어서 CSS의 overflow: hidden 속성으로 무한 로딩을 구현한 적이 있다. https://jsfiddle.net/J00nas/xpvt214o/970756/ 위 링크에서도 동작하는 모습을 볼 수 있다. 기존의 progess bar의 인터페이스는 그대로 유지하고 기능만 추가하였기에, 코드도 나름 깔끔한 편이다. 문제는 기존에 제공되는 placement text는 안된다. 당시에 이걸 유지해보려고 많은 삽질을 해봤다가 실패했다. 사실 이 기능은 Semantic-UI에 PR을 날렸으나 무산되었다. [Progress] Add properties for infinite loop as loader style #6691(..

성능 테스트 코드를 작성하다가, 평균을 실시간으로 구하는 방법을 글로 정리해볼까 한다. (직관으로) 어렸을 적에 이게 당연한 줄 알았다. 근데 몇개의 반례를 찾고는 틀렸다고 생각했다. 그런데 학부 시절에 교수님께서 '그런 것이 있다'고 말씀해주셨다. 이름은 Moving average이고, 한국어로는 모르겠다. 나는 데이터 범위에 따라 점진적으로 평균을 구해간다는 느낌으로 점진적 평균 또는 실시간 평균으로 부르고 싶지만, 통계쪽에서 "이동 평균"으로 부르는 모양이다. 아무튼, 본디 평균을 구하는 식은 전체 합 \(S_n\)에서 데이터의 개수 \(n\)만큼 나눈 \(S_{n} / n\) 이다.그럼 이것이 뭐가 문제인가?\(n\)개를 전부 더하거나 카운팅 하지 않으면 평균을 구할 수 없다. 어떤 실험 \(X_..

시험 직전에 벼락치기 겸 수업 내용을 전부 정리하는 게 꽤 좋았다.정리를 하다가 예상 문제가 떠오르기도 한다. 근데, 전에 파일구조도 그렇고 이것도 반쪽짜리다. (기말고사 범위만 정리함)문서 정리하다가 우연히 아이폰에서 발견했는데, 아까워서 올려본다.목차09. Digital Signature Digital Signatures Security Model Signature Schemes RSA ElGamal DSA 10. Hash functions and Message Authentication Codes Hash function SHA Message Authentication Codes (MAC) 11. User Authentication User Authentication Password-based au..

2014년부터 2019년까지 내가 github을 사용했던 흔적들을 모두 모아봤다.여기서 초록색(흔히 말하는 잔디)은 이 문서(GIthub - Learn how we count contributions)를 기준으로 색칠된다.어떤 레포지토리에 이슈를 적은 것, Pull Request 한 것, commit 한 것, 심지어는 start를 누른 것도 포함되는 것 같다.이렇게 모아서 보니 패턴이 없는 듯 있는 것 같기도 하고.. 사실, Github을 사용한 이유는 개인 데스크탑이 없어서 컴퓨터를 자주 옮기다보니까 저장소로만 사용했는데, 조금 더 지나서야 버전 관리를 이유로 사용할 수 있었다. 한참 더 지나서야 issue, PR 까지 사용했지만 이렇게 보니 생각보다 꾸준히 개발했나보다.