뽀루피의 개발스토리

트리의 순회 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 문제이다.인오더는 중위 순회를, 포스트오더는 후위 순회를, 프리오더는 전위 순회를 의미한다.중위 순회는 left -> root -> right 순으로 순회,후위 순회는 left -> right -> root 순으로 순회,전위 순회는 root -> left -> right 순으로 순회하는 것이다. 이 문제는 중위 순회와 후위 순회의 특징을 이용해 트리의 구조를 파악하여 푸는 문제이다.중위 순회와 후위 순회의 공통 부분은 left부터 순회를 시작하는 것. 즉, 순회 시작부분은 둘이 같다. 후위 순회의 경우 가장 마지막 순회 노드가 루트 노드이고,중위 순회는 루트노드가 왼쪽 트리와 오른쪽 트리를 나누는 중간 노드이므로,후위 순회를 ..

위상정렬위상정렬은 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)에서 순서를 정렬하는 알고리즘이다. 위상정렬을 구현하기 위해서는 4가지 변수를 만들어줘야 한다.int[] indegree : 특정 노드에 대해서 다른 노드로부터 들어오는 간선의 개수List> array : 그래프의 간선 정보를 담은 2차원 리스트Queue q : indegree 값이 0이 된 노드들을 담기 위한 queueQueue result : 정렬된 순서를 보여줄 결과 queue. q에서 빠져나온 순서대로 정렬된다. 1. 맨 처음 indegree 값이 0인 노드들을 Queue에 담고 시작한다. 2. Queue에서 노드 1을 빼주며 1에서 가르킨 노드들의 indegree 값을 1씩 감소시킨다.즉, ..

나머지(모듈러) 연산나머지를 구하는 연산으로 예를 들어, 두 정수 A, B에 대해서 A를 B로 나누어서 C가 나왔다면A % B = C 또는 A mod B = C 이다. 나머지(모듈러) 연산에는 덧셈, 뺄셈, 곱셈 성질이 있다.덧셈 성질(A+B) mod C = (A mod C + B mod C) mod C뺄셈 성질(A-B) mod C = (A mod C - B mod C) mod C곱셈 성질(A*B) mod C = ((A mod C) * (B mod C)) mod C  우리는 이러한 성질을 이용해 int의 범위를 넘어서는 값을 int로 표현할 수 있거나 큰 값을 계산할 경우 분할정복을 통해 간단하게 표현할 수 있다. '백준 1629번 문제 곱셈' 이 이러한 성질을 이용한 문제이다.  백준 1629 곱셈ht..

BFS (너비 우선 탐색) BFS는 위의 그림과 같이 점차 탐색 영역을 확장시켜 나가는 알고리즘이다.BFS는 그래프 탐색 문제에 적합한 알고리즘인데 이번에 풀어본 아기상어가 그래프 탐색 문제이다.  BFS의 원리는 간단하다.1. Queue 자료구조에 그래프에서 현재 위치를 넣어준다.2. 방문했던 곳을 다시 가지 않도록 방문처리를 해준다.3. Queue에서 하나씩 Poll한다.4. Poll한 위치에서 이동할 수 있는 그래프의 위치들을 탐색하고 이를 또 Queue에 Add한다.5-1. 탐색 도중 조건에 맞는 위치가 나온다면 성공한 결과값과 함께 BFS 종료,5-2. Queue에 더 이상 이동할 위치가 남아있지 않다면 실패 결과값과 함께 BFS 종료  기본 형태는 다음과 같다.static boolean bfs..

https://www.acmicpc.net/problem/1167 트리에서 임의의 두 점 사이의 거리 중 가장 긴 거리를 구하는 문제다.트리의 정점의 개수 V가 주어지고 V개의 줄에 걸쳐 간선의 정보가 주어졌다. 이 문제를 풀기 위해 플로이드-워셜 등의 방법을 잠시나마 생각해봤지만 100,000개의 정점을 삼중 반복문으로 돌릴 생각을 하니 안 된다는 것을 깨닫기까지 그렇게 오래걸리지 않았다. 결국 트리의 지름 공식을 알아야 풀 수 있는 문제였다.트리의 지름 공식은 다음과 같다. 1. 임의의 점 A에서 가장 먼 지점 B를 찾는다.2. B에서 가장 먼 지점 C를 찾는다.3. B ~ C의 거리가 트리의 지름이다. 이 공식만 이용한다면 어렵지 않게 풀 수 있다.import java.io.*;import java..

정의플로이드-워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.시간복잡도는 O(N^3)이다. 음의 가중치를 가지는 그래프에서도 사용할 수 있다는 점이 다익스트라 알고리즘과 다른 특징.   설명임의의 노드 Start 에서 End까지 가는데 최단 거리를 구하기 위해 Start와 End 사이의 노드인 Mid에 대해 Start에서부터 Mid까지의 최단 거리와 Mid에서부터 End까지의 최단 거리를 전부 고려하는 것이 플로이드-워셜 알고리즘이다. 방법은 다음과 같다.시작 노드와 도착 노드의 가중치를 담은 2차원 배열 arr,s는 start 노드의 약자, e는 end 노드의 약자, m는 middle 노드의 약자라고 할 때,if(arr[s][e] > arr[s][m] + arr[..