본문 바로가기

분류 전체보기69

[백준] 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.
[자료구조] 우선순위 큐와 최대힙, 최소힙(Max Heap, Min Heap) Complete Binary Tree 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 또한 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때에는 최하단 좌측 노드부터 차례대로 삽입해야 한다. Heap 힙이란 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 자료구조를 갖으며 이러한 특성으로 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있다. 중복된 값을 허용하지 않는 이진 탐색 트리와는 달리 힙 트리에서는 중복 값을 허용한다는 특징이 있다. 최대 .. 2023. 5. 23.
[백준] 9372번 - 상근이의 여행 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 그래프이론, 트리 카테고리에 속하는 문제이다. 최근 최소 신장트리 관련 문제를 접하면서 관련 기본 문제를 풀어보고 싶어서 그래프 관련 카테고리를 살펴보던 중 발견한 문제이다. 문제가 요구하는 것은 상근이가 가장 적은 종류의 비행기를 타고 모든 국가를 여행할 수 있도록 하라는 것이다. 입력으로 주어지는 국가를 정점으로 보고 비행 노선을 정점간의 간선으로 생각하면 그래프 형태를 띤다. 가장 적은 적은 종류의 비행기(비행노선)를 .. 2023. 5. 23.
[프로그래머스] 섬 연결하기 처음 시도 했을 때에는 쉽게 풀릴 것 같았다. 첫 번째 시도에는 costs 에서 가중치 기준 오름차순 정렬하여 단순하게 가중치가 작은 간선만을 연결하며 방문처리 하는 방식으로 구현하였지만 처참하게도 0점이었다. 두 번째 시도에는 섬들을 정점, 다리를 두 정점의 간선 가중치로 생각하고 모든 노드를 돌며 방문했다면 재귀를 종료하고, 방문하지 않은 노드라면 이동할 수 있는 다음 노드간의 가중치 중에서 최소값을 갖는 노드에 대해 해당 노드가 바로 직전에 지나온 노드가 아니라면 가중치를 answer에 더하는 방식으로 해결하려고 했는데 단 두개의 테스트(1, 8)만 통과했다. 그 밖에 다른 방법들도 생각해봤지만 정답에 근접하는 느낌은 없었고, 내가 처음 접하는 유형일 수도 있겠다는 생각에 힌트를 찾고자 검색해보니 .. 2023. 5. 23.
[알고리즘]최소 신장 트리(Minimum Spanning Tree) 연결그래프 모든 정점이 연결되어 있는 그래프를 연결 그래프라고 부른다. 여기서 '연결되어 있다'라는 것의 의미는 인접한 정점만을 의미하는 것이 아니라 다른 정점을 거쳐서 도달 할 수 있음을 포함한다. 반대로 어느 두 정점을 골랐을 때 상호간에 도달할 수 없는 경우가 존재하는 그래프를 비연결 그래프라고 한다. Spanning Tree 무방향 연결 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프를 의미하며 신장 트리라고도 부른다. N개의 정점을 가지는 그래프의 최소 간선의 수는 N-1 개이고, 신장 트리의 간선 수는 언제나 N-1개가 된다. 신장 트리를 찾는 방법은 DFS, BFS 등이 있고 하나의 그래프에는 복수개의 신장 트리가 존재할 수 있다. 이런 신장 트리를 적용할 수 있는 분야는 사내 통신 .. 2023. 5. 22.
[백준] 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.

티스토리툴바