전체 글
-
체비쇼프 거리알고리즘/Algorithm Theory 2024. 3. 24. 19:44
체비쇼프 거리 Chebyshev Distance 유클리드 거리와, 맨허튼 거리 외에도 체비쇼프 거리라는 것이 있다. 솔직히 특별한 거리는 아니고, 맨허튼 거리가 8 방향에 대해 적용되는 것이라고 보면된다. 노랑색 칸 부터 다른 칸들에 대해 체비쇼프 거리를 나타내면 다음과 같다. Flood Fill(BFS) 를 8 방향으로 돌려 얻거나, 격자의 좌표의 차이의 최대 값이 거리가 된다. strcut yx{ int y, x }; yx a, b; int distance = max(abs(a.x - b.x), abs(a.y - b.y)); https://www.acmicpc.net/problem/28452(체비쇼프 거리를 활용한 시뮬레이션 문제) 28452번: 탄막 게임 두 점 $A(x_1, y_1)$과 $B(x_..
-
라빈-카프, 접미사 배열, lcp 배열알고리즘/Algorithm Theory 2024. 3. 24. 04:40
- Hash(string to int) https://blog.joonas.io/143 문자열을 정수로 해싱하기 + 사전순 비교까지 (String to unique integer hashing) 문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 blog.joonas.io - RabinKarp https://junstar92.tistory.com/125 Rabin-karp(라빈 카프) 알고리즘 두번째로 살펴볼 문자열 탐색 알고리즘은 Rabin-Karp 입니다. 라빈카프 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾..
-
세그먼트 트리 시리즈알고리즘/백준 2024. 3. 13. 14:22
각 구간에 대해 특정 해를 항상 가지고 있는 트리. 자료구조로 생각하고 풀이하면 편하다. 각 구간 ~ 에 대해 최소값/최대값/합/곱 ... 을 가지는 트리 - 구간 합 (기본) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net - 최대 최소 값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을..
-
세그먼트 트리 (Segment Tree)알고리즘/Algorithm Theory 2024. 3. 12. 13:48
- 일반적인 구간 합 계산 int arr[5] = {3, 2, 1, 5, 4}; arr에서의 2번째에서 4번째까지의 합 : 2 + 1 + 5 = 8 배열의 길이가 N 일 때, 일반적인 구간 합 계산으로는 O(N)의 시간 복잡도를 가진다. 만약 N의 길이가 조금만 커져도 해당 연산을 반복하게 되면, 매우 오랜 시간을 필요로 하게 된다.. 해당 경우, 세그먼트 트리를 사용하여, O(logN)의 시간 복잡도로 구간 합을 구할 수 있다. - 세그먼트 트리 해당 배열을 세그먼트 트리로 나타내면 아래와 같다. 트리는 노드는 9 개, 높이는 3인 이진트리 형태를 가진다. 루트 노드 : 총 합(전체 배열의 합) 리프 노드 : 배열의 각 원소 값 트리의 높이 : math.ceil(log2(N)) //ceil은 올림 함수..
-
[Vue] Components & pinia 실습공부/Vue 2024. 3. 11. 10:46
각 페이지는 여러개의 컴포넌트들로 나눌 수 있음 /components 에 자식 파일 생성 - HomeView.vue Home count: {{userInfoStore.age }} 나이를 줄이자 - HomeChild.vue HomeChild {{ userInfoStore.name }} 이름 변경 - GrandChild.vue GrandChild 한살로 돌아가자 - /stores/counter.js import { ref, computed } from 'vue' import { defineStore } from 'pinia' export const useUserInfoStore = defineStore('userStore', ()=>{ const name = ref("테스트"); const age = ref..
-
[Vue] Day - 1공부/Vue 2024. 3. 6. 14:25
뷰 프로젝트 생성 프론트 서버 실행 cd vue-project npm install npm run dev Chorme 확장 프로그램 veu.js 장점 html에서 변수, 조건문, 반복문 사용 가능 화면 변경사항에 대해 즉각 변경 화면의 각 부분을 컴포넌트 단위로 나눠서 개발 프론트와 백이 서로 다른 프로젝트로 분리되어 통신 단점: 최초 로딩속도가 느림, SEO 검색엔진 최적화 불편 > 단점극복을 위해 SSR 프레임워크인 Nuxt 사용 컴포넌트 .vue확장자가 붙은 파일 총 3 개의 영역, js html css {{}} mustache vue : ref 선언한 변수는 쓸 때 .value를 붙여줘야 함 : .value를 붙이면 에러 v-modal : 양방향 바인딩 는 데이터 변경 가능 v-bind : 단방향..
-
[Algorithm] MST, Minimun Spanning Tree알고리즘/Algorithm Theory 2024. 2. 21. 10:38
- MST : 그래프의 모든 정점을 연결하는 최소 비용 트리 1) Kruskal 크루스칼 - 간선들을 가중치를 기준으로 오름차순 정렬 - 사이클이 생기지 않는 간선을 (정점의 개수 - 1) 개 만큼 뽑아냄 2) Prim 프림 - 최소 힙을 사용하여, 각 정점으로 부터 최소 간선을 선택해나감 - 크루스칼 알고리즘 - 크루스칼 구현 #include #include #include using namespace std; int N = 5; struct Node { int a, b; int price; }; vector line; int arr[10]; bool compare(Node t, Node v) { return t.price < v.price; } void Init() { for (int i = 0; i..