Algorithm Training
07 Jan 2019 | Daily서론 문제 유형을 빠르게 파악하자 알고리즘 분석을 수행하자 코드를 테스트하는 기술에 능숙해지자 내장된 라이브러리가 있는 선형 자료 구조 내장된 라이브러리가 있는 비선형 자료 구조 자체적인 라이브러리가 필요한 자료 구조 그래프 유니온-파인트 상호 배타적 집합 구간 트리 이진 인덱스 트리(펜윅 트리) 문제해결 패러다임 완전 탐색 분할 정복 탐용법 DP 그래프 그래프 탐색 깊이 우선 탐색 너비 우선 탐색 연결된 컴포넌트 구하기(무방향 그래프) 플러드 필(연결된 컴포넌트에 번호를 붙이거나 색칠하기) 위상 정렬(사이클 없는 방향 그래프) 이분 그래프 검사 DFS 스패닝 트리를 이용한 그래프의 간선 속성 검사 절단점 및 다리 구하기(무방향 그래프) 최소 스패닝 트리 크루스칼 알고리즘 프림 알고리즘 몇가지 활용 예 단일 시작점 최단 경로 가중치 없는 그래프에 대한 단일 시작점 최단 경로 가중치 그래프에 대한 단일 시작점 최단 경로 음수 사이클이 존재하는 그래프에 대한 단일 시작점 최단 경로 모든 쌍 최단 경로 플로이드-워셜의 DP 풀이에 대한 설명 몇가지 활용 예 네트워크 유량 포드-풀커슨 기법 에드몬드-카프 알고리즘 유량 그래프 모델링-1 몇가지 활용 예 유량 그래프 모델링-2 특수 그래프 사이클 없는 방향 그래프 트리 오일러 그래프 이분 그래프 문자열 처리 문자열 매칭 KMP 알고리즘 2차원 격자에 대한 문자열 매칭 동적 계획법을 이용한 문자열 처리 문자열 정렬(편집 거리) 최장 공통 부분 수열 DP로 풀 수 있는 고전적이지 않은 문자열 처리 문제 접미사 트라이.트리.배열 접미사 트라이 및 그 활용 예 접미사 트리 접미사 트리의 활용 예 잡미사 배열 접미사 배열의 활용 예 고급 주제 고급 탐색 기법 비트마스크를 이용한 퇴각 검색 가지치키를 많이 사용한 퇴각 검색 BFS나 다익스트라 알고리즘을 이용한 상태 공간 탐색 중간 만남 기법(양방향 탐색) 정보 탐색(A*와 IDA*) 고급 DP 기법 비트마스크를 이용한 DP 자주 사용되는 (DP) 인자 모음 오프셋 기법을 이용하여 인자의 값이 음수인 경우 처리하기 MLE? 메모 테이블로 균형 잡힌 이진 검색 트리를 사용하는 복구하자. 문제 분해하기 두가지 요소: 답에 대한 이진 탐색과 다른 요소 두가지 요소: 정적인 1차원 구간 합 최소 최대 질의 사용하기 두가지 요소: 그래프 사전 처리와 DP 두가지 요소: 그래프를 다루는 문제 두가지 요소: 수학을 다루는 문제 두가지 요소: 완전 탐색과 기하 두가지 요소: 효율적인 자료구조 사용하기. 세가지 요소포스팅
가져온곳: URL