software engineering/algorithms

<안내글>

알고리즘과 관련된 정리 내용은 앞으로 특별한 경우가 아니면 아래 레포지토리 내 문서에 기록할 예정입니다. https://github.com/hagukin/PS/blob/main/algorithms.md

이분탐색, 파라메트릭 서치

https://marades.tistory.com/7 이진탐색(Binary Search)와 파라메트릭서치(Parametric Search) 오늘 처음으로 소개할 알고리즘은 이진 탐색과 파라메트릭 서치입니다. 많은 분들이 이진 탐색에 대해선 많이 들어보셨을거라 생각하지만 파라메트릭 서치라는 알고리즘은 아마 생소하신 분 marades.tistory.com 관련 문제: BOJ 1114 https://dongwoo338.tistory.com/13 [boj 1114] 통나무 자르기 www.acmicpc.net/problem/1114 알고리즘 : 이분탐색(파라메트릭) + 그리디 몇주 전 풀고 올려야지! 하고 생각만 하다 이제야 올리는 문제다. 처음에 문제 분류가 그리디 + 이분탐색으로 되있어서 난 그리 dongwo..

조합과 순열 구현

yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는 결과 값을 찾는 방식이다. 이 글에서는, 순열과 조합을 STL을 사용하지 않 yabmoons.tistory.com

그리디 알고리즘

shlee0882.tistory.com/118 탐욕 알고리즘 1. 대학교 수업시간표 짜기 문제 대학교에서 수강신청을 할 예정인데 최대한 많은 과목을 듣고 싶다. 하지만 시간이 한정적이고 시간이 겹치는 시간대에 동시에 두과목을 들을순 없다. 시간이 shlee0882.tistory.com

이진 트리 반전(inverting binary tree)

크루스칼 알고리즘

한 줄 요약: disjoint set을 사용해 cost의 합이 최소가 되는 Minimum Spanning Tree(혹은 모든 노드를 연결한 덩어리)를 찾는 것. 선행 지식: 분리 집합(Disjoint Set)

트리 순회

인오더(Inorder) - 사진 참고 Left Root Right 프리오더(Preorder) - 트리의 루트 노드에서 DFS를 돌린 것과 유사 (단 항상 왼쪽노드를 먼저 선택) Root Left Right 포스트오더(Postorder) - 트리 좌하단부터 아래에서 위로 출력 가로 한줄씩 좌->우 방향으로 출력 Left Right Root

Tree LCA(Lowest Common Ancestor)

트리에서(이진 트리가 아니어도 된다) 두 노드가 주어졌을 때 두 노드의 공통 조상들 중 가장 깊이 자리잡고 있는 조상을 찾는다. 방법1. 루트에서부터 노드A, 노드B까지의 경로를 구한다. 이렇게 구한 두 경로를 대조하며 처음으로 경로가 달라지는 지점을 찾는다. 방법2. (권장) blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221282478466&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=true&from=search 42. 최소 공통 조상(Lowest Common Ancestor) 이번 시간에 공부할 내용은 최소 공통 조상(Lowest Common Ancestor)입니다. 최소 공통 조상이란 트리..