Hey Tech

📚 문제 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 🤔 접근법 ⚙️ 핵심 자료구조: 스택 본 문제의 핵심 전략은 진도 업데이트 및 [0] 인덱스 기능의 진도가 100 이상 완수되었는지 반복적으로 확인하는 것입니다. 구현 과정을 조금 더 자세히 설명해 드리자면 다음과 같습니다. 먼저, 모든 기능의 진도(progresses)를 업데이트하고, [0] 인덱스 기능 개발이 완료되었는지(i.e...

📚 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 🔥 접근법 문제를 보자마자 전형적인 다이나믹 프로그래밍(Dynamic Programming, DP) 유형의 문제라고 생각합니다. 유사한 접근법을 사용한 DP 문제로서 "최저 비용의 노드만 거쳐 미로를 탈출하는 문제"를 접한 경험이 있습니다. 본 문제의 핵심 전략은 다음과 같습니다. 삼각형 맨 아래부터 2개의 인접한 자식 노드 중 큰 값을 부모 노드에 더해 부모 노드를 업데이트해 나가는 것입니..

문제 원본 링크: https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근법 본 문제의 목표는 가격이 높은 보석을 최대한 많이 담되 용량이 적은 가방부터 차례대로 담는 것입니다. 이때 가방의 용량에 따른 탐색 순서를 고려하지 않으면 문제를 제대로 풀 수 없습니다. 예를 들어, 다음과 같이 (무게, 가치) 정보가 담긴 3개의 보석과 가방 2개가 있다고 가정해 보겠습니다. 여기서 가방의 용량..

문제 문제 원본: https://www.acmicpc.net/problem/12845 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 접근법 가장 높은 골드를 획득하는 방법, 간단합니다. 레벨이 가장 높은 카드 1장을 고정하고 나머지 카드와 차례로 덧셈하면 됩니다. 어차피 모든 카드의 레벨과 합산해야 하며, 두 카드의 덧셈이(=획득 골드량) 최대가 되기 위해서는 최상위 레벨의 카드 1장을 고정시키면 되는 것이죠. 소스코드 # 카드 개수 입력받기 n = int(input()) # 카드별 레벨 입력받기 level_l..

문제 문제 원본: 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 접근법 본 문제를 한 줄로 요약하자면, N가지 종류의 동전을 조합해 화폐 가치가 K원을 만들 때 필요한 동전의 최소 개수를 구하는 문제입니다. 본 문제는 그리디 알고리즘의 기초 예제인 거스름돈 문제와 변수 이름이나 표현방식이 다를 뿐 풀이 방법은 매우 흡사합니다. 그래서 저는 다음과 같이 일부 변수명을 거스름돈 문제..

본 포스팅에서는 그리디(Greedy) 알고리즘에 대해 알아봅니다. 1. 그리디 알고리즘이란? 그리디(Greedy)는 그림 1 에서 보실 수 있듯이 사전적 의미로서 "탐욕스러운"이라는 뜻을 갖고 있습니다(그림 2 참고). 즉, 그리디 알고리즘은 주어진 문제를 프로그래밍을 통해 탐욕스럽게 풀어내는 알고리즘입니다. 여기서 "탐욕스러운"이라는 말은 그리디 알고리즘이 주어진 상황에서 최선의 옵션만 선택하며 현재의 선택이 향후에 미칠 영향은 고려하지 않는다는 의미입니다. 2. 특징 그리디 알고리즘 문제에서는 주로 "가장 큰 숫자 순서대로" 혹은 "가장 짧은 경로 순으로"와 같은 조건을 제시해 줍니다. 이러한 조건은 대체로 정렬 알고리즘으로 해결할 수 있다는 점에서 그리디 알고리즘은 정렬 알고리즘과 세트로 주어지는 ..