Step-by-Step

그래프(Graph) 정점(Vertex)와 간선(Edge)로 구성된 자료구조 그래프 G는 꼭짓점의 집합 V와 변의 집합 E의 순서쌍으로 정의된다 G = ( V , E ) 그래프 용어 정점(vetex) : 노드(node)라고 불리며 데이터가 저장되는 장소 간선(edge) : 링크, arcs 라고 불리며 노드간의 관계를 나타냄 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수 단순 경로(simple path) : 경로 중 반복되는 정점이 없는 경우 사이클(..

여러 알고리즘 유형들을 파악하기 앞서 알고리즘이라는 것에 대해 정리해보려고 한다 알고리즘 (Algorithm) 문제를 해결하기 위한 절차나 방법 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set) 반복되는 문제를 풀기 위한 작은 프로시저(procedure;진행절차) 알고리즘 조건 알고리즘은 아래의 조건을 만족해야 한다 입력 - 알고리즘은 0 도는 그 이상의 외부에서 제공된 자료가 존재한다 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다 효과성 - 알고리즘의 모든 연산들은 사람이 유한한 시간 내 정확하게 수행할 수 있을정도로 충분히..

하노이의 탑 (Tower of Hanoi) 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여있다 아래 두 가지 조건을 만족시키며 탑 전체를 다른 기둥으로 옮겨 다시 쌓는 게임이다 1. 한 번에 한 개의 원판만 옮길 수 있다 2. 큰 원판이 작은 원판 위에 있어서는 안 된다 원리 알고리즘 강의를 들을때 분명 배웠던 내용이지만 (머리가 기억하지 못하니ㅠ_ㅠ ) 다시 공부를 했다 글만 보고는 원리를 한 번에 이해하기 힘들기 때문에 글을 읽은 다음 항상 영상을 찾아보곤 한다 재귀함수랑 하노이의 탑을 이해하기 위해 봤는데 도움이 많이 되었다 [출처:얄팍한 코딩사전] https://www.youtube.com/wat..

에라토스테네스의 체 (Sieve of Eratosthenes) 고대 그리스 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 불림 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법 수학 공식 : f(x)=1P​(x)x​ 원리 시작 전 간단하게 이해하기 위해 아래 2분 30초짜리 영상으로 확인해보자 [출처:비상교육] https://www.youtube.com/watch?v=G1_6A9Ifi3o 1. 1~100까지의 수가 있음 2. 1은 소수가 아니므로 걸러냄 3. 소수 2는 남기고, 2의 배수(짝수)는 모두 걸러냄 4. 소수 3을 남기고 3의 배수를 모두 걸러냄 => 계속 반복 후 남은 숫자들이 소수임 에라토스테네스..