일지 & 개발

문제 요약 알고리즘 분류: 베열 난이도: Silver5 문제내용: 가로, 세로 각각 100인 도화지가 있다. 각 케이스마다 가로, 세로 위치에서 10 크기 정사각형 색종이를 붙인다. 색종이의 넓이를 구해라(색종이 크기가 벗어나지 않는 케이스만 준다.) 사이트 주소: https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 문제풀이 이번 문제는 2차원 배열 활용하는 문제이다. 각 색종이 붙이 범위에 1을 표시하고 1인 값만 찾으면 된다. 2차원 배열 각 크기 100..

문제 요약 알고리즘 분류: 구간합, 누적합, 수학 난이도: Silver1 문제내용: 문자열 S가 주어지고 각 테스트케이스 마다 문자와 인덱스 시작점과 끝을 준다. 문자열에서 시작점과 끝사이에 문자 몇개 있는지 출력해라 사이트 : https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문제풀이 이번문제는 두가지 경우가 있는데 50점짜리는 각 시작점 부터해서 끝지점까지 탐색해서 해당되는 문자 몇개인지 출력..

알고리즘 분류: 구간합, 누적합, 수학 난이도: 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 [알고리즘 이론] 구간합,..

이론 1차원 배열 누적합 누적합부터 먼저 설명하면 0번째 인덱스 부터 N 번째 인덱스까지 탐색하면서 인덱스 i일때 0번째 인덱스 부터 0번째 인덱스합을 말한다. Python array = [1, 8, 7, 4, 3, 5, 6] n = len(array) prefix_sum = [0] * n for i in range(n): for j in range(i+1): prefix_sum[i] += array[j] Java import 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[] prefix_sum = n..

문제 요약 알고리즘 분류: 베열 난이도: 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..

문제 요악 알고리즘 분류: 동적 계획법 난이도: 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..

문제 요악 알고리즘 분류: 동적 계획법 난이도: Gold5 문제 요약 전봇대 A, B 사이에 전기줄이 여러개 있다. 교차가 되는 선이 몇개 있는데 최소 몇개의 선을 잘라야 교차 되는 선이 없는기 구해라 사이트 주소: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다. https://jih3508.tistory...

이론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, ..