코딩테스트 스터디 7주차 학습 자료를 정리한 글이다.정렬된 배열에서 탐색 범위를 절반씩 줄여 나가는 알고리즘과, 이를 확장해 최적값을 구하는 파라메트릭 서치를 다룬다.1. 이분 탐색 기초이분 탐색이란이분 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용하는 탐색 알고리즘이다. 처음부터 끝까지 하나씩 확인하는 선형 탐색은 O(n)이지만, 이분 탐색은 O(log n)이다. n이 10억이어도 탐색 횟수는 30번이면 충분하다.전화번호부를 펼칠 때와 같은 원리다. "박지훈"을 찾는다면 책 한가운데를 펼쳐서 현재 위치가 "박"보다 앞인지 뒤인지 확인한다. 앞이라면 오른쪽 절반만, 뒤라면 왼쪽 절반만 남긴다. 이 과정을 반복하면 수천 페이지의 전화번호부도 10번 남짓한 탐색으로 찾을 수 있다.단, 이분 탐색은 반드시 ..
1. 그래프 기초그래프란 무엇인가그래프는 노드(Node, 정점)와 간선(Edge)으로 구성된 자료구조다. 도시와 도로에 비유할 수 있다. 도시가 노드고, 도시를 연결하는 도로가 간선이다. 지하철 노선도, 소셜 네트워크 친구 관계, 웹 페이지 간의 링크가 모두 그래프 구조다. 1 / \ 2 3 / \ \ 4 5 6배열이나 트리와의 차이는 구조의 자유도에 있다. 배열은 순서가 있고, 트리는 부모-자식 관계가 있으며 사이클이 없다. 그래프는 노드 간 연결 방식에 제약이 없어 사이클도 허용한다.방향 그래프와 무방향 그래프무방향 그래프: 방향 그래프: A --- B A --> B | | ..
1. 재귀 함수 설계 원칙재귀란 무엇인가함수가 자기 자신을 호출하는 방식으로 문제를 더 작은 같은 구조의 문제로 쪼개는 기법이다.거울 두 개를 마주 보게 세우면 그 안에서 거울이 무한히 반복된다. 다만 프로그래밍에서 무한 반복은 곧 RecursionError다. 반드시 멈추는 조건이 있어야 한다.팩토리얼이 가장 직관적인 예시다:5! = 5 × 4!4! = 4 × 3!3! = 3 × 2!2! = 2 × 1!1! = 1 ← 여기서 멈춘다def factorial(n): if n 재귀 설계 3단계재귀 함수를 작성할 때 세 가지를 순서대로 결정한다.1단계: 부분 문제 정의─────────────────────────────────────────────"큰 문제를 같은 구조의 작은 문제로 어떻..
해시란해시 함수는 임의의 데이터를 고정된 크기의 정수로 변환하는 함수다. 좋은 해시 함수가 되려면 세 가지 조건을 갖춰야 한다. 첫째, 결정적이어야 한다. 같은 입력에는 항상 같은 출력이 나와야 한다. 둘째, 균등하게 분포해야 한다. 출력 값이 특정 범위에 몰리지 않고 전체 배열에 고르게 흩어져야 충돌이 줄어든다. 셋째, 빠르게 계산할 수 있어야 한다. 해시 값 계산 자체가 O(1)에 이루어져야 조회 전체가 O(1)로 유지된다. 이 정수를 인덱스로 사용해서 배열에 값을 저장한 것이 해시 테이블이다.키 → 해시 함수 → 정수 (해시 값) → 배열 인덱스"apple" → h("apple") → 3 → table[3] = value배열의 특정 인덱스에 바로 접근하기 때문에 삽입, 삭제, 검색 모두 ..
큐란큐는 FIFO(First In, First Out) 원칙으로 동작하는 자료구조다. 먼저 넣은 것이 먼저 나온다.실생활 비유는 줄서기다. 먼저 줄 선 사람이 먼저 서비스를 받는다. 프린터 대기열도 마찬가지다. 먼저 인쇄 요청한 문서가 먼저 출력된다.enqueue → front [A, B, C] rear ← enqueuedequeue ← front [B, C] ← D 추가 후: [B, C, D]Python에서 큐 구현하기collections.deque로 구현코딩 테스트에서 큐는 collections.deque를 사용하는 것이 표준이다.from collections import dequequeue = deque()queue.append(1)queue.append(2)queue.appe..
스택이란스택은 LIFO(Last In, First Out) 원칙으로 동작하는 자료구조다. 마지막에 넣은 것이 가장 먼저 나온다.실생활 비유로는 접시 쌓기가 대표적인 비유다. 접시를 위에 쌓고, 꺼낼 때도 맨 위에서부터 꺼낸다. 브라우저의 뒤로가기도 같은 원리다. 방문한 페이지를 스택에 쌓고, 뒤로가기를 누르면 가장 최근 페이지부터 꺼낸다.push → [ ] → [A] → [A, B] → [A, B, C]pop ← ← [A, B] ← top: C프로그래밍에서 스택이 가장 핵심적으로 쓰이는 곳은 콜 스택이다. 함수를 호출하면 해당 함수의 실행 정보(지역 변수, 반환 주소 등)가 스택 프레임으로 쌓인다. 함수가 반환하면 해당 프레임이 꺼..
