모듈러 연산 (나머지 연산)은 알고리즘에서 자주 쓰이는 개념입니다.모듈러 연산은 정수론에서 나온 개념이라 깊게 이해하려면 정수론을 조금 들여봐야하나, 지금의 저는 수학자가 아니에요. 간단하게 개념들만 알아봅시다.모듈러 연산(%) 이란?나머지를 구하는 연산.10 % 3 == 1 -> 10을 3으로 나누었을 때의 나머지, 즉 14 % 2 == 0 -> 4를 2로 나누었을 때의 나머지, 즉 0 혹은 %를 mod 라고 표현하기도 합니다.10 mod 3 == 14 mod 2 == 0 모듈러 연산의 합동 법칙 (Modular congruent)어떤 두 정수 a, b가 모듈러 m에 대해 합동이라면, 아래와 같이 나타낼 수 있습니다.a ≡ b (mod m) 이를 더 풀어서 설명하면, 결국 모듈러 연산에서 합동이란 같은..

완전 탐색 (brute force, exhausitive key search)완전 탐색은 모든 경우의 수를 탐색하는 알고리즘입니다. (즉, 노가다)경우의 수란? 순열 또는 조합을 의미합니다.그래서 완전 탐색은 보통 조합/순열 + 로직(DFS/BFS) 로 이루어져 있습니다.  그럼 언제, 완전탐색을 사용해도 될까요? 아주 명확하고 간단하게 정리하면 다음과 같습니다.시간복잡도가 1억 미만일 때! 즉, 대략 총 계산 횟수가 1억 미만이면 완전탐색으로 풀면 됩니다. (대부분 시간 제한이 1초이므로)그러나 1억 이상인 경우에는? 다른 방법이 떠오르지 않으면 완전 탐색을 사용하긴 하되, 의심하긴 해야합니다.   완전탐색의 구현 방법 2가지 (반복문 vs 재귀함수)만약 2가지 방법 모두로 풀 수 있다면, 무조건 반복..

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적이 방법으로 방문하는 과정을 트리 순회라고 합니다.일단 설명을 위해, 공통적으로 사용할 하나의 예시 그림을 제시하겠습니다.  후위 순회 (postorder traversal)자식 노드들을 먼저 방문하고, 본인 노드를 방문하는 방식입니다. (자식 노드들은 보통 왼쪽 -> 오른쪽 순서)//pseudo codepostorder( node ) if (node.visited == false) postorder( node->left ) postorder( node->right ) node.visited = true  직접 코드로 구현해보겠습니다. void postOrder(int here){ if(visited[he..

저번에는 DFS를 다루었으니, 이젠 그래프 탐색 알고리즘 중 BFS를 다뤄봅시다 ! BFS (Breadth First Search)너비우선탐색, 특정 노드부터 시작해 다음 깊이의 노드로 이동하기 전에 현재 깊이의 모든 정점을 탐색합니다.이때, 방문한 정점은 다시 방문하지 않으며 보통 "같은" 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰입니다. pseudocode (수도코드 - 의사코드) - 2가지 버전이 존재합니다. ver1. 방문처리만 하는 BFS 코드BFS(G, u) u.visited = true q.push(u); while(q.size()) u = q.front() q.pop() for each v ∈ G.Adj[u] ..

그동안 3개의 포스팅을 통해 그래프를 다뤘습니다. 이제 그래프를 탐색하는 알고리즘 중 가장 유명한 DFS, BFS 중 DFS 먼저 다뤄봅시다.DFS (Depth First Search)깊이우선탐색, 특정 노드부터 시작해 인접한 노드들을 재귀적으로 방문합니다.이때, 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색합니다.(분기란? : 2개 이상으로 정점이 쪼개지는 지점)  pseudocode (수도코드 - 의사코드)DFS(u, adj) u.visited = true for each v ∈ adj[u] if v.visited == false DFS(v, adj) 시작 정점 u부터 방문하여, u와 인접한 모든 노드들에 대해 방문하지..

종종 알고리즘 문제에서 그래프가 맵으로 주어지는 경우가 존재합니다.이런 형태로요! 이렇게 주어진 맵은 그 맵을 기준으로 탐색을 이어가야만 합니다.굳이 인접리스트나, 인접행렬로 바꾸려고 하면 머리만 아파요! 아, 그리고 위에서 주어진 표는 인접 행렬이 아니라 맵임을 명심하세요. 위의 맵에서 1은 갈 수 있는 지역, 0은 갈 수 없는 지역이라고 합시다. (육지 == 1 && 바다 == 0 혹은 길 == 1 && 벽 == 0 등등의 예시)그럼 이걸 그래프로 표현하면 아래와 같은 모습이 됩니다.   4방향 탐색과 방향 벡터4방향 탐색은 위, 아래, 오른쪽, 왼쪽을 탐색하는 것을 의미합니다. 그리고 보통 (y,x) 로 표현하곤 합니다. → 행, 열을 표현하기에 더욱 적합하기 때문아래의 그림에서, dy, dx는 방..

저번 포스트에서는 그래프에 대한 전반적인 개념을 살펴봤습니다.그럼 그래프는 컴퓨터로 어떻게 구현할 수 있을까요? 그래프에서 가장 중요한 2가지 개념을 뽑는다면 정점과 간선이었습니다.그럼 컴퓨터로 구현하려면, 정점과 간선의 관계를 나타내는 자료구조가 필요하겠네요!바로 인접 행렬과 인접 리스트입니다. 일단 예시를 하나 들어보도록 하겠습니다.  인접 행렬 ( adjacency matrix )위의 예시는 아래의 표로 나타낼 수 있습니다.  i / j012300111110102110031000 형식이 대략 이해가 가시나요? 2차원 배열의 형식(행렬)로 표현을 했는데,a[i][j] 는 i번 노드에서 j번 노드로 향하는 경로(간선)이 있는지를 알려줍니다. 예를 들어, a[0][1] == 1 이므로 0번에서 1번으로 ..

그래프이론은 오일러경로, SCC, 단절점 등 어려운 개념과 넓은 범위를 다루는 이론이지만,해당 포스트에서는 그래프의 기초에 대해 다뤄보도록 하겠습니다. 우선 그래프의 기초 요소에 대해 알아봅시다.Graph, Vertex, Edge, WeightVertex (정점) : 하나의 지점Edge (간선) : 정점을 잇는 선 - 즉 경로Weight (가중치) : 간선에 부여된 값 (일종의 비용)정점과 간선의 대표적 예시는 지하철 노선도를 들 수 있겠네요. 지하철 역 = Vertex,역 사이의 경로 = Edge,경로를 지날 때 걸리는 시간(or 경로 교통비) = Weight 간선은 단방향 간선, 양방향 간선으로 분류되기도 합니다.또한 그래프 자체는 Undirected Graph 와 Directed Graph 로 분리..