뽀루피의 개발스토리

트리의 순회 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 문제이다.인오더는 중위 순회를, 포스트오더는 후위 순회를, 프리오더는 전위 순회를 의미한다.중위 순회는 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..

누적합누적합의 예제부터 살펴보자 [1, 2, 3, 4, 5] 배열이 있다고 할 때 각 구간까지의 합을 구하는 배열 [1, 3, 6, 10, 15]를 구한다고 가정해보면 두 가지 방법을 생각해볼 수 있다. 1. 완전 탐색으로 더하기11+21+2+31+2+3+41+2+3+4+5 2. 누적합을 이용한 더하기11+23+36+410+5 2가지 방법을 비교하면 2번째 방법이 효율적임을 알 수 있다. 누적합은 이처럼 시작점부터 n번째 원소까지 앞에서부터 누적으로 합해오는 알고리즘이다.모든 구간을 반복해서 더하는 것보다 이전 인덱스까지의 누적합에 현재 인덱스를 더하여 구현하는 것이 효과적인 방법이다. 큰 계산을 작게 효율적으로 만든다는 점에서 DP와도 상통하는 부분이 있다.누적합 알고리즘은 A~B 범위의 구간 합을 구..

투포인터1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘이다.  위의 예시처럼 2개의 포인터를 옮김으로써 이루어진다.완전탐색에 비해 시간복잡도를 많이 아낄 수 있다.while (start  코드 예시이다. while문 내에 탈출 조건문과 포인터를 옮겨주는 조건, 얼마나 옮길건지를 작성해주면 완성이다.어찌보면 for문에서 인덱스 초기 조건, 반복문 탈출 조건, 인덱스 이동을 작성하는 것과 같이 이루어지는데 다른 부분이라면 문법이 아닌 내가 직접 구현한다는데 차이점이 있는 것 같다.   백준 1806 부분합길이가 N인 수열이 주어지고 합이 S 이상인 부분합들 중 최단 길이를 구하라는 문제였다.문제를 읽었을 때 부분합이라는 단어와 길이가 ..

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[..