백준 | 11505번. 구간 곱 구하기 - 세그먼트 트리 문풀
⬛ 백준 11505번. 구간 곱 구하기 - 세그먼트 트리 문풀 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다...
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
백준 | 10868번. 최솟값 찾기 2 - 세그먼트 트리 문풀
⬛ 백준 10868번. 최솟값 찾기 2 - 세그먼트 트리 문풀 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
백준 | 2042번. 구간합 구하기 3 - 세그먼트 트리 문풀
⬛ 백준 2042번. 구간합 구하기 3 - 세그먼트 트리 문풀 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 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
트리(Tree) | 세그먼트 트리 Segment Tree (알고리즘) 정리
세그먼트 트리 (Segment Tree) | 인덱스 트리 (Index Tree) 세그먼트 트리 주어진 데이터들의 (구간 합) (데이터 업데이트) 가 함께 일어나거나, (최대, 최소) 를 구할 때 빠르게 수행하도록 고안해낸 자료구조이다. → 더 큰 범위를 ‘인덱스 트리’ 라고 말하기도 한다. [1] 세그먼트 핵심 1) 데이터 초기화하기 a) tree 배열 크기 선언 b) 단말 노드에 arr 원본 배열 초기화 c) setTree로 단말노드 위의 부모노드들을 자식 노드 활용해 세팅 2) 질의값 계산하기 | 구간합, 구간 곱, (구간 안의 최소값, 최대값), 데이터 갱신 등의 질의 질의는 보통 여러 가지가 있는데, 구간 합부터 들어보겠다. 질의값 계산 시에는 원본 idx를 트리의 idx로 맞춰주는 게 중요하다...
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 2. 14.
12회차 데이터베이스 | DB 인덱스(B-Tree, B+Tree, 해쉬테이블), DB 튜닝, DB 다중화 질문 정리
24.02.13 (화) 질문 내용 공유 인덱스에 대해 설명해주세요 RDBMS 에서 Hashtable 이 아닌 B+Tree 를 사용하는 이유 클러스터드 인덱스와 넌클러스터드 인덱스 비교 인덱스를 사용했을 때 유리한 경우 리플리케이션과 클러스터링 비교 DB 튜닝이 무엇인지, 각 단계 설명 관련 질문 정리 ✅ 왜 보편적으로 레드 블랙 트리 대신 B-Tree 자료 구조를 DB 인덱스로 사용하는가? RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터 요소만을 저장하므로 어떠한 요소를 탐색하든 참조 포인터 접근이 필수적이다. 반면, B-Tree는 하나의 노드에 여러 개의 데이터를 저장하므로 각 노드의 데이터 요소를 탐색할 때 참조 포인터 접근 없이 배열의 성질을 이용하여 빠르게 탐색이 가능하다. 결론적으..
- [스터디] CS 기술 면접 준비/CS_데이터베이스 [DataBase]
- · 2024. 2. 13.
12회차 데이터베이스 | DB 인덱스(B-Tree, B+Tree, 해쉬테이블), DB 튜닝, DB 다중화, 내용 정리
DB 인덱스 인덱스 거는이유 인덱스에 왜 해쉬 보다 B Tree를 쓰는지? DB 튜닝 DB 다중화 (클러스터링, 리플리케이션) DB 인덱스 ⬛ DB 인덱스 1) DB 인덱스 개념 원하는 데이터를 빨리 찾기 위해 튜플(행)의 키 값에 대한 물리적 위치 기록해둔 자료구조 주로 테이블의 컬럼을 인덱스로 설정한다. cf. 인덱스가 없는 경우, 테이블의 모든 행을 FUll-Scan하게 된다. (FTS) : Full Table Scan 특정 값 탐색을 위해 모든 데이터, 테이블을 순차 탐색하며 대상을 검색한다면 시간이 오래 걸린다. O(N) → DB 데이터 조회 성능 향상 → ‘인덱스’는 데이터와 데이터 위치를 포함한 자료구조를 생성하여 데이터 탐색 시 빠른 조회를 돕는다. 2) DB 인덱스 관리 (DB 인덱스 관..
- [스터디] CS 기술 면접 준비/CS_데이터베이스 [DataBase]
- · 2024. 2. 12.
트리(Tree) | 트리, 트라이, 이진트리 비교
코딩테스트에서의 Tree 문제 분류 1) 그래프로 푸는 Tree 트리도 특수한 그래프 형태의 하나이기 때문에 노드, 간선 정보가 주어질 수 있다. 이 경우, 인접리스트 형태로 트리를 표현하고, 그에 맞는 그래프 처리 (ex. DFS/BFS) 풀이 2) Tree 만을 위한 문제 보통 1차원 배열로 트리를 표현한다. 이진트리, 세그먼트 트리, LCA(최소 공통 조상) 1. 트리 (Tree) (1) 트리 Tree : 노드-에지로 연결된 그래프의 특수한 형태 (2) 특징 사이클 X, 루트 노드 1개 루트노드 제외한 모든 노드들은 단 1개의 부모 노드만 갖는다. 트리의 부분 트리(=서브트리) 역시 같은 특징을 따른다. (3) 트리의 구성 요소 2. 트라이 (Trie) (1) 트라이 (Trie) ; 문자열 검색 빠..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 2. 9.
11회차 데이터베이스 | 정규화와 역정규화 관련 질문 내용 정리
24.02.06 화 나온 질문 공유정규화 개념, 장단점 설명정규화 : 데이터 일관성, 데이터 중복 최소화를 위해 한 릴레이션이 하나의 의미만 갖도록 릴레이션을 분해하는 과정장점: 데이터베이스에 조작 시 이상현상 문제 해결단점: 릴레이션의 분해로 인해 릴레이션 간의 조인 연산 많아져 질의 응답 시간 느려질 수 있음이상현상 설명이상현상 : 데이터 중복으로 인한 부작용을 말하는데, SELECT시에는 문제가 없어도 데이터 조작 (삽입/삭제/수정) 시 문제가 발생하는 것을 의미한다.1) 삽입 이상 : 튜플 삽입 시 특정 속성에 NULL입력해야 하는 현상2) 삭제 이상 : 튜플 삭제 시 같이 저장된 다른 정보까지 연쇄 삭제 현상3) 수정 이상 : 튜플 수정 시 중복된 데이터의 일부만 수정되어 데이터 일관성 훼손되는..
- [스터디] CS 기술 면접 준비/CS_데이터베이스 [DataBase]
- · 2024. 2. 7.
11회차 데이터베이스 | 정규화와 역정규화 관련 내용 정리
DB 정규화, 비정규화(역정규화) 01. 이상현상 | Anomaly 1. 이상현상의 개념 잘못 설계된 테이블에 데이터 질의 (SELECT) 할 때는 문제가 없는데, 그 외의 데이터 조작 (삽입, 삭제, 수정)을 하면 문제가 발생하는 것을 ‘이상 현상’이라고 말한다. 이상현상이란, 테이블에 튜플 1) 삽입 시 부득이하게 NULL값 입력되거나 2) 삭제 시 연쇄 삭제 현상 발생하거나 3) 수정 시 데이터 일관성 훼손되는 현상 삽입 이상 : 튜플 삽입 시 특정 속성에 해당하는 값이 없어서 NULL 입력해야 하는 현상 삭제 이상 : 튜플 삭제 시 같이 저장된 다른 정보까지 연쇄적으로 삭제되는 현상 수정 이상 : 튜플 수정 시 중복된 데이터의 일부만 수정되어 데이터 일관성 훼손되는 현상 2. 이상현상의 예시 한 ..
- [스터디] CS 기술 면접 준비/CS_데이터베이스 [DataBase]
- · 2024. 2. 5.
10회차 데이터베이스 | 데이터베이스 개요 및 쿼리 관련 질문 정리
24.02.02 (금) 나온 질문 내용 정리데이터베이스 무결성무결성 : 데이터베이스 안에서 유일성을 지키기 위해 할 조건조건개체 무결성 : 릴레이션 내 PK를 구성하는 속성은 NULL값과 중복값을 가질 수 없다.참조 무결성 : FK 값은 NULL이거나 참조테이블의 PK값이어야 한다. 키 무결성 : 한 릴레이션에 하나 이상의 키가 존재해야한다.도메인 무결성 : 속성의 값이 도메인에 속해야한다.RDBMS vs NoSQL 비교하시오.1) NoSQL : 스키마 X. 비정형 데이터. Scale out 가능 - 장점 : 스키마가 없이 Key-Value 형태로 데이터를 자유롭게 관리 O. scale-up + scale-out 가능 - 단점 : 데이터 중복 O. 중복된 데이터 변경 시 수정을 모든 컬렉션에 대해 수행...
- [스터디] CS 기술 면접 준비/CS_데이터베이스 [DataBase]
- · 2024. 2. 2.
10회차 데이터베이스 | 데이터베이스 개요 및 쿼리 내용 정리
데이터 베이스 기본 개념 쿼리 데이터 베이스 기본 개념 1) 데이터베이스 (DB) 개념 일정한 규칙으로 구조화되어 저장된 데이터의 모음 [ 데이터베이스의 특징 ] (4) 1) 실시간 접근성 실시간 처리에 대한 응답 가능 2) 지속적인 변화 데이터베이스 상태가 동적이다.즉, 새 데이터 삽입/삭제/갱신 등 항상 최신의 데이터를 유지한다. 3) 동시 공유 다수의 사용자가 동시에 같은 내용의 데이터 이용 가능 4) 내용에 따른 참조 데이터베이스에 있는 데이터 참조 시 사용자가 요구하는 데이터 내용 기준 찾음 2) 데이터베이스의 종류 (1) 관계형 데이터베이스 | RDBMS : 모든 데이터를 2차원 테이블 형태 (행과 열)로 데이터 저장하는 데이터 베이스 : 테이블 형태로 데이터 관리 : SQL 언어 사용하여 데..
- [스터디] CS 기술 면접 준비/CS_데이터베이스 [DataBase]
- · 2024. 2. 2.
