챎발자

더보기더보기더보기더보기이 포스트는 활동하는 동아리 내에서 공부한 뒤, 작성하였습니다.일반적으로 프로그램은 구현에서부터 시작합니다.단순한 구현은 높은 시간 복잡도를 초래할 수 있습니다. 조건문과 반복문은 재귀 호출을 이용하기에 때문이겠죠?즉, 거대한 데이터에서 빠르게 정답을 도출해야 되는 구현 알고리즘의 상황과는 맞지 않습니다. 그리하여 탐욕법이라는 알고리즘을 사용합니다.우리는 거대한 데이터 크기에서 빠르게 정답 도출을 위해 그 순간마다 가장 최적의 해를 빠르게 구해야 합니다.이는 정확도는 보장이 안 되지만 빠른 시간 복잡도를 가집니다! Greedy 알고리즘은 정확히 무엇일까요?이 알고리즘은 어떠한 정해진 알고리즘 규격이 아닙니다. 매 순간마다 가장 최적의 해를 도출할 수 있는지가 중요한 것입니다.또한, ..

더보기더보기더보기이 포스트는 활동하는 동아리 내에서 공부한 뒤 작성되었습니다.들어가기 전에,완전 탐색이란 무엇일까요?완전 탐색은 브루트 포스라고 하며, 무식한 알고리즘을 의미합니다.이는 의미 그대로 가능한 모든 경우의 수를 확인하여 최적의 해를 찾는 문제겠지요.100 퍼센트의 정확도를 보장하지만 높은 시간 복잡도를 가지게 됩니다. 일반적으로 완전 탐색은 두 가지 경우 때 필요합니다.결과보다 모든 경우의 수를 찾는 과정 필요한 경우모든 경우의 수를 확인해야 결과 도출이 가능한 경우문제에서 달성하고자 하는 솔루션을 정의한 경우 사용 가능합니다.해결할 수 있는 풀이가 정해져있는 경우(모든 경우의 수가 주어진 경우) 에 사용이 용이합니다. 완전 탐색은 보통 반복문과 조건문을 이용하여 단순하게 구현이 가능합니다...

더보기더보기이 포스트는 활동하는 동아리 내에서 공부한 뒤 작성되었습니다.트리 순회에 알아 보기 전에,트리에 대해 간단하게 설명해 보겠습니다. 트리는 계층이 정해져있는 특수한 그래프입니다.트리는 서브 트리를 자식으로 갖고 있으며, 그래프와 다르게 여러 자식 노드를 가지고 있고 자식 노드는 반드시 하나의 부모 노드를 가집니다.첫 노드는 루트라고 부르며, 각각의 부모 자식 노드의 마지막 노드를 리프 노드라고 합니다. # 트리 순회 방식세 가지로 분류할 수 있습니다.전위 순회중위 순회후위 순회먼저, 전위 순회는 부모 노드부터 왼쪽 자식 노드, 오른쪽 노드 순으로 순회합니다. 전위 순회는 트리를 복사하거나 전위 표기법을 구하기 위해서 사용됩니다.  A   B C D E F 이렇게 구성되어있는 트리에서는 순회 순서..

더보기더보기활동하는 스터디 내에서 공부한 뒤 작성된 포스트입니다.오늘은 투 포인터 알고리즘에 대해 설명해 보겠습니다.투 포인터 알고리즘을 배우려면 누적합의 개념에 대해서도 알고 가면 좋기 때문에,이 포스트에서 누적합과 투 포인터 두 가지 개념에 대해 설명하겠습니다. # 투 포인터먼저 투 포인터에 대해 알아 보겠습니다. 일련적인 배열에서 연속적인 값을 표현할 때는 구간으로 해당 영역의 표현이 가능합니다.예를 들어 2 부터 7 인덱스는 2, 3, 4, 5, 6, 7 로 표현하지만 시작점과 끝점을 이용하여 2 부터 7 인덱스로 표현이 가능합니다.  투 포인터 알고리즘으 구간의 개념을 이용한 알고리즘입니다.PS 에서 배열을 순회하여 특정 조건을 찾는 문제가 있습니다.하지만 배열을 순회하며 너무 많은 연산을 진행..

더보기더보기활동하는 스터디 내에서 공부한 뒤 작성된 포스트입니다.이번 포스트에서는 소수 판별 알고리즘에 대해 간단히 작성해 보겠습니다.소수 판별 알고리즘을 알아 보기 위해서는 소수가 무엇인지 알아보아야겠죠? # 소수소수는 1과 자기 자신 외에는 나누어떨어지지 않는 자연수로 정의됩니다.즉, 1 과 자기 자신만을 약수로 갖는 숫자입니다.예를 들어 5 의 약수를 찾아 보면 1 과 5 가 나옵니다. 그렇다면 5 는 소수가 되는 것입니다. 그럼 1 은 소수일까요?아닙니다. 1은 자기 자신 외에 다른 약수가 없기에 소수라고 할 수 없습니다. 따라서 소수 판별을 하기 위해서는  1 과 자기자신을 제외한 수로 나뉘어지지 않은 수를 찾으면 됩니다. # 기본 소수 판별 방법간단히 설명해 보자면,2 부터 자기 자신 이전까지..