일지 & 개발

문제 요약 알고리즘 분류: 백트래킹 난이도: Silver3 문제내용: N, M 가 주어 졌을때 1 ~ N수 에서 중복된 숫자가 없고 크기 순으로 출력하면 된다. 중복되는 수열은 여러번 출력하면 안된다. 사이트 주소: https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 이론] ..

이론 이번에 볼 알고리즘은 백트래킹이다. 백트래킹을 알아두면 대부분 해를 찾는데 도움이 될것이다. 백트레킹은 탐색하는 도중 중복되거나 해를 찾는 방향이 맞지 안 맞으면 그 부분을 탐색하지않는다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 이러면 불필요한 탐색을 할 필요가 없어서 기존 완전 탐색보다 시간적이나 메모리가 단축할수 있다. 자세한것은 아래 사이트에서 확인해보면된다. https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀..

문제 요약 알고리즘 분류: 수학, 조합 난이도: 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()...

문제 요약 알고리즘 분류: 힙, 우선순위 큐, 자료구조 난이도: Gold2 문제내용: 숫자가 추가될때마다 정렬해서 가운데 숫자를 출력하면된다. 사이트: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 이번 문제는 힙으로 풀어야 한다. 하지만 힙을 구하는 목적은 최대값, 최소값인데 중간 크기를 구하는 힙은 없어서 어느정도 생각해서 풀어야 될 문제이다. 힙 관련된 자세한 내용은 아래의 사이트에서 확인 헤보면된다. https..

이론 이번에 볼 자료구조는 힙이다. 힙은 완전 이진트리에서 최대값 또는 최소값을 찾아내는 자료구이다. 자세한 설명은 아래 사이트에서 확인해보면된다. 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

문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: 크래인 N개와 박스 M개가 있다. 각 크레인은 최대 들수 있는 무게와 박스별 무개가 주어진다. 1분당 한 크래인은 한개만 옮길수있다. 모든 박스를 옮기는데 걸리는 시간을 구해라. 사이트: https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑..

문제 요약 알고리즘 분류: 이분탐색 난이도: 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로 풀기에는 시간 초과가 난다. 그래서 이분 탐색으로 풀어야 된다. 그 부분은 아래의 사이트에서 확인 해보면 된다. 아래 사이트에 이분 탐색으로 구현한 코드있으면 거기 코드 보고 약간 추가만 해주면..

문제 요약 알고리즘 분류: 수학 난이도: 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로 선언해..