나다김강니

선형 자료구조선형 자료구조는 연속적으로 데이터가 나열되는 자료구조를 나타낸다. 배열(array)정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조 🔍 용어   요소(element)각각의 데이터   인덱스(index)데이터를 가리키는 번호  🔍 연산   연산설명시간복잡도   접근특정 인덱스에 접근O(1)   검색데이터를 검색O(n)   삽입특정 위치에 데이터 삽입O(n)   삭제데이터 삭제O(n)  연결 리스트(linked list)대표적인 선형 자료구조의 하나로 배열과 달리 크기가 정해져 있지 않은 동적 자료구조이다. 🔍 용어   노드(node)데이터와 다음 노드가 저장된 주소값을 가짐   헤드(head) 포인터첫 번째 노드를 가리킨다.   테일(tail) 포인터마지막 노드를 가리킨다.  🔍 ..

트랜잭션트랜잭션이란 데이터베이스의 상태를 바꾸기 위해 수행하는 작업의 단위 또는 일련의 연산을 의미한다. 트랜잭션의 4가지 특성(ACID)    원자성(Atomicity) 트랜잭션이 데이터베이스에 완전히 반영되거나 아예 실행되지 않아야 한다.    일관성(Consistency)트랜잭션 수행이 완료된 데이터베이스는 일관성이 있다.    독립성(Isolation)수행 중인 트랜잭션에 다른 트랜잭션이 끼어들 수 없다.    영속성(Durability)완료한 트랜잭션의 결과가 데이터베이스에 영구적으로 반영된다.  트랜잭션을 제어하기 위한 명령어(TCL)    COMMIT트랜잭션이 정상적으로 종료되어 데이터베이스에 변경 사항을 반영한다.    ROLLBACK트랜잭션이 비정상적으로 종료되어 트랜잭션이 수행한 변경..

11689 : GCD(n, k)문제자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.입력출력11544524 문제 풀이오일러피로 푸는 문젠데 강의에 나온 이론으로 풀면 자꾸 런타임에러나는거;; 💡 오일러 피 구하는 다른 방법 - 소인수분해 사용 N 에서 소인수를 찾아내고 𝝓(n) 값을 갱신한다.소인수의 배수를 제거하여 N을 점점 작게 만든다.N이 소수로 남아잇다면, 𝝓(n) 값을 최종적으로 갱신한다.(예시)N = 36, res = 36소인수 확인 및 처리(N%i==0 확인, N..

세그먼트 트리주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조이다.더 큰 범위로 '인덱스 트리'라고 불린다. 💡 세그먼트 트리의 핵심 이론세그먼트 트리의 종류는 구간 합, 최대 · 최소 구하기로 나눌 수 있다. 1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N)이상이 되도록 트리 배열을 만든다.트리 배열 크기 구하기 : 2k ≥ N을 만족하는 k의 최솟값을 구하고 2k x 2를 트리 배열의 크기로 정의한다.그리고 주어진 데이터들을 2k에 해당하는 인덱스부터 채운다. 만약, 8개의 데이터가 주어졌을 때는 {5, 8, 4, 3, 7, 2, 1, 6}2의 제곱수 중 처음으로 8보다 크거나 같아지는 제곱수를 구한다 -> k=3배열의 크기는 23 x 2 = 16배열을 채..

TCPTCP는 전송 계층에 해당하는 네트워크 프로토콜로, 연결형 서비스를 지원하고 데이터의 신뢰성을 보장한다.송신부와 수신부의 연결을 확인하는 연결형 서비스패킷 교환 방식 : 패킷이 전달되는 회선이 정해져 있는 가상 회선 방식패킷 전송 순서가 보장된다.패킷의 수신 여부를 확인한다.송신부와 수신부가 1 : 1 통신을 한다.데이터 손실이 없음을 보장하므로 신뢰성이 높다.느리다☝🏻 패킷 교환 방식 2가지· 가상 회선 방식데이터를 주고받기 전에 패킷을 전송할 경로인 가상 회선을 설정해서 모든 패킷을 같은 경로로 전송 · 데이터그램 방식패킷마다 최적의 경로로 전송한다. 때문에 송신부에서 보낸 패킷 순서와 수신부에서 받는 패킷의 순서가 다를 수 있다. TCP 핸드셰이킹TCP에서는 연결형 서비스를 지원하기에 송신부..

플로이드-워셜그래프에서 최단 거리를 구하는 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)모든 노드 간에 최단 경로 탐색 -> 시작 노드가 따로 정해져있지 않다.음수 가중치 에지가 있어도 수행 가능하다. 다만, 사이클이 있으면 안된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.시간 복잡도는 O(V3)   노드가 1000개이면 시간초과가 일어날 확률이 높다.💡  플로이드-워셜 핵심 이론A노드에서 B노드까지 최단 경로를 구했다고 가졍했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로 🔍 도출한 플로이드-워셜 점화식     D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 1. 리스트를 선언하고 초기화하기D[S][E]는 노드 S에서..

1.2.1 프로세스와 스레드프로세스  컴퓨터에서 실행 중인 하나의 프로그램을 의미프로그램은 특정 작업을 수행하기 위한 명령어의 집합OS는 프로그램을 실행하면서 디스크에 저장된 데이터를 메모리로 로드한다.프로세스는 독립된 메모리 영역을 할당받고, 다른 프로세스의 메모리 영역에는 접근 불가능하다. 💡  프로세스의 메모리 영역 구조스택(stack)지역변수, 함수의 매개 변수, 반환되는 주소 값 등이 저장되는 영역영역 크기는 컴파일 때 결정된다.LIFO(후입선출) : 높은 주소 값에서 낮은 주소 값으로 메모리가 할당힙(heap)사용자에 의해 동적 메모리 할당이 일어나는 영역영역 크기는 런타임 때 결정된다.FIFO(선입선출) : 낮은 주소 값에서 높은 주소값으로 메모리가 할당데이터(data)전역 변수, 정적 변..

위상 정렬위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.사이클이 없어야한다.시간복잡도는 O(V+E)항상 유일한 값으로 정렬되지 않는다.💡  위상 정렬의 원리 이해하기1. 진입 차수 배열을 만들어준다.    진입 차수는 자기 자신을 가리키는 에지의 개수이다.    예를 들어 첫번째 리스트를 보면 D[2]++, D[3]++ 계산을 할 수 있다. 2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택한 보드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺀다.0인 노드를 선택할 때 3을 먼저 선택할 수도 2를 먼저 선택할 수도 있다. 이러한 이유로 위상정렬은 유일한 값으로 정렬되지 않는 것이다.    2252 : 줄 세우기..

소수 구하기소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수.1과 자기 자신 외에 약수가 존재하지 않는 수! 💡  소수 구하기의 핵심 이론 - 에라토스테네스의 체 원리구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.2부터 시작하고 현재 숫자가 지원지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.배열의 끝까지 2를 반복한 후 배열에서 남아있는 모든 수를 출력한다.☝🏻 에라토스테네스의 체 원리의 시간복잡도는 최적화의 정도에 따라 다르지만 일반적으로 O(Nlog(logN))이다! 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다!!  192..

이진탐색(Binary Search)데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.시간복잡도  O(logN)💡  이진 탐색의 핵심 이론 1. 현재 데이터셋의 중앙값을 선택한다. 2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 3. 중앙값  4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.☝🏻 이진 탐색을 사용하면 N개의 데이터에서 데이터를 반씩 줄여가며 탐색하기 때문에 총 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.  1920 : 수 찾기문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라..