분류 전체보기
-
JUNGOL...180일지 2022. 1. 14. 15:27
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
알고리즘...102일지 2022. 1. 14. 13:20
그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
JUNGOL...179일지 2022. 1. 12. 15:41
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
동적 프로그래밍 개념프로그래밍 기초/알고리즘 2022. 1. 12. 10:45
동적 프로그래밍 동적 프로그래밍 개념 큰 문제의 해답에 작은 문제의 해답이 포함되는 알고리즘을 재귀적으로 처리할 때 나타나는 비효율을 제거하기 위한 프로그래밍 방식을 동적 프로그래밍이라고 한다. 가령 피보나치수열의 경우 다음과 같은 식으로 나타난다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 재귀적으로 해결하기 위해서는 기존에 구했던 해답을 다시 구하는 등의 반복이 일어난다. 이러한 문제를 해결하기 위해 부분 결과를 저장하면서 해를 구하는 것이 동적 프로그래밍의 핵심이다. 가령 위에서 설명한 피보나치수열의 문제를 동적 프로그래밍을 적용해 해결한다면 다음과 같이 풀 수 있다. 피보나치수열 알고리즘 fib(n) { if (f[n] ≠ 0) then return f[n]; el..
-
JUNGOL...178일지 2022. 1. 11. 17:19
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
알고리즘...101일지 2022. 1. 11. 13:51
트리를 이용한 집합의 처리 연결 리스트를 이용한 집합의 처리보다 효율적인 방식으로 각각의 집합을 트리로 표현하는 방법이다. 기존의 트리와는 달리 자식 노드가 부모 노드를 가리키는 방식으로 표현된다. 이러한 방식을 사용하는 경우 두 집합을 합칠 때 단순하게 합치려는 노드의 루트가 기존 집합의 루트를 가리키도록 하면 된다. 연산의 효율성을 높이는 방법 - 랭크를 이용한 Union 각 노드에 자신의 서브 트리의 높이를 랭크(Rank)라는 이름으로 저장하고 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. - 경로 압축 FindSet 진행 시 중간에 만나는 모든 노드에 대해 루트를 직접 가리키도록 바꾸어 추후 FindSet을 할 때 경로의 길이를 줄이는 방법이다. 더보기 참고문헌 한빛아카데미.문병..