본문 바로가기

알고리즘186

[알고리즘 이론] 힙(Heap) 이론 이번에 볼 자료구조는 힙이다. 힙은 완전 이진트리에서 최대값 또는 최소값을 찾아내는 자료구이다. 자세한 설명은 아래 사이트에서 확인해보면된다. https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 ko.wikipedia.org 2022. 12. 7.
[BAEKJOON] 1092 배 문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: 크래인 N개와 박스 M개가 있다. 각 크레인은 최대 들수 있는 무게와 박스별 무개가 주어진다. 1분당 한 크래인은 한개만 옮길수있다. 모든 박스를 옮기는데 걸리는 시간을 구해라. 사이트: https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑.. 2022. 12. 6.
[BAEKJOON] 12015 가장 긴 증가하는 부분 수열 2 문제 요약 알고리즘 분류: 이분탐색 난이도: Gold2 문제내용: 수열 A가 주면 가장 긴 증가하는 수열의 길이를 구해라 사이트: https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제풀이 이번 문제는 LIS문제인데 1,000,000크기 데이터로는 DP로 풀기에는 시간 초과가 난다. 그래서 이분 탐색으로 풀어야 된다. 그 부분은 아래의 사이트에서 확인 해보면 된다. 아래 사이트에 이분 탐색으로 구현한 코드있으면 거기 코드 보고 약간 추가만 해주면.. 2022. 11. 29.
[BAEKJOON] 1300 K번째 수 문제 요약 알고리즘 분류: 이분탐색 난이도: Gold2 문제내용: 크기 N×N 배열이고 시작 인덱스는 0이 아니고 1부터 시작한다. 배열 A[i][j]의 값은 i × j이다. 2차원 배열 A를 일차원 배열 B로 만들어서 오름차순으로 정렬하면 배열 B에서 K번째 인덱스 값을 구해라 사이트: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제풀이 이번 문제는 간단해 보일거 같은데.. 배열 A에서 완전탐색으로 값을 넣.. 2022. 11. 28.
[BAEKJOON] 2012 등수 매기기 문제 요약 알고리즘 분류: 그리디 난이도: Silver3 문제내용: 실제 성적 등수와 학생 예상 등수 최소 차이를 구해라 사이트: https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑에 사이트에 참조하면된다. https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 .. 2022. 11. 28.
[BAEKJOON] 6549 히스토그램에서 가장 큰 직사각형 문제 요약 알고리즘 분류: 분할정복, 스택, 세그먼트 트리 난이도: Platinum5 문제내용: 각 케이스마다 위 그림 처럼 히스토그램 넓이중 가장 큰것을 구해라. 사이트 : https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제풀이 이번에는 문제 유형은 분할 정복, 스택, 세그먼트 트리 3가지 방법으로 풀수 있다. 간단하게 완전탐색으로도 답은 나오지만 문제는 주는 데이터의 수가 10만이다.. 2022. 11. 25.

티스토리툴바