반응형 Programming/Algorithm5 [Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드 이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다. 사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다. .. 2023. 10. 5. [Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드 너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다. 이 그래프를 기본으로 해서 알아보겠습니다. 깊이 우선 탐색(Depth First Search) 먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊.. 2023. 8. 12. [Algorithm][Python]유니온-파인드(Union-Find) 알고리즘 + 코드 이번에는 유니온 파인드 알고리즘에 대해서 한 번 알아봅시다. 아직 학부생이던 시절에 저보다 먼저 알고리즘 공부를 하던 친구가 유니온 파인드 한 번 써보라고, 진짜 너무 편하다고 했던 기억이 나는데요. 그 때 저는 DFS/BFS도 모르던 시절이라 그런게 있구나 생각만 하고 넘겼습니다. 사실상 그런 일이 있었다는 것도 거의 잊고 지내다가 평소처럼 알고리즘 문제를 풀었는데 별로 런타임이 빠르지 않았고, 해당 문제가 어떤 태그가 있나 살펴보다가 분리 집합이라는 알고리즘으로 분류가 되어있어서 이걸 사용하면 좀 빨라지려나 싶어서 찾아봤던게 유니온 파인드와의 첫 만남이었네요. 사실 이게 유니온 파인드구나를 알았을 때는 약간의 당황과 겁이 났습니다. 저한테 유니온 파인드는 상당히 먼 얘기일거라고 생각하고 있었거든요. .. 2023. 8. 3. [Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드 저를 가장 오랫동안 괴롭혔던 알고리즘 중에 하나인 데이크스트라 알고리즘에 대해서 정리를 해볼까합니다. 그 때의 헤매던 저와 비슷한 분들께 도움이 되면 좋겠네요. 데이크스트라(Dijkstra) 최단 경로 알고리즘 최단 경로라는 말에서 짐작할 수 있듯이 데이크스트라 알고리즘은 출발점에서 도착점까지 가장 빠르게 갈 수 있는 경로를 탐색하는 알고리즘입니다. 최단 경로를 구하는 알고리즘에는 대표적으로 데이크스트라, 플로이드-워셜, 벨만-포드, A*(에이 스타) 이렇게 네가지가 있으며 이번 포스팅에서는 데이크스트라 알고리즘에 대해서만 정리를 해보겠습니다. 알고리즘의 이름인 데이크스트라는 알고리즘의 고안자인 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라(Edsger Dijkstra)의 이름을 따서 부르고 있습니다. 한.. 2023. 8. 1. [Algorithm][Python] 계수 정렬(Counting Sort) 알고리즘 + 코드 이번에는 제가 가장 좋아하는 정렬 알고리즘인 계수 정렬(Counting Sort)에 대해 작성해보겠습니다. 문제 풀이를 하면서 상당히 많이 계수 정렬을 이용한 풀이를 포스팅했습니다. 계수 정렬을 굳이 사용했던 이유는 너무 많지만 계수 정렬을 알게 된 이유는 백준 문제 때문이었네요. counting sort 정도로 빠른 정렬 알고리즘을 사용하지 않으면 풀 수 없는 문제가 있었던 것으로 기억합니다(비고에도 counting sort를 알아보라는 말이 적혀있었구요). 그게 계기가 되어서 계수 정렬을 공부했고 처음엔 이게 무슨 말인가 싶었는데 익숙해지니까 속도도 빠르고 직관적이라 자주 쓰게 되었네요. 계수 정렬 그렇다면 계수 정렬(Counting Sort)은 무엇일까요? 위키피디아에 따르면 양의 정수를 키로 하여.. 2022. 12. 23. 이전 1 다음 반응형
