최대공약수를 구할 때 사용되는 알고리즘으로 이를 활용한 알고리즘 문제들이 정말 많기 때문에 한번 정리하고 넘어가려 한다. 먼저 참조 문서를 보고 오겠다. 공부할땐 위키백과만한게 없다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 ko.wikipedia.org 요약하자면 최대공약수를 구하려는 수 a ,b 가 있다면 (a > b..
이번 포스팅에서는 비선형 자료구조인 트리중 이진트리에 대해 다뤄보겠다. 우선 비선형 자료구조란 무엇인가 정의를 살펴보면, 비순차적인 성질을 지닌 자료들을 표현하는데 적합한 구조. 라고 명시 되어있다. 이런 비선형 자료구조에는 그래프와 트리로 나뉘고 이번에 다룰 이진 트리는 이런 트리의 일종이다. 트리의 정의는 하단의 링크를 참조하도록 하겠다. https://terms.naver.com/entry.naver?docId=2270428&cid=51173&categoryId=51173 트리 트리(tree) 구조는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합하다. 계층 구조의 대표적인 예가 회사 또는 대학의 조직도인데 다음은 J 대학의 조직도 일부를 나타낸 것이다. 다음은 [ terms.naver.com ..
이번 포스팅에서는 지난 포스팅 스택의 구현에 이어서 마찬가지로 가장 많이 쓰이는 자료구조중 하나인 큐에 대해서 알아보고 구현해보도록 하겠다. 우선 큐의 사전적인 정의를 살펴보도록 하겠다. https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 큐 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬 ko.wikipedia.org 큐는 FIFO first in first out 즉 선입선출(先入先出)의 구..
이번 포스팅에서는 가장 많이 쓰이는 자료구조중 하나인 스택에 대해서 알아보고 구현해 보도록 하겠다. 우선 사전적인 정의를 한번 보고오도록 하겠다. https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D 스택 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 스택의 구조 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 ko.wikipedia.org 사전적인 정의에 대해서는 굳이 다시 옮겨 적진 않겠다. 중점적으로 볼것은 FILO , LIFO 구조 라는것이다. fisrt in last out, last in first out 즉 선입후출(先入後..
BFS는 DFS와 더불어 그래프 이론의 가장 기본적인 탐색기법중 하나로, 그래프의 너비를 우선하여 탐색하는 알고리즘이다. 간단한 그래프를 예시로 들어 설명해보겠다. 다음과 같은 그래프가 있다고 가정하고 1번 정점부터 탐색을 시작한다고 할때, 너비우선탐색을 실행하면 1 >> 2 >> 3 >> 4 >> 5 >> 6 >> 7 >> 8 순으로 탐색을 진행한다. 보다 자세한 과정을 설명하자면 다음과 같다. 1. 현재 정점을 방문처리후 큐에 삽입한다. 2. 큐에서 정점을 꺼내고 정점과 연결된 다른 정점중 방문하지 않은 정점을 현재 정점 취급한다. 3. 1, 2 과정을 큐가 빌때까지 반복한다. 조금 더 자세한 과정의 설명을 위해 위의 그래프를 예시로 들어 보겠다. 꺼낸 정점은 현재 '1' 이므로 '1' 과 연결되어있..