좌표들이 주어질때 좌표간 간격이 될 수 있는 모든 수를 찾는 방법

30105번: 아즈버의 이빨 자국 (acmicpc.net) 초코바에 이빨 자국을 남기는데 이빨간 간격이 k라고 한다면 0이상의 수 x에 대하여 x부터 x+k에 이빨 자국을 남긴다 이빨자국을 동일한 위치에 여러번 남겨도 한번만 보인다 이빨자국이 남겨진 좌표들 x0,x1,x2,...,xn이 주어진다면 가능한 k를 모두 구해본다면?  1. 무식하게 찾는 방법 쉽게 생각할 수 있는 방법은.. 일단 모든 좌표쌍 (xi,xj)에 대하여 간격 k = xj - xi를 구하고 간격 k에 대응하는 xi,xj를 저장해둔다 모든 간격 k에 대하여 간격 k에 대응하는 x좌표가 주어진 이빨 자국 수와 같다면 해당 간격 k는 가능한 k라는 것 예를 들어 [0,5,10,15]로 주어질때 모든 쌍에 대하여 5-0 = 5이므로 h[5]..

• format_list_bulleted 알고리즘/브루트포스
• · 2024. 9. 24.
• textsms

Python dict indexing보다는 list indexing을 사용해야하는 이유

dict에서 key에 접근하는 시간과 list에서 index로 접근하는 시간은 O(1)인데, dict의 경우 hash로 구현되어 있어서 key,value가 많은 경우 hash collision으로 인해 list indexing보다 시간이 더 걸릴 수 있다. 만약 시간초과 판정을 받는다면 dict indexing을 list indexing으로 바꿀 수 있는지 체크해보자. https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기 String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming..

• format_list_bulleted 알고리즘/알고리즘 일반
• · 2024. 4. 12.
• textsms

ABC 344 E번 복기 - 원소에 바로 접근할 수 있는 연결리스트 구현하는 법

E - Insert or Erase (atcoder.jp) E - Insert or Erase AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 수열 A의 원소들이 모두 서로 다른 원소이며, 삽입하는 연산과 삭제하는 연산을 수행한다. 연산을 수행할 때마다 A의 원소들은 모두 서로 다르다는 것이 보장된다. 연산은 2가지이다. x 원소 바로 뒤에 y를 삽입하는 연산 x를 삭제하는 연산 연결리스트로 접근해야지 생각하긴 했는데... x를 어떻게 바로 찾아야 하나 고민하다가 실패했다.. 연결리스트는 접근하는데 O(N)이라서.. 분명..

• format_list_bulleted 알고리즘/연결리스트
• · 2024. 3. 14.
• textsms

값 압축(value compression) 기본 문제로 연습

1. 문제 18869번: 멀티버스 Ⅱ (acmicpc.net) 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 2. 풀이 문제 이해하는것부터 쉽지 않았다 m개의 줄마다 리스트 A를 입력받아서 전체 리스트 universe에 저장해두고, universe에서 i,j 2개를 선택해서, (i universe[j][b]를 만족해야한다. -----..

• format_list_bulleted 알고리즘/압축 알고리즘
• · 2023. 4. 28.
• textsms

react&node.js 개발 - 로그인하면서 JWT 토큰 발급받고 유저 정보 알아내기

1. 비밀 키 생성 백엔드에 config.js 파일 작성 다음과 같이 secret key를 작성 JWT 토큰 검증시 해싱에서 사용할 키라고함 //backend//config.js //jwt verification secret key module.exports = { 'secret':'대혁이다' } 2. 서버에 secret key 세팅 서버에 작성한 config 파일을 불러오고 secret key를 다음과 같이 세팅 //backend/server.js // set the secret key variable for jwt const config = require('./config') app.set('jwt-secret', config.secret) 3. 로그인 api 작성 $npm install jsonwe..

• format_list_bulleted 프로그래밍/node.js
• · 2023. 1. 22.
• textsms