분류 전체보기

1.  이진 탐색이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘입니다. 이진탐색 알고리즘은 리스트 내 데이터가 어느 정도 정렬되어 있어야만 사용 가능하며 데이터가 무작위로 정렬되어 있다면 사용할 수 없습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g., 1,000억 이상) 효과적으로 문제를 해결할 수 있습니다.2.  이진 탐색의 동작 과정이진 탐색은 특정 데이터를 찾기 위해 리스트 내 기준점으로서 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용합니다.  이진 탐색의 동작 순서는 아래와 같습니다. 1️⃣ 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정합니다.2️⃣ 중간 ..

플로이드 워셜플로이드 워셜 알고리즘을 쓰는 문제의 경우, 노드의 개수가 500개 이하일 경우가 많다.하지만 노드가 500개라고 해도 500 * 500 * 500 은 1억이 넘어가기 때문에 시간제한이 넉넉하지 않다면 시간초과에 걸릴 수도 있다.1. 플로이드 워셜 알고리즘 개요모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.2. 플로이드 워셜 알..

최단 경로 문제최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. cf. 다양한 문제 상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현한다.지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 방향그래프 예시 1. 다익스트라 최단 경로 알고리즘 개요특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. 2..

DP 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있다.중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결한다. DP 예시대표적인 문제로는 피보나치 수열이 있다.(cf. 점화식: 인접항들의 관계식을 의미한다.)// 피보나치 수열1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...  * 피보나치 수열의 점화식  단순 재귀를 통한 피보나치 수열 구현* [Python] 단순 재귀를 통한 피보나치 수열# 피보나치 함수를 재귀함수로 구현def fibo(x): if x == 1 or x == 2: return 1 return fib..

알고리즘을 풀면서 문제를 맞추어도 효율이 안좋은 경우가 종종 있다.시간복잡도를 최대한 줄여 효율을 끌어올려야 겠다고 생각이 들어 시간복잡도를 정리해본다.삽입(insert,pop), 제거(delete, remove) , 탐색(check ==,≠) 포함여부 확인( containment(in, not in))의 경우 List는 전부 O(N)이다. Set,Dict은 O(1)혹은 O(len)의 시간을 가지고 있다.-> 삽입,삭제,탐색,포함여부 확인등의 문제는 list보다 set,dict을 사용하는게 효율면에서 뛰어나다고 생각한다. List SetDictionary

보안비인가자가 데이터베이스에 침입하여 데이터를 유출하거나 손상한다면 조직에 치명적인 손실이 발생함인가자만 데이터베이스에 접근할 수 있도록 통제하여 보안을 유지하는 일이 무척 중요보안의 유형물리적 환경에 대한 보안 - 자연 재해 등으로부터 보호권한 관리를 통한 보안 - 권한이 없는 사용자로부터 보호운영 관리를 통한 보안 - 권한이 있는 사용자로부터 보호권한 관리DBMS는 보안을 유지하기 위해, 계정이 발급된 사용자가 로그인에 성공했을 경우에만 데이터베이스에 접근이 가능하도록 하는 접근 제어(access control)기능을 기본으로 제공계정을 생성, 변경, 제거하는 사용자 계정 관리는 DBA가 담당데이터베이스에 존재하는 모든 객체는 기본적으로 해당 객체를 생성한 사용자만 사용 권한을 지님필요에 따라 공유할..

회복과 병행 제어DBMS는 데이터베이스가 항상 정확하고 일관된 상태를 유지할 수 있도록 하는데, 그 중심에는 트랜잭션이 있음트랜잭션을 관리함으로써 데이터베이스의 회복과 병행 제어가 가능트랜잭션(transaction)하나의 작업을 수행하는 데 필요한 데이터베이스의 연산들을 모아놓은 것데이터베이스에서 논리적인 작업의 단위 (데이터베이스에 장애가 발생했을 때 데이터를 복구하는 작업의 단위)트랜잭션의 모든 명령문이 완벽하게 처리되거나 하나도 처리되지 않아야 데이터베이스가 모순이 없는 일관된 상태를 유지할 수 있음데이터베이스의 무결성과 일관성을 보장하려면 필요한 연산들을 하나의 트랜잭션으로 제대로 정의하고 관리해야 함일반적으로 데이터베이스를 변경하는 INSERT문, DELETE문, UPDATE문의 실행을 트랜잭션..

정규화의 개념과 이상 현상정규화(normalization)데이터베이스를 잘못 설계하면 데이터의 삽입, 수정, 삭제 연산을 수행할 때 부작용(이상현상 (anomaly))이 발생정규화는 이상 현상이 발생하지 않도록 릴레이션을 분해(decomposition)하는 과정을 의미데이터베이스를 설계한 후 설계 결과물을 검증하기 위해 사용하기도 함이상 현상의 종류삽입 이상(insertion anomaly) - 새 데이터를 삽입하기 위해 불필요한 데이터도 함께 삽입해야 하는 문제갱신 이상(update anomaly) - 중복 투플 중 일부만 변경되어 데이터가 불일치하게 되는 모순의 문제삭제 이상(deletion anomaly) - 투플을 삭제하면 필요한 다른 데이터까지 함께 삭제되는 데이터 손실의 문제정규화의 필요성관련..