노랑꼬리의 개발 블로그

문제링크 : https://www.acmicpc.net/problem/1931 작성코드 해설 가장 많은 회의를 하기 위해서는 회의를 최대한 빨리 끝나는 회의들로 구성해야 한다. 그러기 위해 회의들을 오름차순으로 정렬 해주는데 time 리스트를 sort 해주면 첫번째 원소인 start에 대해서만 정렬 된다. 하지만 끝나는 시간이 섞여있기 때문에 두번째 원소에 대해서도 정렬 해주어야 하는데 이는 key=lambba a:a[] 식으로 원소를 지정해줄 수 있다. ※ 원소 지정은 여러개도 가능한데 예를 들어 sort(key=lambda a: (a[1], a[0])) 라면 우선 a[1] 원소에 대하여 오름차순 정렬해주고 a[1] 값이 같은 경우들의 a[0]에 대해 오름차순으로 정렬해준다. 정렬한 상태에서 순서대로 ..

문제링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 작성코드 해설 조건으로 동전은 배수로서 주어진다는 것을 알게 되었으니 문제가 간단해진다. 동전 사용 갯수를 최소로 만들기 위해서는 큰 동전을 최대한 많이 사용하면 되므로 해당 금액에서 사용할 수 있는 가장 큰 동전을 사용하고 남은 금액을 다시 반복해주면 된다. 이를 코드로 작성하면 아래와 같다. 동전 입력은 오름차순으로 ..

문제링크 : 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로 푼다면 엄청난 시간이 걸리..