노랑꼬리의 개발 블로그

문제링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 작성코드 해설 입력받은 x1,y1, x2,y2의 값들을 매번 계산하게 된다면 테스크 케이스, 좌표값 차이가 커질 경우 연산 시간을 감당하기 힘들어진다. 이를 위해 누적합을 저장해주고 이를 활용하여 값을 출력해준다. 1. 누적합 계산하기 누적합 값을 계산할 dp 표를 만든다. N x N 의 표에서는 1,1 부터 시작하므로 계산을 편리하게 하기 ..

문제링크 : https://www.acmicpc.net/problem/26217 26217번: 별꽃의 세레나데 (Easy) 겨울 나라의 왕은 꽃을 좋아하는 왕비를 위해 가장 아름다운 꽃들을 모아 화관을 만들기로 했다. 왕비가 좋아하는 꽃들은 특별해서 마법의 씨앗을 심은 뒤 별빛을 받아야 피어난다. 마법의 씨앗 www.acmicpc.net 작성코드 해설 꽃이 필 확률은 꽃의 종류와 동일하다. 즉 3종류라면 각각 1/3 일 것이고 5종류라면 각각 1/5 일 것이다. 그런데 모든 종류를 피워야만 한다. 5종류를 예시로 들어보자 필요한 씨앗의 기댓값을 구해야한다. 일단 무조건 첫번째 피는 꽃은 100% 확률로 사용될 것이다. 어떤 꽃이던지 사용될 것이므로 씨앗 하나면 성공한다. 5/5 두번째 꽃은 첫번째 꽃을 ..

문제링크 : https://www.acmicpc.net/problem/26215 26215번: 눈 치우기 집 2와 집 3 앞의 눈을 치우고, 집 2와 집 3 앞의 눈을 치우고, 집 1과 집 3 앞의 눈을 치운 뒤 집 3 앞의 눈을 두 번 치우면 5분만에 모든 집 앞의 눈을 치울 수 있다. www.acmicpc.net 작성코드 해설 눈을 치우는 규칙은 한번에 한 집 혹은 두 집의 눈을 1만큼 치우는 것이다. 한번에 두 집의 눈을 치우는 것이 가장 빠르게 눈을 치울 수 있기 때문에 최대한 두 집을 치워야만 한다. 두 가지 경우로 나눌 수 있는데 1. 가장 많은 눈이 쌓인 집의 눈 양이 나머지 쌓인 눈보다 적은 경우 2. 가장 많은 눈이 쌓인 집의 눈 양이 나머지 쌓인 눈보다 클 경우 1 의 경우 모든 집을 ..

문제링크 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 작성코드 해설 이 문제는 구간합을 활용하여 푸는 문제이다. 단순히 리스트를 탐색하여 i + K 식으로 전체를 돌며 계산할 경우 시간초과가 나온다. 구간 합에 관한 내용은 https://yellowtail2357.tistory.com/28 [백준] 11659 구간 합 구하기 (python 파이썬) 문제링크 : https://www.acmicpc.net/problem/1165..

문제링크 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 작성코드 해설 11053 문제 (https://yellowtail2357.tistory.com/40) [백준] 11053 가장 긴 증가하는 부분 수열 (python 파이썬) 문제링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A =..

문제링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 작성코드 해설 LIS (Longest Increasing Subsequence)알고리즘이라고 불리는 문제로서 dp 혹은 이분탐색으로 풀 수 있는 문제이다. 수열에서 가장 긴 부분 수열을 찾는 문제인데 기존 dp에서 값을 넣어 연산하는 방식과 조금 다르게 랭크을 넣어 순서를 구해준다. ※ 만약 해당 순서의 원..

문제링크 : https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 작성코드 해설 이 문제는 2579 계단 오르기 문제와 거의 동일한 문제이다. https://yellowtail2357.tistory.com/37 [백준] 2579 계단 오르기 (python 파이썬) 문제링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다..

문제링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 작성코드 해설 문제에서 룰은 총 세가지이다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 이를 계산하기 위해 모든 과정을 탐색 알고리즘인 DFS로 푼다면 엄청난 시간이 걸리..

문제링크 : https://www.acmicpc.net/problem/26073 26073번: 외로운 곰곰이는 친구가 있어요 첫 번째 줄에 친구의 수 $N\ (1 \le N \le 10\,000)$이 주어집니다. 이후 $N$개의 친구 정보가 각각 두 줄에 걸쳐 주어집니다. $i$번째 친구 정보의 첫 번째 줄에는 친구의 처음 위치 $X_i$, $Y_i\ (-100\,000 \le X www.acmicpc.net 작성코드 해설 1) 좌표에 도달하기 위한 시간 제한 같은것은 없기 때문에 얼마나 오랫동안 헤매던 상관없이 도달만 하면 된다. 즉, 좌표이동 값의 최소단위를 알면 도달 가능 여부를 알 수 있다. (Ex. 이동 가능 거리가 9999와 9998이 있다면 오른쪽으로 9999 이동 후 왼쪽으로 9998을 이..

문제링크 : https://www.acmicpc.net/problem/26072 26072번: 곰곰이와 시소 첫번째 줄에 정수 $N$과 $L$이 공백을 사이에 두고 주어진다. $(1 \le N, L \le 100\,000)$ 두번째 줄에 정수 $x_1, x_2, \cdots, x_N$이 공백을 사이에 두고 주어진다. $(0 \le x_i \le L)$ 세번째 줄에 정수 $w_1, w_2, \c www.acmicpc.net 작성코드 풀이 1) 문제 노트에 있는 공식을 활용해서 풀어야한다. WL은 왼쪽에 있는 치킨들의 값 WR은 오른쪽에 있는 치킨들의 값으로 생각하면 된다. Σ 는 숫자의 합이므로 Σ(1~N)이라면 1~N 까지의 합이다 2) 시그마 공식을 그대로 써서 계산하면 바로 나오겠지만 이해하기 쉽도록..