구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정, 모든 범위의 코딩테스트 문제 유형을 포함하는 개념 Problem Thinking Solution 완전 탐색 모든 경우의 수를 주저 없이 다 계산하는 방법 시뮬레이션 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 구현 시 고려해야할 메모리 제약 사항 파이썬에서의 리스트 크기에 따른 메모리 사용량 데이터의 개수(리스트 길이) 메모리 사용량 1000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 파이썬은 다른 언어에 비해서 구현상의 복잡함은 적은 편이지만 데이터 처리량이 많을 때는 메모리 제한을 고려해야한다. 리스트를 여러 개 선언하고, 그 중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로..
그리디 알고리즘(Greedy) 어떤 문제가 있을 때 탐욕적으로 문제를 푸는 알고리즘. 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 다만 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰(작은) 순서대로'와 같은 기준을 알게모르게 제시해준다. 예제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 돈이 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야할 돈이 N원일 때 거슬러줘야할 동전의 최소 개수를 구하라. 단 거슬러 줘야할 돈 N은 항상 10의 배수이다. 가장 큰 화폐 단위부터..
복잡도(complexcity) 알고리즘의 성능을 나타내는 척도 시간 복잡도(Time complexcity) : 특정한 크기의 입력에 대하여 알고리즘에 대하여 얼마나 오래 걸리는지 의미 공간 복잡도(Space complexcity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미 보통 시간 복잡도와 공간 복잡도는 거래 관계(trade off)이다. 연산 횟수를 줄이는 대신 메모리를 더 소모하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 시간 복잡도(Time complexcity) 알고리즘 문제를 풀 때는 흔히 시간복잡도를 고려한다. 시간 복잡도를 표기할 때는 빅오(Big-O) 표기법을 사용한다. 빅오 표기법 간단 정의 : 빠르게 증가하는 항만 고려하는 표기..
