CS (7) 썸네일형 리스트형 [알고리즘] 이진 탐색 (Binary Search) 우리가 흔히 알고있는 Netflix나 YouTube 같은 서비스에서 "2025년 10월 21일의 사용자 로그"를 찾는다고 상상해보자. 로그가 날짜순으로 정렬되어 있다면, 처음부터 하나씩 찾아볼까요? 아니면 중간부터 시작해서 "이게 1월이면 앞으로, 3월이면 뒤로" 이런식으로 범위를 좁혀갈까요?이것이 바로 이진 탐색입니다.데이터베이스의 인덱스, Git의 bisect, 배포 버전 찾기 등 실무 곳곳에서 사용되는 핵심 알고리즘입니다. 여러 코딩 테스트에서도 단골손님이죠. 이러한 중요한 알고리즘, 탐색 알고리즘에서 가장 기초가 되는 "이진 탐색"에 대해 학습한 내용을 정리하려고 합니다.이진 탐색이란?이진 탐색은 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘입니다. 배열의 중간 값과 찾으려는 값을 비교하여, 탐색.. [알고리즘] 정렬 알고리즘(선택, 삽입, 버블, 합병, 퀵, 힙) 정렬은 데이터를 특정 순서로 배열하는 알고리즘으로, CS에서 가장 기본적이면서도 중요한 개념입니다. 이번 포스팅에서는 대표적인 정렬 알고리즘 6가지를 시간 복잡도와 함께 자세히 알아보겠습니다. 정렬 알고리즘 분류정렬 알고리즘은 성능에 따라 크게 Slow, Fast 정렬 두가지로 나뉩니다.Slow 정렬 - O(n²)선택 정렬 (Selection Sort)삽입 정렬 (Insertion Sort)버블 정렬 (Bubble Sort)Fast 정렬 - O(n log n)합병 정렬 (Merge Sort)퀵 정렬 (Quick Sort)힙 정렬 (Heap Sort)성능 비교표여기서 말하는 안정성은 같은 값을 가진 요소들의 상대적 순서가 정렬 후에도 유지되는지 여부에 대한 내용입니다.알고리즘최선평균최악공간 복잡도안정성선택.. [알고리즘] 시간 복잡도와 빅오 표기법 완벽 이해하기 알고리즘을 공부하다 보면 가장 먼저 만나게 되는 개념이 바로 '빅오 표기법'입니다. "이 알고리즘의 시간 복잡도는 O(n)입니다", "O(log n)이 더 효율적입니다"와 같은 표현을 들어보셨을 텐데요. 이번 포스팅에서는 빅오 표기법이 무엇이고, 왜 중요한지, 그리고 실제로 어떻게 활용하는지 알아보겠습니다.알고리즘 복잡도란?알고리즘의 효율성을 평가하는 데는 공간 복잡도와 시간 복잡도 두 가지 기준이 있습니다.공간 복잡도 (Space Complexity)공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간을 나타내는 개념입니다.주요 특징데이터 관리에 필요한 메모리 공간을 분석합니다.입력 데이터의 크기에 따라 메모리 사용량이 어떻게 변하는지 측정합니다.변수, 배열, 재귀 호출 스택 등이 차지하는 공간.. [운영체제] 프로그램 메모리 구조 가이드 프로그램이 실행될 때 운영체제는 메모리를 어떻게 관리할까요? 이번 포스팅에서는 프로그램 실행 시 메모리가 어떻게 구성되고 동작하는지 깊이 있게 알아보겠습니다.메모리 구조의 4가지 영역프로그램이 실행되면 운영체제는 메모리를 크게 4개의 영역으로 나누어 관리합니다.1. Text 영역 (Code 영역)Text 영역은 실행 가능한 코드가 저장되는 공간입니다.1.1. 특징프로그램의 실제 명령어(기계어)가 저장됩니다.함수, 제어문(if, for, while 등), 상수 리터럴이 포함됩니다.읽기 전용(Read-Only) 영역으로 설정되어 코드 변조를 방지합니다.프로그램 실행 중 크기가 변하지 않는 정적 영역입니다.여러 프로세스가 같은 프로그램을 실행할 경우 Text 영역을 공유할 수 있습니다. 2. Data 영역Da.. 트랜잭션 개념과 ACID 원칙 트랜잭션트랜잭션은 데이터베이스에서 하나의 논리적 작업 단위를 의미합니다.모든 작업이 성공적으로 완료되거나, 하나라도 실패하면 전체가 무효화(rollback) 되어야 합니다.즉, 데이터의 정합성과 신뢰성을 보장하기 위한 핵심 메커니즘입니다.ACID 원칙원자성 (Atomicity)트랜잭션 내의 모든 작업은 전부 수행되거나 전부 취소되어야 하며, 중간 상태는 존재하지 않는다.일관성 (Consistency)트랜잭션 수행 전과 후에 데이터는 정의된 규칙(무결성 제약 등) 을 항상 만족해야 한다.고립성 or 격리성 (Isolation)동시에 실행되는 트랜잭션 간에는 서로 간섭 없이 독립적으로 수행되어야 한다.지속성 (Durability)트랜잭션이 커밋되면 그 결과는 시스템 장애가 발생해도 영구적으로 유지되어야 한다.. HTTP의 무상태성과 비연결성 상태성 (Stateful)상태성은 글자 그대로 상태를 유지하는것이다.상태를 유지하기 때문에 클라이언트와 연결된 서버는 클라이언트 요청에 대한 정보를 계속 갖고 있게 됩니다.하지만, 이 연결된 서버가 장애가 발생해 작동하지 않는다면 클라이언트는 다른 서버와 다시 연결을 하고 다시 요청을 해야합니다.예시1)카페에서 같은 점원A 에게 커피주문손님: 아메리카노 주세요.점원A: 2,000원 입니다. (아메리카노)손님: 2잔 주세요.점원A: 4,000원 입니다. (아메리카노 2잔)손님: 카드로 결제할께요.점원A: 결제 완료 되었습니다. (아메리카노 2잔 카드 결제)해당 경우에 점원A 는 주문 상태에 대해 기억하고 있습니다.예시2)카페에서 점원A + B 에게 커피주문손님: 아메리카노 주세요.점원A: 2,000원 입니.. 디스크 스케줄링 알고리즘 디스크 접근 시간탐색시간 + 회전 지연시간 + 전송시간탐색시간: 현 위치에서 특정 실린더로 디스크헤드가 이동하는데 소용되는 시간회전지연시간: 가고자하는 섹터가 디스크헤드까지 도달하는데 걸리는 시간전송시간: 데이터를 전송하는데 걸리는 시간FCFS (First-Come First Served)원리: 요청이 들어온 순서대로 처리한다.장점: 구현이 단순하며, 공평하다.단점: 디스크 헤드의 이동이 최적화되지 않아 비효율적이다.예시:요청순서: 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67헤드가 53에서 시작이동순서: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67SSTF (Shortest-Seek Time First)원리: 탐구시간이 가장 짧은 접근 요구.. 이전 1 다음