백준

[Java] 백준 1967번 - 트리의 지름

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net [ 1 ] 풀이 및 소스코드 - 트리의 지름은 모든 노드에 대해 DFS를 하여 트리에 존재하는 모든 경로 중 가장 긴 것(가중치가 큰 경로)을 찾음으로써 구할 수 있다. - 각 노드마다 DFS를 통해 연결된 노드들의 가중치를 더해가며 distance를 구하고, max를 업데이트 해 준다. - 모든 노드에 대해 DFS를 실행한 후의 max 값이 트리의 지름이 된다. - 각 노드와..

[알고리즘/Java] 투 포인터(Two Pointers)

[ 1 ] 기본내용 "투 포인터"는 1차원 배열에서 각기 다른 원소를 가리키는 2개의 포인터를 활용하여 원하는 값을 얻는 알고리즘이다. 이때, 포인터는 C/C++에서의 포인터가 아닌 배열에서의 "인덱스"를 의미한다. 2개의 포인터를 적절히 이동시키며 시간 복잡도를 최적화할 수 있는 것이 투 포인터 알고리즘의 핵심이다. 투 포인터가 자주 활용되는 문제로는 (1) target 값을 미리 설정하고, 특정 배열 내에 target 값과 같은 - 유사한 부분 합이 몇 개 존재하는지 계산하는 문제 (2) 배열 내 target = arr[i] + arr[j] 를 만족하는 (i, j) 쌍이 몇 개 존재하는지 계산하는 문제 등이 있다. [ 2 ] 부분 합에서의 투 포인터 해당 내용은 대표 예제인 백준 2003번을 통해 살..

[알고리즘/Java] 구간 합(Prefix Sum)과 관련 예제(BOJ-11659)

[ 1 ] 정수 배열 A에서 특정 구간(i ~ j) 내 모든 원소의 합을 구하라 특정 배열이 주어지고 위와 같은 질문을 받는다면, 우리는 어떻게 특정 구간 내 모든 원소의 합을 구할 수 있을까? 시간 제한이 없고 배열 원소의 수가 적다면 단순히 선형 탐색으로 i ~ j 까지의 특정 구간 내 원소의 합을 구할 수 있을 것이다. 하지만, 배열 내 원소의 수가 매우 많고, 계산해야 할 특정 구간도 많이 주어진다면 위와 같은 선형 탐색은 오랜 시간이 소요될 것이다. [ 2 ] 구간 합(Prefix Sum) [2 - 1] 정의 구간 합 알고리즘을 활용하면 선형 탐색으로 O(n)이 소요되던 시간 복잡도를 O(1)으로 줄일 수 있다. 어떻게 이것이 가능한가? 우선 A라는 정수 배열이 있을 때 S라는 '합 배열'을 정..

[C/C++] 백준 7576번

문제출처: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [ 문제 ] 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익..

[C/C++] 백준 2263번

문제출처: https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net [ 문제 ] n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. [ 입력 ] 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. [ 출력 ] 첫째 줄에 프리오더를 출..

[C/C++] 백준 1655번

문제출처: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net [ 문제 ] 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면,..

[자료구조/C++] 우선순위 큐

[ 1 ] 기본내용 우선순위 큐(Priority Queue)란 First-In First-Out(FIFO) 구조를 따르는 일반적인 큐와 달리 힙(heap)을 활용하여 원소들의 우선순위를 설정하고, 우선순위에 따라 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조이다. 단, 최대 or 최소 둘 중 하나에 대해서만 우선순위를 적용할 수 있으며 최댓값을 우선순위로 둘 경우 최대 힙(Max heap), 최솟값을 우선순위로 둘 경우 최소 힙(Min heap)이라 한다. [ 2 ] C++에서의 우선순위 큐 [ 2 -1 ] 헤더파일 C++에서는 container adaptor로서 priority_queue를 제공하고 있으며, vector를 기본 컨테이너로 사용한다. priority_queue를 사용하..

[C/C++] 백준 5430번

문제출처: https://www.acmicpc.net/problem/5430 [ 문제 ] 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. [ 입력..