Algorithm & Data Structure

그래프 그래프는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 데이터 구조이다. 그래프의 종류무방향 그래프(Undirected Graph)간선에 방향이 없는 그래프로, 두 정점 사이의 연결이 쌍방향으로 되어있다.방향 그래프(Directed Graph)간선에 방향이 있는 그래프로, 한 정점에서 다른 정점으로의 방향이 정해져 있다.비가중치 그래프(Unweighted Graph)간선에 가중치(비용, 거리 등)가 없는 그래프이다.가중치 그래프(Weighted Graph)간선에 가중치가 할당된 그래프이다.이 외에도 순환 그래프(Cyclic Graph), 비순환 그래프(Acyclic Graph) 등이 존재한다. 인접 행렬(Adjacency Matrix) 인접 행렬은 각 정점들이 연결되어 있는 정보를 ..

유클리드 호제법 public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } public static int lcm(int a, int b) { return (a * b) / gcd(a, b); }

소수 1과 자기 자신을 제외한 자연수들을 약수로 갖고 있지 않은 수이다. (ex : 2, 3, 5, 7 ...) 제곱근을 이용한 방식 public boolean isPrime(long num) { if (num == 1) { return false; } for (int i = 2; i  에라토스테네스의 체를 이용한 방식import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..

들어가며 백준 3273번 문제를 해결하려는 데 2중 for문으로 코드를 짜서 제출하면 시간 초과가 나서 이에 대한 해결방안을 알아보게 되었다. 투 포인터(Two Pointers)로 해결하면 쉽게 해결할 수 있다는 것을 알고 이에 대해 설명한다. 투 포인터란? 투 포인터(Two Pointers)는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘을 말한다. 이처럼 두 개의 포인터를 사용하면 반복문을 여러번 시행하는 것 보다 시간을 효율적으로 사용할 수 있다. 최악의 경우에도 두 개의 포인터가 배열의 마지막 인덱스로 오게 된다. 따라서 시간 복잡도는 O(n)이다. 투 포인터 알고리즘 백준 2003번 문제를 예시로 알고리즘을 이해해보자. 이 문제에서는 N까지의 배열이 있고 부분합이 M이 ..

들어가며 DFS는 앞에서 배운 BFS처럼 탐색 알고리즘 중 하나이다. BFS와 구현의 차이점이 있다면 BFS에서는 Queue(큐)를 사용 했지만, DFS에서는 Stack(스택)을 사용해서 구현한다. DFS(깊이 우선 탐색) 이란? 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. - 위키백과 DFS 알고리즘 아래의 사진들을 보고 DFS를 이해해보자. 시작 지점을 1이라고 하자. 1을 방문했다는 표시를 ..

들어가며 BFS는 코딩테스트에 자주 사용되는 알고리즘이다. Flood Fill과 같은 문제들을 해결하는 데 사용할 수 있다. 이를 구현하기 위해서는 Queue(큐)를 사용한다! BFS(너비 우선 탐색) 이란? 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. - 위키백과 BFS 알고리즘 아래의 사진들을 보고 BFS를 이해해보자. 시작 지점이 1이라고 하자. 그러면 1에 방문했다는 표시를 남기고 해당 칸을 큐에..

들어가며 이번에는 스택을 활용하여 수식의 괄호 쌍을 검사하는 알고리즘에 대해 알아보자! 수식의 괄호 쌍 예시 ( { { ) } } -> 올바르지 않은 식 ( ( ) ) -> 올바른 식 수식의 괄호 쌍 해결 알고리즘 여는 괄호가 나오면 스택에 추가한다. 닫는 괄호가 나왔을 때 아래의 3가지 방법으로 처리한다. 스택이 비어있으면 올바르지 않은 괄호 쌍이다. 스택의 top과 짝이 맞지 않는 괄호라면 올바르지 않은 괄호 쌍이다. 스택의 top과 짝이 맞는 괄호라면 pop한다. 위의 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍이고, 반대로 스택에 괄호가 남아있지 않다면 올바른 괄호 쌍이다. 문제 해결 아래는 백준(BOJ) 4949번 균형잡힌 세상을 위의 알고리즘을 이용해 해결한 코드이다. ht..

들어가며 덱(Deque)은 Double Ended Queue의 약자로 큐에 양쪽 끝에서 원소를 추가하거나 삭제를 할 수 있는 자료구조이다. 그리고 C++ STL에 덱이 구현되어 있어 쉽게 이용할 수 있다! 덱(Deque) 이란? 덱(deque, "deck"과 발음이 같음 ← double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. - 위키백과 덱 덱에 대해서 아래의 사진을 보고 이해해보자. 위 사진을 보면 원소 32를 back에 넣어서 덱 안에 원소가 5, 17, 32가 들어있게 된다. 여기서 front에 있는 원소 5를 제거하면 덱 안에 17,..