CS/Algorithms15 ♟ 하이어홀처(Hierholzer) 알고리즘 관련글 :작동 방식 (6번 문제)https://waydd.tistory.com/135 1, 하이어홀처 알고리즘 이란 오일러 투어나 회로를 효율적으로 찾는 알고리즘 → 오일러 투어 (= 오일러 회로) 가 존재한다는 전제하에 실제 경로를 구하는 효율적인 방법모든 정점의 차수가 짝수인 연결 그래프에서 오일러 회로를 찾는 알고리즘으로 처음 제안 → 현재 존재하는 간선을 재귀적으로 탐색하여 오일러 회로(사이클)를 구성하는 방식 → 모든 간선을 한 번씩만 방문 + 역순 경로가 오일러 회로 → 응용하여 오일러 경로도 구할 수 있음 DFS와 스택을 활용 + 사이클 구성먼저 오일러 경로나 회로 존재 조건을 확인해야 함그래프가 오일러 회로 조건을 만족할 때 (무향 그래프 : 모든 정점 차수 짝수, 방향 그래프 : i.. 2025. 8. 22. ♟ 백트래킹 함께 쓰는 미니맥스(Minimax) 알고리즘 관련글 :완전 탐색 https://waydd.tistory.com/97 1. 미니맥스 알고리즘 두 명의 플레이어가 번갈아가며 최적의 수를 선택하는 게임에서,내가 최선의 전략을 취할 때, 상대도 최선의 방해를 한다고 가정하고 판단하는 탐색 알고리즘 (완전탐색 + 재귀 기반)→ 한쪽은 가장 큰 점수(max) 를 얻으려 하고, 다른 한쪽은 그 점수를 최소화(min) 하려 하기 때문에 이름이 Minimax 최선의 결과를 보장하는 선택하는 것 을 목표 → 내가 최대 이득, 상대는 최대 방해, 두 명의 플레이어가 교대로 최선의 수를 둔다고 가정 (내 차례에선 가장 큰 점수를 선택, 상대 차례에서는 내 점수를 가장 작게 만들 수 있는 선택을 상대가 한다고 가정) → 상대가 항상 최적의 수를 두지 않는다면.. 2025. 7. 29. ♟ 빠르고 똑똑하게 길찾기, A* 알고리즘 (+ 휴리스틱) 관련글 :다익스트라https://waydd.tistory.com/13 1. A* 알고리즘 (A star) 시작 지점에서 목표 지점까지 가장 짧은 경로를 빠르게 찾아가는 휴리스틱 기반 알고리즘그래프 탐색 알고리즘의 일종, 최단 경로 탐색에 효율적 (최적+빠름)경로의 실제 비용 + 예측 비용 동시 고려다익스트라 + 추정값(h) (휴리스틱 기반)→ 우선순위 큐 사용 ( 탐색 속도 + 최단 경로 보장 )→ 낙관적인 추정 + 현실적인 속도 가 중요한 알고리즘 f(n) = g(n) + h(n) 함수를 기준으로 가장 유망한 노드부터 경로를 선택 함 → f(n) : 전체 예상 비용 (A* 는 이 값을 기준으로 가장 작은 노드를 우선 탐색) → g(n) : 시작 지점에서 현재 노드 n 까지의 실제 비용 → h(n.. 2025. 7. 28. ♟ 가장 많은 일정을 소화하는 법, 활동 선택(Activity Selection) 관련글 : 그리디https://waydd.tistory.com/91허프만 인코딩https://waydd.tistory.com/110 1. 활동 선택 문제 하나의 자원을 여러 활동들이 공유할 때, 겹치지 않게 할 수 있는 최대 개수의 활동을 선택 하는 그리디 + 정렬 기반 문제각 활동은 시작 시간(start) 과 종료 시간(end) 이 주어짐 (단, 모든 활동은 단일 자원 사용, 한 시점에 하나의 활동만 가능) 종료 시간이 가장 빠른 활동부터 선택 (선택시 비겹치게) 하는 것이 전역 최적을 보장 (그리디) → 모든 활동을 종료 시간 기준으로 오름차순 정렬 후, 선형 탐색(먼저 끝나는 것부터) + 겹치지 않으면 선택 → 현재 활동의 시작 시간 ≥ 이전 활동의 종료 시간 이면 선택 ( 두 활동이 겹치지 않.. 2025. 7. 28. ♟ 최소한의 비트로 압축하기, 허프만 코딩(Huffman Coding) 관련글 :그리디https://waydd.tistory.com/91활동 선택 문제https://waydd.tistory.com/111 1. 허프만 코딩 (Huffman Coding) 주어진 문자들의 빈도에 따라 최소 길이의 이진 코드를 만드는/할당하는 그리디 알고리즘, 트리 기반의 압축 알고리즘(이자 문제 이름)→ 그리디 알고리즘의 대표 예시로, 매 단계에서 가장 비용이 적은 두 항목을 선택하여 병합→ 트리 구조 생성 + 그 트리 바탕으로 이진 코드 부여자주 나오는 문자는 짧게, 드물게 나오는 문자는 길게 빈도 기반 인코딩→ 빈도 수 큰 문자가 많은 비중을 차지, 짧게 표현함으로서 전체 평균 길이 (혹은 전체 데이터 크기) 를 최소화 (무손실 압축이므로 나중에 복원도 가능)※ 인코딩이란? 다른 환경.. 2025. 7. 28. ♟ 구간을 유지하며 처리하는 전략, 슬라이딩 윈도우 관련글 :완전 탐색https://waydd.tistory.com/97 1. 슬라이딩 윈도우 (Sliding Window) 연속된 범위 (구간) 에서 반복 계산을 줄이기 위한 알고리즘 기법→ 고정된 크기의 창을 배열 위에서 왼쪽에서 오른쪽으로 한칸씩 이동하면서 계산 (반복 계산 없이 값을 재활용)고정/가변 구간을 이동시키며 누적값(합, 카운트) 또는 조건(중복 방지, 최대 길이 제한)을 유지 → 구간을 이동 시킬때 윈도우의 좌우경계를 투포인터로 표현, 이동 (특히 가변 윈도우에서) + 누적값(합계, 빈도)/상태(중복 여부) 등 윈도우 상태를 저장 → 고정 길이 윈도우 는 end 만 이동 ex) 중복 없는 문자열 : 중복 생기면 start를 오른쪽으로 이동→ 가변 길이 윈도우 는 start.. 2025. 7. 21. 이전 1 2 3 다음