<div id="readability-page-1" class="page"><div><blockquote>
<p>해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.</p>
</blockquote>
<h2 id="1-그리디란">1. 그리디란?</h2>
<p>매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘. 단, 최적해를 보장해주지 않는다.</p>
<p><img src="https://velog.velcdn.com/images/2taesung/post/388525e6-11c2-43ac-85e9-554b37f40da1/image.png"></p>
<p>=&gt; 다음과 같이 A에서 B/D를 선택할때 최적의 선택.<br>
=&gt; 그리고 B를 갔을때 최적의 선택 .... 으로 이어짐.<br>
=&gt; 결과적으로 전체를 봤을때는 최고의 선택이 아닐 수 있음</p>
<h2 id="실제-사용-예시">실제 사용 예시</h2>
<ul>
<li>거스름돈 반환 문제</li>
</ul>
<h2 id="2-그리디-알고리즘의-특징">2. 그리디 알고리즘의 특징</h2>
<ul>
<li>보통 최적해를 구하는 알고리즘보다 빠른 경우가 많음<br>
=&gt; 주로 선형 단위에서 해결이 됨</li>
<li>크루스칼, 다익스트라 알고리즘 등에 사용됨</li>
<li>직관적인 문제 풀이에 적합</li>
</ul>
<p>=&gt; 하나의 특정 문제풀이 방식이 아닌 하나의 개념으로 봐야함</p>
<h2 id="3-코테">3. 코테</h2>
<p>핵심키워드 : 가장 큰 순서대로, 가장 작은 순서대로<br>
참고 상황 : 탐색으로 풀 수 있으나 제한조건이 걸려있는 상황<br>
대표문제 : 큰수만들기<br>
<img src="https://velog.velcdn.com/images/2taesung/post/757a9704-42e7-4038-a58c-4624bcbc97f9/image.png"></p>
<h2 id="꿀팁으로-강사님의-문제풀이-과정을-엿볼-수-있었음">꿀팁으로 강사님의 문제풀이 과정을 엿볼 수 있었음.</h2>
<ol>
<li>
<p>맨 처음에 탐색을 고려해본다 그러나 제한조건에 걸림<br>
=&gt; N이 백만 이상이면 O(N), O(N log N) 만이 가능<br>
=&gt; 고로 모든 케이스를 찾는 탐색은 효율성에 걸린다.</p>
</li>
<li>
<p>아이디어 제시<br>
=&gt; 테스트에 이 아이디어를 대입해본다<br>
=&gt; 틀리면 수정 틀리면 수정... 반복</p>
</li>
<li>
<p>이를 통해 여러 조건들이 생성 되는데 하나하나 텍스트로 정리해본다</p>
</li>
<li>
<p>해당 조건들에 맞는 자료구조 등 문제유형이 파악되면 적용한다.</p>
</li>
</ol>
<p>현재 상황에서 제일 합리적인 판단을 하고 그리드의 특징은 규칙을 이용해 선형 시간을 사용한다<br>
=&gt; 결국엔 모든 값을 구하는 방법도 있기는 한데 제한시간으로 걸린다. 그러므로 기존에 알고 있는 명칭으론 가지치기 해서 처리하는 방법이라고 생각됨.</p></div></div>

2taesung.log

Taesung Lee

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.
1. 그리디란?
매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘. 단, 최적해를 보장해주지 않는다.
=> 다음과 같이 A에서 B/D를 선택할때 최적의 선택.
=> 그리고 B를 갔을때 최적의 선택 .... 으로 이어짐.
=> 결과적으로 전체를 봤을때는 최고의 선택이 아닐 수 있음
실제 사용 예시
거스름돈 반환 문제
2. 그리디 알고리즘의 특징
보통 최적해를 구하는 알고리즘보다 빠른 경우가 많음
=> 주로 선형 단위에서 해결이 됨
크루스칼, 다익스트라 알고리즘 등에 사용됨
직관적인 문제 풀이에 적합
=> 하나의 특정 문제풀이 방식이 아닌 하나의 개념으로 봐야함
3. 코테
핵심키워드 : 가장 큰 순서대로, 가장 작은 순서대로 
참고 상황 : 탐색으로 풀 수 있으나 제한조건이 걸려있는 상황
대표문제 : 큰수만들기
꿀팁으로 강사님의 문제풀이 과정을 엿볼 수 있었음.
맨 처음에 탐색을 고려해본다 그러나 제한조건에 걸림
=> N이 백만 이상이면 O(N), O(N log N) 만이 가능
=> 고로 모든 케이스를 찾는 탐색은 효율성에 걸린다.
아이디어 제시 
=> 테스트에 이 아이디어를 대입해본다
=> 틀리면 수정 틀리면 수정... 반복
이를 통해 여러 조건들이 생성 되는데 하나하나 텍스트로 정리해본다
해당 조건들에 맞는 자료구조 등 문제유형이 파악되면 적용한다.
현재 상황에서 제일 합리적인 판단을 하고 그리드의 특징은 규칙을 이용해 선형 시간을 사용한다 
=> 결국엔 모든 값을 구하는 방법도 있기는 한데 제한시간으로 걸린다. 그러므로 기존에 알고 있는 명칭으론 가지치기 해서 처리하는 방법이라고 생각됨.

그리디

댓글