본문 바로가기

백준_JAVA46

[백준] 1991번 - 트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리란 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2개로 제한되어 있는 트리구조로 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 부른다. 트리를 사용하는 경우 보통은 트리를 순회하며 찾고자 하는 값을 탐색하기 때문에 해당 자료구조를 사용하기 위해서 순회하는 방법에 대해서는 기본적으로 알아두면 좋다. 트리를 순회하는 방법은 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(pos.. 2023. 5. 25.
[백준] 6497번 - 전력난 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제는 전력난에 허덕이는 도시의 시장이 모든 길로 통하도록 하면서 최소 비용으로 가로등을 켤 때 절약할 수 있는 최대 액수를 구하라고 말한다. 문제 조건을 보면 도시는 항상 연결 그래프 형태이고 거리는 양방향 도로이다. 거리가 양방향 그래프이기 때문에 방향은 고려하지 않아도 되기에 무방향 그래프라고 생각해도 된다. 또한 도시상의 모든 길의 거리 합은 2^31 미터 보다 작다고 하였으므로 변수에 int 자료형을 사용해도 문제없다. 집을 정점, 집과 집 사이의 도로를 간선 그.. 2023. 5. 24.
[백준] 1717번 - 집합의 표현 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드 개념을 이해하고 적용해볼 수 있는 문제이다. 유니온 파인드 개념은 아래 글을 참고하자. [알고리즘] 유니온 파인드(Union Find) Union Find - 유니온 파인드 - 그래프 자료구조에서 주로 사용하는 알고리즘 - 두 노드가 같은 그래프에 속하는지 판별 - 서로소 집합(Disjoin-Set)으로도 불린다. - 노드를 합치는 Uion 연산과 노드의 루 stonage.tistory.com 유니온 파인드는 .. 2023. 5. 24.
[백준] 1197번 - 최소 스패닝 트리 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 프로그래머스 섬 연결하기와 동일한 문제이다. [프로그래머스] 섬 연결하기 처음 시도 했을 때에는 쉽게 풀릴 것 같았다. 첫 번째 시도에는 costs 에서 가중치 기준 오름차순 정렬하여 단순하게 가중치가 작은 간선만을 연결하며 방문처리 하는 방식으로 구현하였지만 처 stonage.tistory.com 무방향 가중치 그래프에서 모든 정점을 연결하는 동시에 가중치 합의 최소를 구하는 '최소 신장 트리'를 구하는 문제이다... 2023. 5. 23.
[백준] 9372번 - 상근이의 여행 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 그래프이론, 트리 카테고리에 속하는 문제이다. 최근 최소 신장트리 관련 문제를 접하면서 관련 기본 문제를 풀어보고 싶어서 그래프 관련 카테고리를 살펴보던 중 발견한 문제이다. 문제가 요구하는 것은 상근이가 가장 적은 종류의 비행기를 타고 모든 국가를 여행할 수 있도록 하라는 것이다. 입력으로 주어지는 국가를 정점으로 보고 비행 노선을 정점간의 간선으로 생각하면 그래프 형태를 띤다. 가장 적은 적은 종류의 비행기(비행노선)를 .. 2023. 5. 23.
[백준] 12865번 - 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2차원 배열인 dp[][]에 계산결과를 저장하며 최댓값을 구하는 동적 계획법 활용 가능 문제이다. 문제 풀이에 앞서 해당 문제의 유형에 대해 간략하게 정리하겠다. 12865 배낭문제와 같은 문제를 냅색(knapsack problem)문제라고 부른다. 가능한 조합 중에서 어떤 수치의 합의 최대값을 구하는 조합 최적화 문제의 일종이다. 이러한 냅색문제, 통칭 '배낭 문제'는 분할이 가능한 문제와 분할할.. 2023. 5. 22.
[백준] 9251번 - LCS 백준 9251번 - LCS LCS - Longest Common Subsequence의 약자로 최장 공통 부분수열을 의미한다. 이전에 풀이한 백준 11053번 가장 긴 증가하는 부분수열(LIS)와는 달리 두 수열이 주어졌을 때, 두 수열의 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 찾아야 한다. [백준] 11053번 - 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부 stonage.tistory.com 처음 문제를 접했을 때에 쉽게 풀이법을 떠올리지 못했던 기억이 있다. 결국 다른 사람이.. 2023. 5. 22.
[백준] 2565번 - 전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 이전에 해결한 백준 11053번 가장 긴 증가하는 부분 수열을 적용할 수 있는 문제이다. [백준] 11053번 - 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부 stonage.tistory.com 문제를 읽어보면 두 전봇대 A와 B 사이에 1개 이상의 전깃줄이.. 2023. 5. 21.
[백준] 11053번 - 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹프로그래밍을 사용하여 해결할 수 있는 문제이다. 문제에서 요구하는 것은 가장 긴 '증가하는 부분 수열'이다. 부분 수열은 연속적이지 않아도 되기 때문에 처음 문제를 접했을 때는 쉽게 풀지 못했던 기억이 있다. 이 문제를 접하기 이전의 비슷한 문제들의 경우 문제에서 어느정도의 연속성은 보장해주었기 때문이다. 문제에서 주어진 예시를 보면 수열 10, 20, 10, 30, 20, 50.. 2023. 5. 21.

티스토리툴바