상상쓰

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 동적 계획법 문제로 dp 배열을 잘 정의해주자. dp 는 2차원 배열로 행을 물건의 개수, 열을 배낭의 무게로 잡는다. dp[i][j] 는 물건이 i 개 있을 때 j 를 수용할 수 있는 배낭에 들어갈 수 있는 가치의 합의 최댓값이라고 정의하자. 그럼, 물건이 추가됐을 때, 그 물건의 무게가 j 보다 작으면 그 물건은 수용할 수 없으..

https://programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr DFS 와 동적 계획법을 이용하여 풀 수 있을 거라고는 생각했는데 dp 배열을 구현하기가 어려워서 다른 블로그를 참고하여 풀어나갔다. dp[i][0] : i 가 참석하지 않았을 때의 최솟값, dp[i][1] : i 가 참석했을 때 최솟값으로 정의하고, 기본값으로 dp[i][1] = sales[i-1], dp[i][0] = 0 으로 시작한다. 리프 노드부..

https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 위클리 챌린지 2주차 문제로 열을 기준으로 탐색한다. 대각 원소를 기준으로 대각 원소보다 큰 값이 N - 1 또는 작은 값이 N - 1 이면 대각 원소는 유일한 최고점 아니면 유일한 최저점이므로 제외하고 평균을 계산한다. def solution(scores): answer = '' N = len(sco..

https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 조합, 파스칼의 삼각형을 이용하여 풀었다. 4를 예로 들면, 2칸을 기준으로 2칸을 뛴 적이 0번일 때 : 4C0 1번일 때 : 3C1 2번일 때 : 2C2 answer = 4C0(1) + 3C1(3) + 2C2(1) = 5 이다. 파스칼의 삼각형의 원리를 이용하여 2차원 배열에 각 조합 값을 담아(dp[..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 이차원 배열로 수열을 비교하여, 1) 같은 문자일 때, dp[i][j] = dp[i-1][j-1] (두 수열에서 같은 문자가 추가되기 전의 최댓값) + 1 ACAYK 와 CAPCAK 의 LCS 의 길이는 ACAY 와 CAPCA 의 LCS 의 길이의 + 1 이다. 2..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net dictionary 를 이용하여 친구 관계를 나타내고 1 과 dic[1] (1 의 친구들) 의 친구들을 friends 집합에 담아서 중복을 없앤다. friends 에 원소가 있는 경우 1 이 존재하므로 len(friens) - 1 을 반환해주고 그렇지 않으면, 0 을 반환해준다. import sys from collections import defaultdict n = int(sys..

https://programmers.co.kr/learn/courses/30/lessons/82612?language=java 코딩테스트 연습 - 1주차 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 등차수열의 합 공식 (첫째 항 + 마지막 항) * 항의 개수 / 2 class Solution { public long solution(long price, long money, long count) { return Math.max(0, (price + (price * count)) * count / 2 - money); } }

https://www.acmicpc.net/problem/10699 10699번: 오늘 날짜 서울의 오늘 날짜를 출력하는 프로그램을 작성하시오. www.acmicpc.net 파이썬에서 아래와 같이 현재 날짜를 출력할 수 있다. from datetime import datetime print(datetime.today().strftime("%Y-%m-%d"))

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 위치도 기억해야 하고 N 이 50 이하이므로 정렬로 구하기보다는 이중 for 문을 사용하여 덩치마다 큰 덩치가 나타나면 rank 를 1 씩 더하여 answer 에 담았다. 몸무게가 같고 키가 크면 덩치가 더 큰 줄 알았는데, 문제를 다시 보니 둘 다 값이 커야 덩치가 크다고 말 할 수 있다. import sys N = int(sys.stdin.readline()) bulk = [] a..

https://www.acmicpc.net/problem/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 세 자리수 곱셈 import sys A = int(sys.stdin.readline()) B = sys.stdin.readline().strip() answer = 0 print(A * int(B[2])) answer += A * int(B[2]) print(A * int(B[1])) answer += A * int(B[1]) * 10 print(A * int(B[0])) answer += A * int(B[0]) * 100 print(answer)