ENAN

Developer, Artist, Traveler

공부/알고리즘 스터디 2

#2. 구현

구현이란? 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 : 피지컬 딱히 뭐 설명할 말이 없다. 그냥 주어진 대로 구현하는 형식의 문제다! 이 파트에서 다루는 문제 유형 지금 읽고있는 킹동빈 님의 '이것이 취업을 위한 코딩 테스트다' 에서는 구현 파트에 아래의 두 유형의 문제를 엮었다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현 문제의 특징 구현 문제의 특징으로는, 사소한 입력 조건 등을 문제에서 제시해 준다. 그렇기 때문에 보통 문제 길이가 긴 편이라, 문제를 읽기도 전에 문제 길이에 압도당해 지레 겁을 먹는 경우가 많다. 그러지 말자! 딱히 어떤 알고리즘 지식을 알고 있어야만 풀 수 있..

#1. Greedy

그리디(Greedy) 알고리즘이란? 그리디 알고리즘이란 어떠한 문제가 있을 때 단순 무식하게, 탐욕적(greedy)으로 문제를 푸는 알고리즘을 말한다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 하나의 문제를 여러 작은 문제(단계)로 나누고 작은 문제(단계)에서의 답을 통합해서 하나의 문제의 대한 답을 내놓는다는 근본적인 개념은 브루털포스나 DP와 비슷하지만, 그리디 알고리즘이 갖는 차이점은 모든 선택지를 고려하지 않는다는 것이다. 그리디 알고리즘은 각 단계에서 가장 좋은것만 고르게 된다. 그리디 알고리즘은 정렬, 최단경로 등의 다른 알고리즘과 비교했을 때 사전에 외우고 있는 지식 없이도 풀 가능성이 높은 유형이다. 따라서 코딩테스트에서 그리디 알고리즘 유형..