본문 바로가기

알고리즘185

[BAEKJOON] 2559 수열 알고리즘 분류: 구간합, 누적합, 수학 난이도: Silver3 문제내용: 전체 날짜 수 N과 연속적인 날짜의 수 K와 전체 날짜를 준다. 연속적인 K일 온도의 합중 가장 큰것을 구해라 사이트 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제풀이 이번 문제는 누적합, 구간합 기본 문제이다. 개념이나 이론적인 설명은 아래에 사이트에 참조 하면된다. https://jih3508.tistory.com/50 [알고리즘 이론] 구간합,.. 2022. 11. 8.
[알고리즘 이론] 구간합, 누적합(prefix sum) 이론1차원 배열누적합 누적합부터 먼저 설명하면 0번째 인덱스 부터 N 번째 인덱스까지 탐색하면서 인덱스 i일때 0번째 인덱스 부터 0번째 인덱스합을 말한다. Pythonarray = [1, 8, 7, 4, 3, 5, 6]n = len(array)prefix_sum = [0] * nfor i in range(n): for j in range(i+1): prefix_sum[i] += array[j]Javaimport java.util.Arrays;public class Main { public static void main(String[] args){ int[] array = {1, 8, 7, 4, 3, 5, 6}; int n = array.length; int[] prefixSum .. 2022. 11. 8.
[BAEKJOON] 2566 최댓값 문제 요약 알고리즘 분류: 베열 난이도: Bronze3 문제내용: 9×9 격자판에 가장 큰 값과 위치를 구해라 사이트 주소: https://www.acmicpc.net/problem/2566 4999번: 아! 입력은 두 줄로 이루어져 있다. 첫째 줄은 재환이가 가장 길게 낼 수 있는 "aaah"이다. 둘째 줄은 의사가 듣기를 원하는 "aah"이다. 두 문자열은 모두 a와 h로만 이루어져 있다. a의 개수는 0보다 크거 www.acmicpc.net 문제풀이 최댓값, 위치 x,y 저장할 변수를 선언한다. 이중 for 문으로 기존 최대값이랑 비교해서 기존 최대값보다 크면 기존 최대값을 저장하고 위치 x, y를 저장 한다. 최대값을 출력하고 위치 x, y 각 +1 한 다음 출력한다. Code Python mat.. 2022. 11. 8.
[BAEKJOON] 11054 가장 긴 바이토닉 부분 수열 문제 요악 알고리즘 분류: 동적 계획법 난이도: Gold5 문제 요약 수열 S가 있다. 수열 S[1] S[N - 1] 만족하는 최장 길이 수열을 구해라 증가 했다가 중간에 감수하는 수열을 구해라 사이트 주소: https://www.acmicpc.net/problem/11054 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다. https://jih3508.ti.. 2022. 11. 7.
[BAEKJOON] 2565 전깃줄 문제 요악 알고리즘 분류: 동적 계획법 난이도: Gold5 문제 요약 전봇대 A, B 사이에 전기줄이 여러개 있다. 교차가 되는 선이 몇개 있는데 최소 몇개의 선을 잘라야 교차 되는 선이 없는기 구해라 사이트 주소: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다. https://jih3508.tistory... 2022. 11. 3.
[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 이론1. LIS이란? LIS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알jih3508.tistory.com  LIS, 최장 증가 부분 수열은 나열된 배열이나 리스트에서 원소를 몇개 제외하고 오름차순또는 내림차순으로 가징 긴 수열을 말한다 예를 들어 {1, 5, 3, 6, 7, 9, 4, 2, .. 2022. 11. 2.

티스토리툴바