알고리즘/백준
-
11066 파일 합치기알고리즘/백준 2022. 4. 1. 00:43
백준 11066번 파일 합치기 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이 전] 예를 들어, 40 30 30 50의 입력을 받으면 1 : 40 / 30 / 30 / 50 2 : 40 30 / 30 30 / 30 50 3 : 40 30 30 / 30 30 50 4 : 40 30 30 50 와 같은 순서로 1부터 4까지 파일 묶음의 최소 비용을 순서대로 구해가면 될 것이라 생각했다. ( ex. 3 : 40 30 30의 최소비..
-
1260 DFS와 BFS알고리즘/백준 2022. 3. 25. 00:28
백준 1260 DFS와 BFS : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [개념(간단하게 정리)] 깊이 우선 탐색(DFS, Depth First Search) : 탐색 방법 : 현재 노드에서 분기를 완벽하게 탐색 후 다음 분기로 넘어감의 반복 스택으로 구현 가능 너비 우선 탐색(BFS, Breadth First Search) 탐색 방법 : 현재 노드에서 연결된 노드를 모두 방문하면 다음 노드로 넘어..
-
2805 나무 자르기알고리즘/백준 2022. 3. 23. 10:26
백준 2805번 나무자르기 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이분탐색으로 풀 수 있는 문제다 이분 탐색 참고 -> https://wh514.tistory.com/20 [코드 작성 전] 우선, 높이를 입력받으며 미리 나무 중 가장 높은 높이(hmax)를 저장한다. 탐색 범위를 0 ~ hmax로 설정하고 이분 탐색을 진행한다. 중간 값(cutter)를 절단기 설정 높이로 가정하고 ..
-
1920 수 찾기(이분탐색)알고리즘/백준 2022. 3. 23. 09:48
백준 1920번 수찾기 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net [개념] 이분탐색 : (정렬된 리스트에서) 탐색범위를 절반으로 좁혀가며 데이터를 탐색하는 방법 - 이진탐색, Binary search 라고도 한다. 예시로, 상대방의 0~100 까지 숫자 중 생각해둔 숫자를 맞출 때, 내가 말한 숫자에 대해 up down을 해주면 범위를 점점 좁혀가며 숫자를 맞추는 경우가 있다. 여기서, ..
-
6549 히스토그램에서 가장 큰 직사각형알고리즘/백준 2022. 3. 21. 01:14
백준 6549 히스토그램에서 가장 큰 직사각형 : https://bit.ly/3Jtkc86 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net [코드 작성 전 정리] 우선 분할 정복으로 풀 것이기 때문에 재귀함수로 구현 필요한 것 ① 반(left, right) 나누기 return max, 높이 정보 필요 (높이는 참조로 전달) ② 합치기 left, right 중 더 낮은 높이를 기준으로 합치기 ③ 합칠 때 겹치는 부분 생각하기 겹치는 부분 기준으로 왼쪽, ..
-
2630 색종이 만들기알고리즘/백준 2022. 3. 17. 18:45
백준 2630 색종이 만들기 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할 정복 문제는 간단히 말하면, 문제를 나누어 풀어 작은 문제의 답을 구해 그 답을 합치면서 최종 문제의 답을 구하는 것 즉, 재귀로 풀면 좋을 것 [문제를 풀기 전 생각한 것 ] ① n/2가 1이 될 때 까지 나누고 합치면서 값을 계산할 것 ② 재귀 함수 구성 정사각형을 1, 2, 3, 4로 나누기 (순서는 아래 그림 참고) 1, 2,..
-
1068 트리알고리즘/백준 2022. 3. 13. 02:19
백준 1068 트리 : https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 코드 작성 전, 하나의 노드에 대해 필요한 정보를 ① 부모 값 ② 자식의 수 로 정리하고, 리프 노드를 구하는 방법을, 자식의 수가 0인 노드의 부모 값, 부모의 부모 값 … 루트 노드 값까지 삭제한 노드 값과 일치하는 값이 없으면 리프 노드로 결정하는 방법으로 정했다. 그리고 주의할 점, 루트 노드가 삭제될 경우 직선 상태에서 노드가 삭제된 경우 #include us..