초코chip의 코딩 생활

알고리즘최적 시간평균 시간최악 시간제자리 정렬안정 정렬거품 정렬O(n)O(n²)O(n²)OO선택 정렬O(n²)O(n²)O(n²)OX삽입 정렬O(n)O(n²)O(n²)OO퀵 정렬O(n log n)O(n log n)O(n²)OX병합 정렬O(n log n)O(n log n)O(n log n)XO힙 정렬O(n log n)O(n log n)O(n log n)OX기수 정렬O(nk)O(nk)O(nk)XO계수 정렬O(n + k)O(n + k)O(n + k)XO In-place & Stable Sort제자리 정렬(in-place sorting): 추가적인 메모리 공간을 거의 사용하지 않고, 입력 배열 자체에서 정렬을 수행하는 알고리즘을 의미O(1) 또는 O(log n) 정도의 보조 메모리만 사용하며, 기존 데이터를 재배..

알고리즘최적 시간평균 시간최악 시간제자리 정렬안정 정렬거품 정렬O(n)O(n²)O(n²)OO선택 정렬O(n²)O(n²)O(n²)OX삽입 정렬O(n)O(n²)O(n²)OO퀵 정렬O(n log n)O(n log n)O(n²)OX병합 정렬O(n log n)O(n log n)O(n log n)XO힙 정렬O(n log n)O(n log n)O(n log n)OX기수 정렬O(nk)O(nk)O(nk)XO계수 정렬O(n + k)O(n + k)O(n + k)XO In-place & Stable Sort제자리 정렬(in-place sorting): 추가적인 메모리 공간을 거의 사용하지 않고, 입력 배열 자체에서 정렬을 수행하는 알고리즘을 의미O(1) 또는 O(log n) 정도의 보조 메모리만 사용하며, 기존 데이터를 재배..

알고리즘최적 시간평균 시간최악 시간제자리 정렬안정 정렬거품 정렬O(n)O(n²)O(n²)OO선택 정렬O(n²)O(n²)O(n²)OX삽입 정렬O(n)O(n²)O(n²)OO퀵 정렬O(n log n)O(n log n)O(n²)OX병합 정렬O(n log n)O(n log n)O(n log n)XO힙 정렬O(n log n)O(n log n)O(n log n)OX기수 정렬O(nk)O(nk)O(nk)XO계수 정렬O(n + k)O(n + k)O(n + k)XO In-place & Stable Sort제자리 정렬(in-place sorting): 추가적인 메모리 공간을 거의 사용하지 않고, 입력 배열 자체에서 정렬을 수행하는 알고리즘을 의미O(1) 또는 O(log n) 정도의 보조 메모리만 사용하며, 기존 데이터를 재배..

DB index정의: 데이터를 빠르게 검색할 수 있도록 도와주는 데이터 구조Why?: 데이터를 빠르게 검색하고 조회 성능을 개선하기 위해 사용책의 목차처럼 특정 데이터의 위치를 미리 알고 빠르게 찾을 수 있게 한다. 언제 사용?사용해야 할 때:자주 검색하거나 정렬해야 하는 컬럼이 있을 때WHERE, JOIN, ORDER BY, GROUP BY 절에 자주 사용되는 컬럼데이터 양이 많아질수록 검색 성능이 중요한 경우 사용하지 말아야 할 때:자주 업데이트, 삽입, 삭제가 발생하는 컬럼 (인덱스 유지 비용이 높음)작은 테이블 (인덱스 효과가 크지 않음)   인덱스 종류dense vs sparsedense : 데이터 파일의 모든 값에 대한 인덱스 항목이 존재하는 것을 의미sparse : 데이터 파일의 일부 값에 ..

정의: 해커에 의해 조작된 SQL 쿼리문이 데이터베이스에 그대로 전달되어 비정상적 명령을 실행시키는 공격 기법 공격 방법Basic SQL Injection정의: 쿼리 문자열에 악성 SQL 코드 삽입예시: 항상 참이 되는 조건을 삽입해 인증을 우회하는 경우 (' OR '1'='1 )SELECT * FROM users WHERE username = 'input' AND password = 'input';SELECT * FROM users WHERE username = 'jang' OR '1'='1'; -- AND password = 'input'; Union-Based SQL Injection정의: UNION SQL 연산자를 사용하여 추가 데이터를 반환받음단, 자료형이 동일해야함예시: 상품 정보를 가져오는 ..

종류두 개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법(INNER) JOINLEFT OUTER JOINRIGHT OUTER JOINFULL OUTER JOINCROSS JOINSELF JOIN 1. INNER JOIN정의: 두 테이블의 공통된 정보만 가져오는 방식 결과: 2. LEFT OUTER JOIN정의: 왼쪽 테이블의 모든 정보를 가져오고, 만약 오른쪽 테이블에 해당 정보가 없으면 빈 값(NULL)을 삽입 결과:  3. RIGHT OUTER JOIN정의: 오른쪽 테이블의 모든 정보를 가져오고, 만약 왼쪽 테이블에 해당 정보가 없으면 빈 값(NULL)을 삽입 결과: 4. FULL OUTER JOIN정의: 두 테이블의 모든 정보를 가져오는데, 어느 한 쪽에 정보가 없으면 빈 값으로 ..

TCP 통신정의: 네트워크 통신에서 신뢰적인 연결방식 = reliable network를 보장하는 프로토콜How?: network congestion avoidance 알고리즘을 사용 reliable Networkunreliable vs reliableunreliable: 전송한 데이터그램이 유실될 수 있고, 순서가 바뀌어 도착할 수 있음reliable: 세그먼트가 유실될 경우 재전송을 통해 복구, 순서가 바뀌어 도착하더라고 순서 번호를 이용하여 제대로 맞추어 전달 reliable network의 4가지 문제점reliable network를 보장한다는 것은 4가지 문제점 존재손실 : packet이 손실될 수 있는 문제순서 바뀜 : packet의 순서가 바뀌는 문제Congestion : 네트워크가 혼잡한 ..

파일 시스템(HDD)의 주요 문제OS가 파일 시스템에 파일을 어떻게 할당(allocate) 할 것인가?효율적으로, 빠르게 접근이 가능하도록3가지 방법연속적 할당(Contiguous Allocation)연결 할당(Linked Allocation)색인 할당(Indexed Allocation) 연속적 할당정의: 파일 시스템(HDD)에 파일들을 연속적으로 배치하는 방법문제점: 외부 단편화(external fragmentation) 문제 발생또한, 파일을 수정하면서 파일 크기가 늘어났을때, 현재 공간의 용량을 초과하면 전체를 또 맞는 크기의 공간으로 옮겨줘야함 연결 할당정의: 파일을 블럭 단위로 쪼재고, 이거를 링크 리스트 방식으로 관리하는 방법장점: 외부 단편화 문제X단점: 랜덤 엑세스 불가능: 링크 리스트로 ..

배경정의: 프로세스를 실행할 때 실행에 필요한 일부만 메모리에 로드하고 나머지는 디스크(backing store)에 두는 기술따라서, 프로세스 전체가 물리적 메모리에 있는 것'처럼' 수행되어, 물리적 메모리가 훨씬 많이 있는 것처럼 보이게 됨결과적으로 더 많은 프로그램을 동시에 실행 가능  Demand Paging정의: 현재 필요한 Page만 메모리에 올리는 방법Page Fault Handling을 통해 구현 가능Page Fault: 요청된 페이지가 MM에 없는 경우 Page Fault Handling(처리 방법)valid-invalid 1bit를 이용해서 처리valid: page가 메모리에 존재 ( & 해당 프로세스에 맞는 페이지 legal )invalid page가 메모리에 존재 ( | 해당 프로세스..

배경지금까지는 CPU를 중점으로 프로세스들이 CPU를 어떻게 나눠 가지냐를 다뤘다면, 이제부터는 메모리에 프로세스를 어떻게 배치하고 관리할지에 대해서 학습 메모리 할당(Allocation)Contiguous Memory Allocation정의: 한 프로세스를 메모리상에 연속적인 위치에 할당하는 방법 - 간단한 방법즉, 프로세스를 한 덩어리채로 메모리에 할당한다는 것방법: 메모리의 어느 부분이 비어있는지에 대한 정보(free-block list)를 통해 프로세스를 할당Dynamic 프로세스를 빈 공간(hole)에 넣는 3가지 전략First-Fit: 프로세스를 넣을 수 있는 첫번째 hole에 할당하는 전략Best-Fit: 프로세스를 넣을 수 있는 공간 중에 가장 작은 hole에 할당하는 전략Worst-Fit..