목록알고리즘 (12)
멈추지 않고 끈질기게
[알고리즘] 플로이드-워셜(Floid-Warshall) 알고리즘
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다. ※ 해당 포스팅은 하기 출처들을 참조하였습니다.- 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022- https://chanhuiseok.github.io/posts/algo-50/ 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘컴퓨터/IT/알고리즘 정리 블로그chanhuiseok.github.iohttps://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm..
[알고리즘] 소수 관련(에라토스테네스의 체, 골드바흐 추측)
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다. ※ 해당 포스팅은 하기 출처들을 참조하였습니다.https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 2부터 소수를ko.wikipedia.orghttps://ko.wikipedia.org/wiki/%EA%B3%A8%ED%8A%B8%EB%B0%94%E..
[알고리즘] 백 트래킹(back-tracking)
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.※ 해당 포스팅은 하기 출처들을 참조하였습니다.- https://edder773.tistory.com/75 [파이썬] 탐색 알고리즘 정리 - 백트래킹백트래킹 (*Notion AI의 설명) 백트래킹(Backtracking)은 해결책을 구하기 위해 모든 가능성을 시도해보는 것이 아니라, 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지 여부edder773.tistory.comhttps://youngdroidstudy.tistory.com/entry/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9%EC%9D%98-%..
[알고리즘] 팰린드롬 찾기 - Manacher's Algorithm
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.※ 해당 포스팅은 하기 출처들을 참조하였습니다.- https://m.blog.naver.com/jqkt15/222108415284 [알고리즘] Manacher’s Algorithm - 마나커(마나허) 알고리즘어떤 문자열에서 팰린드롬의 개수와 위치를 찾는 알고리즘인 "Manacher's Algorithm"에 ...blog.naver.com- https://small-stepping.tistory.com/987 마나커(Manacher) 알고리즘1. 마나커 알고리즘(Manacher's Algorithm)이란?어떤 문자열에서 팰린드롬의 개수와 위치를 찾는 알고리즘이다. 팰린드롬이란?팰린드롬(회문, Palindrome)은..
[알고리즘] 이분법(Bisection method)
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다. ※ 해당 포스팅은 하기 출처들을 참조하였습니다. - https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84%EB%B2%95_(%EC%88%98%ED%95%99) 이번 포스팅에서는 이분법 알고리즘에 대해 알아보겠습니다. 1. 이분법(Bisection Method)의 정의 이분법(Bisection method)이란 수학에서 해를 구하는 접근법입니다. 해가 반드시 존재하는 폐구간을 정한 뒤, 중간 값이 해를 만족하는지 검사한 후 결과에 따라 폐구간의 범위를 좁혀가며 계산해나가는 방식입니다. 상기 그림은 y = ax + b의 그래프를 그린 것입니다. 단순한 1차 함수이므로 바로 x = ..
[알고리즘] 동적 계획법(Dynamic Programming)
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다. ※ 해당 포스팅은 하기 출처들을 참조하였습니다. - 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022 이번 포스팅에서는 동적 계획법(Dynamic Programming)에 대해 알아보도록 하겠습니다. 1. 동적 계획법이란 동적 계획법(Dynamic Programming, 이하 DP)이란 문제를 해결하기 위해 해당 문제를 여러개의 부분 문제로 나누고, 그 부분 문제의 해답을 이용하여 전체 문제를 해결하는 방식을 말합니다. A*와 같이 특정 기능에 특화된 알고리즘은 아니고, 일종의 방법론에 속합니다. 동적 계획법을 적용하려면 문제가 다음과 같은 특성을 만족해야 합니다. -..
[알고리즘] 그리디 알고리즘(Greedy Algorithm)
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다. ※ 해당 포스팅은 하기 출처들을 참조하였습니다. - 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022 이번 포스팅에서는 그리디 알고리즘(Greedy Algorithm)에 대해 알아보겠습니다. 1. 개요 그리디 알고리즘(Greedy Algorithm)은 우리말로 탐욕법이라고도 하며, 현재 가장 좋다고 판단되는 값을 우선적으로 취하고 이를 반복하여 가장 좋은 결과를 도출해내는 방식입니다. 그림 1은 은행의 각 창구의 손님들의 대기열을 도식화 한 것입니다. 각 사각형은 손님을 나타내며, 안의 숫자는 해당 손님이 업무를 보는데 소요되는 시간(분)을 나타냅니다. A 창구에서 가..
[알고리즘] A* 알고리즘
※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다. ※ 해당 포스팅은 하기 출처들을 참조하였습니다. - 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022 이번 포스팅에서는 특정 정점간의 최단거리를 계산하는데 있어 효율적인 A* 알고리즘에 대해 알아보겠습니다. 1. 개요 A* 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 거리(경로)를 구하는 데 사용하는 알고리즘이며, 시작점부터 방문하여 연결된 정점들과 값을 비교하는 방식은 비슷하나 다음과 같은 차이점이 있습니다. - 1) 모든 정점이 아닌 시작점과 목표지점 간의 최단 거리(경로)를 계산 - 2) 정점의 값(F)을 지금까지의 이동 비용(G)과 목표 지점까지의 예상 이동..