백준(C언어)/23년 9월7 [C] 백준 - 1753번: 최단경로 9월 15일(금) - 그래프와 순회 (1753번) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 문제점 1. 최소 힙을 활용하면 될 것 같다는 아이디어까지만 생각남 -> 힙을 이용한 풀이와 관련해서 참고 힙(Heap)을 이용한 다익스트라(Dijkstra) 알고리즘 다익스트라 .. 2023. 9. 15. [C] 백준 - 3584번: 가장 가까운 공통 조상 9월 14일(목) - 트리 (3584번) 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 입력은 테스트케이스의 개수인 T, 테스트케이스마다 노드의 개수 N, N-1개의 줄에 A, B를 입력받아야하며 마지막 줄인 N번째 줄에 가장 가까운 공통 조상을 구해야하는 두 노드가 주어진다 - 그러므로 parents[ 10001 ]과 visited[ 10001 .. 2023. 9. 14. [C] 백준 - 9252번: LCS - 2 9월 11일(월) - 다이나믹 프로그래밍 (9252번) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 이전에 풀이했던 "9251번: LCS" 문제와 거의 유사 [C] 백준 - 9251번: LCS 9월 4일(월) - 다이나믹 프로그래밍 (9251번) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는.. 2023. 9. 11. [C] 백준 - 1916번: 최소비용 구하기 9월 8일(금) - 그래프와 순회 (1916번) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 문제점 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 풀이 - 1 (풀이출처 -> https://kim1124.tistory.com/19) .. 2023. 9. 8. [C] 백준 - 9934번: 완전 이진 트리 9월 7일(목) - 트리 (9934번) 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 완전 이진 트리이기에 중앙값을 차례대로 저장해나간다면, 원하는 출력의 순서를 맞출 수 있을 것 - 또한 완전 이진 트리이기에 하나의 배열에 입력받고, 합병정렬처럼 재귀를 돌려주면 될 것으로 예상 - 재귀함수에는 (start, end, 깊이)가 매개변수로 넘어와야하고, 탈출조건은 (깊이 ==.. 2023. 9. 7. [C] 백준 - 1339번: 단어 수학 9월 6일(수) - 그리디 알고리즘 (1339번) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 입력으로는 단어의 개수인 N, 그리고 N개의 단어가 주어진다 - for문을 N개만큼 돌려주면서 word[9]에 입력받고, word[ ] - 'A' 값을 인덱스로 받은뒤 qsort를 통해서 alphabet[ ] 배열을 정렬해주고 for문을 돌려주면서 max 값을 갱신해준다 - 출력은 최댓값을 갱신해놓.. 2023. 9. 6. [C] 백준 - 9251번: LCS 9월 4일(월) - 다이나믹 프로그래밍 (9251번) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 최초 생각 정리 - 이전의 "11053번: 가장 긴 증가하는 부분수열"의 풀이가 결국 정리되어서 LIS알고리즘이 존재했던 것 처럼, 이번 문제도 LCS알고리즘이 있을 것이라 판단하고, 먼저 찾아보기로 결정 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Com.. 2023. 9. 4. 이전 1 다음