반응형 greedy 알고리즘3 [Algorithm] 그리디 알고리즘(Greedy Algorithm)이란? 이 글은 '이것이 코딩테스트다'를 요약하여 그리디 알고리즘에 대하여 설명합니다. 학습 목표 · 그리디 알고리즘이란? · 예시 - 거스름돈 문제 · 그리디 알고리즘의 정당성 그리디 알고리즘이란? · 탐욕적으로 문제를 푸는 알고리즘 - 탐욕적이라는 말은 ‘매 순간 가장 좋아 보이는 것만 선택하고 나중에 미칠 영향은 고려하지 않는’ 방식을 의미한다. · 코딩 테스트에서 만나게 될 그리디 알고리즘 문제 유형의 특징: - 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. - 문제 유형이 매우 다양하여 암기한다고 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 때문에 많은 유형을 접해보고 문제를 풀어보며 훈련 해야 한다. - 일반적으로 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 .. 2021. 11. 4. [Algorithm] 그리디 알고리즘 문제 풀이 - 1이 될 때까지 그리디 알고리즘 문제 풀이 - 1이 될 때까지 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 그리디 알고리즘 문제 중 '1이 될때까지' 문제와 풀이를 설명합니다. 문제 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 .. 2021. 1. 11. [Algorithm] 그리디 알고리즘 문제 풀이 - 숫자 카드 게임 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 그리디 알고리즘 문제 중 ' 숫자 카드 게임' 문제와 풀이를 설명합니다. 문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑를 것을 고려하여 최종적으.. 2021. 1. 10. 이전 1 다음 반응형
