1. 트리의 정의와 표현트리란 무엇인가사이클이 없는 연결 그래프가 트리다. 정점이 V개이면 간선은 정확히 V-1개다. 간선 하나를 더 추가하면 사이클이 생기고, 하나를 제거하면 연결이 끊긴다.회사 조직도를 떠올리면 이해하기 쉽다. 대표가 루트, 각 팀장이 자식, 팀원이 리프 노드다. 한 팀원이 두 팀장에 동시에 속하는 일은 없다. 그런 경우가 생기면 그것은 이미 트리가 아니다. 1 / \ 2 3 / \ \ 4 5 6 | 7용어 정리 용어설명 루트(Root)부모가 없는 최상단 노드 부모(Parent)자신보다 한 단계 위 노드 자식(Child)자신보다 한 단계 아래 노드 리..
코딩테스트 스터디 8주차 학습 자료를 정리한 글이다.1. 최단 경로 문제의 두 갈래단일 출발점 vs 모든 쌍최단 경로 문제는 출발점이 몇 개냐에 따라 두 유형으로 나뉜다. 단일 출발점 최단 경로(SSSP, Single Source Shortest Path): 한 정점에서 나머지 모든 정점까지의 최단 거리를 구한다. 다익스트라가 대표적이다. 모든 쌍 최단 경로(APSP, All Pairs Shortest Path): 모든 정점 쌍 (i, j) 사이의 최단 거리를 한 번에 구한다. 플로이드-워셜이 대표적이다.가중 그래프 표현인접 리스트 방식으로 가중 그래프를 표현한다. graph[u]는 정점 u에서 출발하는 간선들을 (도착 정점, 가중치) 튜플의 리스트로 저장한다.graph = { 1: [(2, 2..
Python 코딩테스트 알고리즘 스터디 9주차 — 동적 계획법(DP) 내용을 정리한 글이다.LCS, 편집 거리, 0/1 배낭 — 두 변수가 동시에 변하는 문제의 점화식 패턴1. 2차원 DP 개념1차원 DP가 이전 상태 하나 혹은 두 개만 참조했다면, 2차원 DP는 두 개의 변수(인덱스)가 동시에 변하는 문제에서 등장한다. dp[i][j]가 무엇을 의미하는지 먼저 명확히 정의한다. 두 개의 변수가 있다는 것은 보통 두 가지 입력이 동시에 관계를 맺는 상황임을 뜻한다.대표적인 상황: 두 문자열 A, B를 동시에 참조하는 경우 (LCS, 편집 거리) 물건 개수와 용량을 동시에 고려하는 경우 (배낭 문제) 부분 구간 [i, j]를 고려하는 경우 (구간 DP)2차원 테이블 초기화2차원 dp는 테이블로 시각화..
Python 코딩테스트 알고리즘 스터디 8주차 — 동적 계획법(DP) 내용을 정리한 글이다.1차원 DP 문제는 점화식 도출 방법론을 익히면 대부분 같은 패턴으로 풀린다.1. 점화식 도출 방법론점화식을 도출하는 방법은 다음 세 단계를 따른다. 1단계: dp[i]의 의미를 먼저 정의한다 무엇을 저장할지 결정하는 것이 가장 중요하다. dp[i]가 무엇을 의미하는지 명확하게 써둔 뒤 코드를 짜야 실수가 없다. 2단계: 마지막 선택을 기준으로 경우를 분기한다 dp[i]를 만들기 직전 단계에 어떤 선택이 가능했는지 나열한다. 각 선택에서 이전 dp 값이 어떻게 연결되는지 찾으면 점화식이 보인다. 3단계: 초기값(base case)을 설정한다 가장 작은 입력에서의 정..
Python 코딩테스트 알고리즘 스터디 8주차 — 동적 계획법(DP) 내용을 정리한 글이다.다이나믹 프로그래밍은 이미 계산한 결과를 기억해두고 다시 계산하지 않는 방식이다.1. DP란 무엇인가핵심 아이디어다이나믹 프로그래밍(이하 DP)은 중복 부분 문제와 최적 부분 구조를 가진 문제를 효율적으로 푸는 기법이다. 중복 부분 문제: 같은 하위 문제가 반복적으로 등장한다 최적 부분 구조: 전체 문제의 최적해가 부분 문제들의 최적해로 구성된다 "기억하며 풀기"가 DP의 핵심이다. 같은 계산을 두 번 하지 않는다.재귀의 중복 계산 문제: 피보나치 트리피보나치 수열을 순수 재귀로 구현하면 무슨 일이 일어나는지 살펴보자. fib(5)를 계산하는 호출 트리를 그리면 다음과 같다. ..
코딩테스트 스터디 7주차 학습 자료를 정리한 글이다.매 순간 가장 좋아 보이는 선택을 반복해 전체 최적해를 구하는 방식과, 이분 탐색과 결합해 최적값을 검증하는 패턴을 다룬다.1. 그리디 알고리즘그리디란그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방식이다. 미래를 고려하지 않고 현재 상태에서 최적인 선택을 반복한다.편의점에서 잔돈을 거슬러줄 때와 같은 원리다. 1000원을 거슬러줘야 한다면, 500원짜리를 먼저 최대한 사용하고, 그다음 100원, 50원, 10원 순서로 처리한다. 매 단계에서 가능한 큰 동전을 선택하는 것이 결국 최소 개수의 동전으로 이어진다.그런데 이 전략이 항상 옳은 것은 아니다. 동전 종류에 따라 그리디가 실패하는 경우도 있다. 그것이 그리디와 DP를 구분하는 핵심이다...
