[DFS & BFS]

1. 그래프 기초그래프란 무엇인가그래프는 노드(Node, 정점)와 간선(Edge)으로 구성된 자료구조다. 도시와 도로에 비유할 수 있다. 도시가 노드고, 도시를 연결하는 도로가 간선이다. 지하철 노선도, 소셜 네트워크 친구 관계, 웹 페이지 간의 링크가 모두 그래프 구조다. 1 / \ 2 3 / \ \ 4 5 6배열이나 트리와의 차이는 구조의 자유도에 있다. 배열은 순서가 있고, 트리는 부모-자식 관계가 있으며 사이클이 없다. 그래프는 노드 간 연결 방식에 제약이 없어 사이클도 허용한다.방향 그래프와 무방향 그래프무방향 그래프: 방향 그래프: A --- B A --> B | | ..

  • format_list_bulleted CodingTest/자료구조-알고리즘
  • · 2026. 3. 31.
  • textsms

[재귀 & 완전 탐색] & [백트래킹]

1. 재귀 함수 설계 원칙재귀란 무엇인가함수가 자기 자신을 호출하는 방식으로 문제를 더 작은 같은 구조의 문제로 쪼개는 기법이다.거울 두 개를 마주 보게 세우면 그 안에서 거울이 무한히 반복된다. 다만 프로그래밍에서 무한 반복은 곧 RecursionError다. 반드시 멈추는 조건이 있어야 한다.팩토리얼이 가장 직관적인 예시다:5! = 5 × 4!4! = 4 × 3!3! = 3 × 2!2! = 2 × 1!1! = 1 ← 여기서 멈춘다def factorial(n): if n 재귀 설계 3단계재귀 함수를 작성할 때 세 가지를 순서대로 결정한다.1단계: 부분 문제 정의─────────────────────────────────────────────"큰 문제를 같은 구조의 작은 문제로 어떻..

  • format_list_bulleted CodingTest/자료구조-알고리즘
  • · 2026. 3. 24.
  • textsms

해시 (Hash)

해시란해시 함수는 임의의 데이터를 고정된 크기의 정수로 변환하는 함수다. 좋은 해시 함수가 되려면 세 가지 조건을 갖춰야 한다. 첫째, 결정적이어야 한다. 같은 입력에는 항상 같은 출력이 나와야 한다. 둘째, 균등하게 분포해야 한다. 출력 값이 특정 범위에 몰리지 않고 전체 배열에 고르게 흩어져야 충돌이 줄어든다. 셋째, 빠르게 계산할 수 있어야 한다. 해시 값 계산 자체가 O(1)에 이루어져야 조회 전체가 O(1)로 유지된다. 이 정수를 인덱스로 사용해서 배열에 값을 저장한 것이 해시 테이블이다.키 → 해시 함수 → 정수 (해시 값) → 배열 인덱스"apple" → h("apple") → 3 → table[3] = value배열의 특정 인덱스에 바로 접근하기 때문에 삽입, 삭제, 검색 모두 ..

  • format_list_bulleted CodingTest/자료구조-알고리즘
  • · 2026. 3. 17.
  • textsms

큐 (Queue)

큐란큐는 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..

  • format_list_bulleted CodingTest/자료구조-알고리즘
  • · 2026. 3. 17.
  • textsms

스택 (Stack)

스택이란스택은 LIFO(Last In, First Out) 원칙으로 동작하는 자료구조다. 마지막에 넣은 것이 가장 먼저 나온다.실생활 비유로는 접시 쌓기가 대표적인 비유다. 접시를 위에 쌓고, 꺼낼 때도 맨 위에서부터 꺼낸다. 브라우저의 뒤로가기도 같은 원리다. 방문한 페이지를 스택에 쌓고, 뒤로가기를 누르면 가장 최근 페이지부터 꺼낸다.push → [ ] → [A] → [A, B] → [A, B, C]pop ← ← [A, B] ← top: C프로그래밍에서 스택이 가장 핵심적으로 쓰이는 곳은 콜 스택이다. 함수를 호출하면 해당 함수의 실행 정보(지역 변수, 반환 주소 등)가 스택 프레임으로 쌓인다. 함수가 반환하면 해당 프레임이 꺼..

  • format_list_bulleted CodingTest/자료구조-알고리즘
  • · 2026. 3. 17.
  • textsms

연결 리스트 (Linked List)

연결 리스트란연결 리스트는 노드(Node)들이 사슬처럼 이어진 자료구조다. 각 노드는 두 가지를 담고 있다. 하나는 실제 데이터인 값(value)이고, 다른 하나는 다음 노드를 가리키는 참조(next)다. 마지막 노드의 참조는 None으로 끝난다.연결 리스트의 시작점을 head라고 부른다. head를 알면 연결된 모든 노드를 순서대로 따라갈 수 있다. 배열처럼 인덱스로 건너뛰는 것은 불가능하고, 반드시 head부터 한 칸씩 이동해야 한다.보물찾기에 비유할 수 있다. 각 쪽지에는 힌트와 함께 다음 쪽지가 있는 장소의 주소가 적혀 있다. 처음 쪽지(head)부터 시작해서 하나씩 따라가야만 원하는 쪽지에 도달할 수 있다. 중간 쪽지를 건너뛰고 바로 다섯 번째 쪽지로 이동하는 방법은 없다.head → [10 |..

  • format_list_bulleted CodingTest/자료구조-알고리즘
  • · 2026. 3. 16.
  • textsms