병합 정렬의 개념 병합 정렬이란? 하나의 리스트를 두 개의 균등한 크기로 최대한 분할하고 분할된 부분 리스트를 순서대로 합하는 방식이다. 분할된 리스트를 순서대로 합쳐서 담기 위한 자료구조가 추가적으로 필요하다. 가장 작은 단위로 절반씩 쪼갠 후 가장 작은 단위부터 다시 합쳐나가는데 이 합쳐나가는 과정에서 데이터가 정렬이 된다. Divide and Conquer Merge Sort의 해결 전략 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 Divide and Conquer 방식은 대개 재귀 호출을 이용하여 구현함 동작 방식과 구현 1. 데이터들을 절반으로 나눈다. (분할) 2. 데이터를 가장 작은 단위로 분해한 후 맨 밑에서 부터 차례대로 합병을 진행..

다익스트라 알고리즘의 개념 다익스트라 알고리즘이란? 하나의 정점에서 모든 정점으로의 최단 경로를 계산하는 것을 목표로 하는 알고리즘 Single source shortest paths problem 로직 모든 정점들은 처음에 무한대 값을 갖는다. 정점 A에서 정점 B가 이어지면 정점 A까지의 최단거리 + A에서 B까지의 거리를 계산한다. 만약 B가 가지고 있는 값(즉, A에서 B로 이어지는 다른 경로에 의한 값)과 2번에서 계산한 값과 비교하여 후자가 더 작다면 갱신한다. 가장 작은 값을 가지고 있는 정점부터 이어서 반복한다. (가장 작은 값을 가지고 있는 정점부터 시작하는 이유는 작지 않은 값부터 시작되면 쓸모없는 연산이 진행되기 때문이며, 올바른 결과를 얻어낼 수 없다.) 작은 값으로 갱신이 되어야 ..

버블 정렬의 개념 버블 정렬이란? 서로 인접한 두 원소의 대소를 비교하고, 두 원소의 위치가 바뀌어야 한다면 자리를 교환하며 정렬하는 알고리즘이다. 선택 정렬과 기본 개념이 유사하지만, 버블정렬은 선택정렬과 다르게 SWAP이 계속적으로 일어난다. 버블 정렬의 동작 방식과 구현 동작 방식 1. n-1개의 데이터의 위치만 찾으면 되므로 n-1번 반복한다. (n-1개의 데이터의 위치가 정해지면 나머지 1개는 자동 정렬) 1-1. 앞에서부터 버블처럼 올라가며 2개의 데이터씩 짝지어 비교한다. 1-1-1. 2개의 데이터를 비교하여 위치가 바뀌어야 한다면 SWAP한다. 1번을 한번 반복할 때마다 정렬되지 않은 데이터들 중 가장 큰 값이 뒤로 이동한다. (즉, 반복 한번 당 하나의 데이터가 무조건 정렬됨) 구현 fo..

선택 정렬의 개념 선택 정렬이란? 넣을 위치는 이미 정해져 있고, 그 위치에 어떠한 데이터를 넣을지 선택하는 알고리즘이다. 동작 방식 1. 리스트 길이(n)의 -1 만큼 반복한다. (앞에서부터 위치를 정하게 되면 마지막 값은 자동으로 위치가 정해진다) 1-2. 선택된 최솟값과 최솟값이 들어갈 위치의 값과 교체한다. 1-1. 값이 들어갈 위치부터 마지막 값까지 최솟값을 찾는다. void sort() { int min; // 1. 값이 들어갈 위치를 선택하는 반복문 for(int i=0; i

트랜잭션 트랜잭션이란? 데이터베이스의 상태를 변화(SQL 질의어 사용)시키기 위해 수행하는 작업 단위 작업 단위는 SQL 명령문들로 이루어져 있으며 개발자가 정하는 기준에 따라 다름 예시) 회원 정보 수정 저장 버튼 클릭 : UPDATE문을 이용하여 사용자 정보 수정 회원 정보 구성 : SELECT문을 이용하여 사용자 정보 최신 유지 작업 단위 : UPDATE + SELECT 트랜잭션 특징 원자성 : DB에 모두 반영되거나, 아예 반영되지 않거나 일관성 : 작업 처리 결과는 늘 같아야함 독립성 : 트랜잭션의 연산에 다른 트랜잭션이 끼어들 수 없음 지속성 : 트랜잭션이 성공적으로 완료되었다면, 그 결과는 영구적이여야함 Commit과 Rollback Commit : 하나의 트랜잭션이 완료되었으며, DB가 일..