https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr kakao 의 공식 해설을 참고했다. https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/ 2022 테크 여름인턴십 코딩테스트 해설 2022년 카카오 여름 인턴십 코딩 테스트가 지난 5월 7일에 5시간에 걸쳐 진행되었습니다. 시간이 부족하여 문제를 풀지 못하는 아쉬움이 없도록 1시간을 늘려 테스트를 진행한 것이 작년과 조금 ..
dp
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..
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp 는 3 * (n+1)의 공간으로 만들어 주었다. 사자를 배치하는 것에 대해 생각해보면 다음과 같은 세 가지 이다. 1. 사자를 배치하지 않는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] 2. 사자를 왼쪽 칸에 배치하는 경우 사자를 연속해서 왼쪽 칸에 배치할 수 없으므로, 이전 계산 값 (dp[i-1])에서 오른쪽에 배치한 경우와 배치하지 않는 경우의 수를 가져온다. dp[i][1] = dp[i-1][0] + dp[i-1][2] 3. 사자를 오른 쪽 칸에 배치하는 경우 사자를 연속..
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1) 시간초과 풀이 n = int(input()) array = list(map(int, input().split())) answer = 0 def dfs(total, index, target): global answer if total 20: return if index == n-1: if total == target: answer += 1 return if 0
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 짜잔 이렇게 dp 테이블을 그려서 dp[i][j] = dp[i-1][j] + dp[i][j-1] 라는 점화식을 도출해내면 끝이다 단 i -1 > 0, j -1> 0 이어야 하므로 i, j 는 각각 2이상이어야 한다 !! 그러기 위해서는 dp[?][1] 은 n (자기자신) 값으로 초기화 해주어야 하고 dp[1][?] 는 1로 초기화해주어야 한다 # 2225 합분해 n, k = map(int, input().split()) dp = [[0] * 201 for _ in range(201)] for i in range(1, 201..
유형 : DP(다이나믹 프로그래밍) 배열을 뒤집어서 가장 긴 증가하는 수열을 찾는다 예전에 풀었던 문제 11722 가장 긴 감소하는 부분 수열과 똑같은 dp 문제이다. 다만 이번 문제에서는 제외할 병사의 수를 출력해야 하므로 n - dp의 최댓값 (= 가장 긴 수열의 길이) 를 출력해주어야 한다. https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 가장 긴 감소하는 부분 수..
다이나믹 프로그래밍은 전형적으로 보텀업 방식 형태를 보인다. 그렇지만 탑다운 방식과 보텀업 방식의 차이를 알아볼 필요가 있다. 상향식, 하향식에 따라 재귀호출인지 반복호출인지의 차이도 보여지기 때문이다. 1. 탑다운 방식 (Top-down) 재귀 함수를 이용하여 DP를 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있으면 그대로 값을 반환한다. return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] * 실행 결과 f(10)을 구하기 위해서 ..
