Algorithm & Data Structure/이론7

• 

  [Algorithm] 위상정렬(Topological Sort)을 Java로 구현해보자!! 안녕하세요 Coding-Knowjam입니다. 오늘은 그래프 알고리즘인 위상 정렬을 Java로 구현해보겠습니다. 1. 위상 정렬(Topological Sort)이란? 1.1 개념 우리가 알고리즘을 공부할 때 그래프에 관련된 문제를 많이 접하게 됩니다. 위상 정렬(Topological Sort) 또한 그래프와 관련된 알고리즘 중 하나입니다. 그렇다면 위상 정렬(Topological Sort)은 언제 사용할까요?? 바로 선후관계가 정의된 그래프 구조에서 정렬을 하기 위해 사용할 수 있습니다. 글로만 보면 이해가 잘 되지 않으실 테니 그림과 함께 설명하겠습니다. 위와 같은 그래프가 있을 때, 노드마다 연결된 간선에 방향이 있고 어떤 특정 노드를 방문하기 위해서는 해당 노드에 진입 가능한 노드들을 모두 방문한 후.. Algorithm & Data Structure/이론 2021. 7. 31.

• [Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609) 안녕하세요 Coding-Knowjam입니다. 오늘은 유클리드 호제법에 대해서 알아보고 코드로 구현해보겠습니다. 그리고 추가적으로 백준 온라인 저지에 있는 BOJ 2609번 최대공약수 문제도 같이 풀어보겠습니다. 1. 유클리드 호제법이란? (Euclidean Algorithm) 1.1 개념 유클리드 호제법은 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다. 일반적으로 우리가 수학을 배울 때, 두 수 사이의 최대공약수는 소인수분해를 하고 소인수들의 곱으로 구할 수 있었습니다. 소인수분해를 물론 코드로 구현할 수는 있겠지만 효율적이지는 않을 겁니다. 왜냐하면 우선 소인수분해를 위해 소수를 먼저 찾아야 하고, 찾은 소수가 두 개의 수를 공통적으로 나눌 수 있는지를 확인을 해야 하기 때문입니다. 만.. Algorithm & Data Structure/이론 2021. 7. 21.

• [Algorithm] 세그먼트 트리(Segment Tree)를 Java로 구현해보자! !(with BOJ-2042 Java로 문제풀이) 안녕하세요 Coding-Knowjam입니다. 오늘은 세그먼트 트리를 Java로 구현해보도록 하겠습니다. 1. 세그먼트 트리 (Segment Tree) 세그먼트 트리는 이름에서도 나타나듯이 트리 형태의 자료구조를 사용합니다. 숫자가 저장된 배열이 존재할 때 해당 배열의 구간 합을 구하거나, 배열의 특정 인덱스의 값을 변경한 후에 다시 구간합을 구해야 한다면 세그먼트 트리를 사용하는 것이 시간 복잡도 측면에서 적합합니다. 세그먼트 트리에 대한 이론적인 설명은 백준 온라인 저지에 있는 게시물에 명쾌하게 정리가 되어있습니다. 그러므로 해당 게시글을 꼭 읽어보시길 바라며 세그먼트 트리가 무엇인지는 대충 아신다는 전제하에 Java로 코드를 구현해보겠습니다. 구현 코드는 예제를 들어서 해도 되지만 백준 온라인 저지에.. Algorithm & Data Structure/이론 2021. 6. 13.

• 

  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) 안녕하세요 Coding-Knowjam입니다. 오늘은 다익스트라(Dijkstra) 알고리즘을 알아보겠습니다. 이론과 더불어 실제 구현을 백준 온라인 저지에 있는 문제풀이와 함께 할 예정이므로 문제를 미리 읽고 오시길 바라겠습니다. https://www.acmicpc.net/problem/1753 1. 다익스트라(Dikstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 방향성을 가지는 그래프에서 최단거리를 구할 때 자주 쓰입니다. 방향성을 가지는 그래프란 A에서 B노드로 이동은 가능하지만, B노드에서 A노드로는 이동할 수 없는 경우가 있는 그래프를 말합니다. 즉, 노드 간의 연결된 간선이 방향과 거리 비용을 가지고 있고, 시작 노드에서 다른 노드들까지의 최단거리 비용을 구할 때 사용할 수 있습니.. Algorithm & Data Structure/이론 2021. 4. 20.

• 

  [Algorithm] DFS (Depth-first Search)를 Java로 구현해보자! 안녕하세요 Coding-Knowjam입니다. 오늘은 그래프와 트리를 탐색할 때 사용되는 DFS알고리즘에 대해서 알아보겠습니다. 1. DFS (Depth-first Search)란? DFS는 번역하면 깊이 우선 탐색이라고 합니다. 이름에서도 알 수 있듯이 연결된 노드를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들을 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색을 합니다. 사실 글로 설명하기는 좀 애매해서 그림과 같이 설명을 드리겠습니다. 위와 같은 그래프가 존재한다고 하고, 1번 노드부터 DFS탐색을 시작해보겠습니다. 1번 노드 방문처리 후 출력 (탐색 순서 : 1) 1번 노드에 인접한 노드 2번, 3번, 8번 중 하나를 방문해야 하는데 오름차순으로 방문하기로 가정하겠습니다. 2.. Algorithm & Data Structure/이론 2021. 4. 16.

• 

  [Algorithm] BFS(Breadth-first search)를 Java로 구현해보자! 안녕하세요 코딩노잼입니다. 오늘은 BFS(너비 우선 탐색)을 Java로 구현해보겠습니다. 1. BFS (Breadth-first Search) BFS는 너비 우선 탐색이라고 부르기도 하며, 코딩 테스트에서 자주 등장하는 알고리즘 중에 하나입니다. 기본적으로 그래프 탐색에 사용되며, 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. BFS는 큐(Queue) 자료구조를 사용해서 구현할 수 있습니다. 글로만 보면 이해가 어려우실 테니 그림과 같이 보겠습니다. 위와 같은 그래프가 존재하고 노드의 탐색은 1번부터 시작한다고 가정해보겠습니다. 1. 큐에 1번 노드를 넣고 방문 처리합니다. (여기서 방문처리라는 것은 내가 해당 노드에 방문했음을 기록하는 것입니다.) 2. 1번 노드와 가까운 노드를 큐에 넣고 방문 .. Algorithm & Data Structure/이론 2021. 4. 11.

• 

  [Algorithm] Trie를 Java로 구현해보자! 안녕하세요 coding-knowjam입니다. 오늘은 검색할 때 O(N)의 시간 복잡도를 가지는 Trie를 구현해보겠습니다. 1. Trie란? Trie는 일반적인 Tree자료구조와 같은 모양이지만 저장하는 값이 다른 형태입니다. 정수형을 저장하는 Tree가 아래와 같은 모양으로 있다고 가정하겠습니다. 위와 같은 정수형 자료의 이진트리에서는 검색을 수행할 때 O(logN)의 시간 복잡도를 가지게 됩니다. 그러나 같은 이진트리 형태 이어도 문자열을 저장하고 있다면 문자열의 길이가 M일 때, O(M*logN)의 시간 복잡도를 가지게 됩니다. 이러한 문제를 해결하기 위해 Trie를 사용하게 됩니다. Trie는 문자열 전체를 하나의 노드에 저장하는 게 아니라, 한 단어씩 노드에 저장하는 트리입니다. Trie는 루트.. Algorithm & Data Structure/이론 2021. 4. 10.