Algorithm/Algorithm Study 썸네일형 리스트형 에라스토테네스의 체 (소수 구하기) 소수 구하기 알고리즘은 간단하지만 확실하게 정리해두지 않으면 헷갈리기 좋은 문제라고 생각한다. 하지만 다른 알고리즘들과 마찬가지로 한번만 확실하게 이해해두면 바로바로 구할 수 있기 때문에 한번정도는 정리해두는 것이 좋다. 소수는 정규 교육과정을 거친 사람은 누구나 이해하고 있을만큼 간단한 개념이다. 1을 제외하고 자기 자신으로만 나누어 떨어지는 수. 이것이 소수의 정의이다. 소수에는 많은 수학적 이론과 증명이 배경에 있겠지만 과감히 생략하고 이 정의에 입각하여 알고리즘적으로 소수를 판가름 하는 코드를 작성해보겠다. 소수에 대해서는 아래의 링크를 참고하자. 소수(수론) - 나무위키https://namu.wiki/w/%EC%86%8C%EC%88%98(%EC%88%98%EB%A1%A0) 소수는 1과 자기 자신.. 트라이(Trie) 문자열 관련 알고리즘은 정말 다루기 힘든편에 속한다. 하지만 그중에도 잘만 이해하면 유용하게 사용할 수 있는 알고리즘이 몇있다. 그중에서 트라이(Trie)에 대해서 얘기해보고자 한다. 트라이 - 나무위키https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4 트라이 알고리즘은 여러 단어들이 주어진 경우, 특정 단어가 예시로 주어진 단어들 중에 포함되는가를 빠르게 파악할 수 있는 알고리즘이다. 예를들어 n개의 단어가 주어져있고, 각 문자열의 길이가 m인 경우 단순하게 이 단어들중에 특정 단어가 포함되어있는지 확인하려면 최대 O(nm)의 시간 복잡도를 갖게된다. 하지만 트라이를 사용하면 시간복잡도가 O(m)으로 압도적으로 단축되게 된다. 어떻게 이렇게 시간이 줄어들 수 있는지 생.. 트리의 순회 트리 구조를 순회하는 방법은 일반적으로 전위, 중위, 후위 순회 세가지 방법이 있다. 방법이 복잡하지는 않지만 정리해두지 않으면 헷갈리니 기회가 되면 한번 정리해보고 직접 코드로 구현해보는 것이 좋을 것같다. 전위 순회는 루트 노드부터 시작해서 왼쪽 서브트리를 타기 전에 노드의 자료를 확인하고 그다음 왼쪽 서브트리로 이동해서 마찬가지로 전위 순회를 하게 되어있고, 왼쪽 서브트리에 대한 전위 순회를 마친 후 우측 서브트리의 전위 순회가 일어난다. 중위 순회는 루트 노드에서 시작해서 좌측 서브트리에 대한 중위 순회가 먼저 일어나고, 중위 순회가 더이상 일어날 수 없는 지점에서 노드의 자료를 확인하면서 좌측 서브트리의 중위 순회를 종료시킨다. 그다음 우측 서브트리의 중위 순회가 일어나게 된다. 후위 순회는 루.. LIS (Longest increasing subsequence) nlogn 해법 LIS(Longest Increasing Subsequence) 정의컴퓨터 공학에서, 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열 - 위키백과https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EC%A6%9D%EA%B0%80_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 LIS 문제는 수열에서 주어진 순서에서 벗어나지 않으면서 숫자가 증가하는 가장 긴 부분수열을 찾는 문제이다. 예를 들어 6개의 숫자가 주어져있다고 하자. 0 1 2 3 4 5 10 20 10.. 1102번: 발전소 - Baekjoon Online Judge 외판원 문제(TSP: Traveling Salesperson Problem)로 대표되는 NP-난해에 해당하는 문제이다. 외판원 문제는 여러 도시가 주어졌을때 외판원이 도시별로 이동하는데 드는 비용이 각각 다른 경우 모든 도시를 다 돌고오는데 드는 비용을 어떻게 최소로 만들 것인지를 물어보는 문제이다. 외판원 문제 - 위키백과, 우리 모두의 백과사전https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C 발전소 문제도 이와 유사하다. 여러 발전소가 주어지고 발전소가 켜져있는 경우 그 발전소를 이용하여 다른 발전소를 켤 수 있고 그때의 비용은 각각 다르게 주어진다. 이때 최소한 켜져야하는 발전소의 숫자가 주어졌을 때 그 발전소 .. 1654번: 랜선 자르기 - Baekjoon Online Judge 1654번: 랜선 자르기 - Baekjoon Online Judgehttps://www.acmicpc.net/problem/1654 랜선 자르기 문제는 이분 탐색을 이용하여 범위 내에서 원하는 개수의 랜선을 만들되 그 길이는 최대값이 되도록 하는 문제이다. 원하는 값을 찾기에는 너무 많은 값을 하나씩 대입해야 하기 때문에 이분 탐색을 이용하여 가능한 후보군을 줄임으로써 시간내에 원하는 값을 찾을 수 있다. 이분 탐색 문제를 푼다고 했을 때 구현에서 차이가 나는 부분은 어떤 기준으로 중앙값을 옮겨줄 것인가이다. 이 문제의 경우 주어진 랜선을 적절하게 잘라서 원하는 개수를 맞춰주는 것이기 때문에 랜선의 길이가 중앙값 이동의 기준이 된다. 처음 중앙값은 0에서 int의 max값 사이에 있다는 것을 가정하고 그.. 2162번: 선분 그룹 - Baekjoon Online Judge 선분 그룹이라는 문제는 기하 알고리즘 문제풀이의 기초이자 꽃이라고 할 수 있는 CCW를 이용하는 동시에 유니온 파인드를 섞어 놓은 문제였다. 문제를 보면서 대충 어떤 식으로 풀면되겠다는 것이 머리 속에 그려져서 로직도 금방 세우고 코딩도 금방했는데 의외로 계속 오답이 나서 짜증나는 문제였다. 문제를 살펴보면 여러 선분이 주어졌을 때, 만일 선분끼리 교차되거나 겹치게 되면 그 선분들은 하나의 그룹이 된다. 이 때 선분들을 몇 개의 그룹으로 묶을 수 있고 그룹 중에 가장 많은 선분을 포함하고 있는 그룹에 속한 선분이 몇 개인지 출력하면 된다. 문제를 보고 생각난 것은 CCW였다. 기하 문제를 풀어본 사람은 알겠지만, CCW를 이용하면 두 선분의 교차 여부를 쉽게 파악할 수 있다. 만일 CCW가 익숙하지 않은.. CCW(CounterClockWise) 알고리즘 CCW(CounterClockWise)는 외적을 이용해서 두 벡터의 상대적 위치를 파악하는 알고리즘이다. 좀더 구체적으로 설명하자면 하나의 정점을 기준으로 다른 두 정점으로 향하는 벡터가 존재할 때 각 정점의 상대적 위치를 판단하는 공식이다. 만일 하나의 정점에서 다른 정점으로 향하는 벡터를 기준으로 왼쪽에 존재하는 정점의 경우 외적은 양의 값을 갖게 되고, 상대적으로 우측에 있게 되면 외적은 음의 값을 갖게된다. 마지막으로 세 점이 하나의 직선 위에 놓이게 되었을 때 외적은 0이 된다. 이를 이용하여 다각형의 넓이 구하기, 정점의 위치판단(다각형 내부/외부 위치 구분), 볼록다각형 그리기(Convex Hull) 등 다양한 기하 문제를 풀어낼 수 있다. 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세.. 이전 1 2 다음
