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 0-1 냅색 문제이다 i번째 물건을 가방에 넣는경우와 넣지 않는 경우를 비교해서 최대 값을 저장한다. 이때 값은 value가 된다 dp[i][j] 는 i 번째 물건을 확인하는 중 j kg 까지 넣을 때 최대 value를 저장한다. import sys input = sys.stdin.readline n, k = map(int, inp..
Algorithm (PS)
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 입출력을 꼭 sys.stdin.readline 으로 바꿔주어야 시간초과가 안난다 !! 그리고 pypy3로 통과했다 i 부터 j 까지의 수열이 펠린드롬인지 확인해야 하는데 미리 dp 테이블을 채워준다. 펠린드롬 수열의 경우 길이가 1인경우 펠린드롬이므로 dp[i][i] = 1 을 채워준다. if start == end: # 자기 자신인 경우 무조건 1 임 dp[start][end] = 1 길이가 2인경우 수열 두가지만 확인하면 되는데, ..
https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net n, k = map(int, input().split()) array = [0] * 1000002 # 1 ~ 100001 까지 저장 for i in range(n): a, b = map(int, input().split()) array[a+1] += 1 array[b+1] -= 1 for i in range(1, 1000002): array[i]..
https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 아 어렵다 원래 dfs밖에 기억이 안났는데 문제유형보고 DP란것을 알았다 dfs로 풀면 대각선&상하좌우 8방향을 모두 확인해야하니까 시간초과가 날것 같다 0의 개수를 dp 테이블에 누적하여 저장한다. 단 !! 1 또는 2를 만났을 때는 누적하면 안된다. 이걸 방지하기 위해서 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1 대각선방향, 위쪽방향, 아..
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net n = int(input()) task = [] price = [] # price dp = [0] * (n+1) for _ in range(n): t, p = map(int, input().split()) task.append(t) price.append(p) # result 예제 10번에서 예외케이스 처리 -> dp[10]이 최댓값(60) + price[7] 로 갱..
https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr total_member = 0 total_profit = 0 rates = [10, 20, 30, 40] def calc(rate_list, users, emoticons): temp_member = 0 temp_profit = 0 for user in users: rate, money = user user_profit = 0 for i in range(len(emoticons)): if rat..
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 원래는 row 별 갈수 있는 길, column 별 갈 수 있는길을 각각 함수로 만들어줄까 했다. 그래서 원래는 row 체크중이면 type 1 column 체크중이면 type2로 할까했는데.. 생각해보니까 check_row 함수를 재활용하고 배열을 90도 시계방향으로 돌려서 array를 parameter로 전달하면 될것 같아서 따로 column 을 확인하는 함수를 만들지 않았다 (사실 귀찮아서..) 그래서 코드에 저 ty..
https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 2019년도 블라인드 공채 문제이다 솔직히 이제는 이런 문제 안나올 것 같다 ㅋㅋ 카카오는 가끔 이렇게 실질적인 기능 개발을 연상케 하는 문제를 출제하는 것 같다. 확실히 예전보다 지금이 더 코딩테스트 레벨이 상향 평준화 되고 있는 느낌을 받는다. from collections import defaultdict def solution(record): answer = [] table = de..
