본문 바로가기

알고리즘231

[BAEKJOON] 2407 조합 문제 요약 알고리즘 분류: 수학, 조합 난이도: Silver3 문제내용: 조합 결과값을 출력해라 사이트 주소: https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제풀이 이번 문제는 조합 공식만 알면 되는데 파이썬같은 동적 변수타입은 문제 없지만 정적 타입 선언 해야 되는 언어는 long타입 선언해도 결과값이 오버 되기때문에 그점을 유의 하면서 풀면 된다. Code Python 파이썬은 어떤 방식으로 풀어도 된다. 그래서 factorial과 comb 사용 법만 알면된다. from math import factorial n, m = map(int, input()... 2022. 12. 8.
[BAEKJOON] 1655 가운데를 말해요 문제 요약 알고리즘 분류: 힙, 우선순위 큐, 자료구조 난이도: Gold2 문제내용: 숫자가 추가될때마다 정렬해서 가운데 숫자를 출력하면된다. 사이트: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 이번 문제는 힙으로 풀어야 한다. 하지만 힙을 구하는 목적은 최대값, 최소값인데 중간 크기를 구하는 힙은 없어서 어느정도 생각해서 풀어야 될 문제이다. 힙 관련된 자세한 내용은 아래의 사이트에서 확인 헤보면된다. https.. 2022. 12. 7.
[알고리즘 이론] 힙(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] 22193 Multiply 문제 요약 알고리즘 분류: 수학 난이도: Bronze5 문제내용: N M 길이 준다 A , B 곱한 결과를 출력해라 사이트: https://www.acmicpc.net/problem/22193 22193번: Multiply Write a program that computes a product of two non-negative integers A and B. The integers are represented in decimal notation and have N and M digits, respectively. www.acmicpc.net Code Python input() print(int(input()) * int(input())) Java 정수의 길이의 제한이 없어서 BigInteger로 선언해.. 2022. 11. 28.