![]()
그리디 알고리즘 그리디 알고리즘은 매번 최적의 선택을 하여 결국 결과가 최적이 되게 하는 알고리즘이다. 또한 그리디 알고리즘은 최소 비용 신장트리, 크루스칼 알고리즘, 다익스트라 알고리즘 등 다양한 알고리즘에 응용되어 사용되므로 Greedy 특징을 잘 알아두어야한다. 하지만 그리디 알고리즘은 투포인트처럼 특정한 풀이방식이 정해져있는 알고리즘과는 다르게 문제마다 풀이방식이 다르므로 처음 접하면 어렵게 느낄 수 있는 알고리즘이다. 01. 그리디 알고리즘이란? 그리디 알고리즘은 직역하자면 탐욕 알고리즘으로 미래를 고려하지 않고 오직 현재 시점에 가장 좋은 선택을 하는 알고리즘이다. [예시] 단위가 다른 동전들로 총액 K를 만들 수 있는 최소한의 동전 개수를 구한다. 1,620원을 만들려면 500원 동전 3개,..
에라토스테네스의 체란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 소수란? 간단하게 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의할 수 있다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간복잡도로 빠르게 구현할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나눌 수 있는 둘 중에 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 ..
1. Hash Table 해쉬 테이블(Hash Table)은 입력값이 키-값 쌍(Key-value pair)일 때 이를 저장하는 자료구조이다.대부분의 언어에서 해쉬 테이블은 이미 구현되어 있다. 예를 들어 자바스크립트에서 객체(Object) 자료형이 해쉬테이블로 구현되어 있고 파이썬은 dictionary 자료형을 해쉬 테이블로 사용할 수 있다.해쉬 테이블의 장점Hash tableHash tableLinked listArrayaccessO(1)O(n)O(1)insertO(1)O(1)O(n)append O(1)O(1)deleteO(1)O(1)O(n)빠른 검색 및 삽입유연한 크기 조정(메모리 효율 좋음)해쉬 테이블의 단점무작위성(순서가 없으므로 순서대로 자료를 저장해야 할 경우 list 사용) 해쉬 테이블은 ..
오늘은 표현식/ 표기법 알고리즘에 대해 정리해보겠습니다 :) 📍 계기표기법에 대해 가장 먼저 알게 되었을 때는 정보처리기사 시험을 준비하면서 접하였습니다.그 후 백준 1935번 문제를 마주하게 되었고, 후위표현식 관련 알고리즘을 다뤘습니다. 📍 설명표기법 즉, 표현식에는 전위(prefix) / 중위(infix) / 후위(postfix) 표기법으로 나뉩니다.1. 전위 표기법연산자를 먼저 표기하고 연산자가 필요한 피연산자를 나중에 표기하는 방법ex) +12 2. 중위 표기법연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법ex) 1+2 3. 후위 표기법피연산자를 먼저 표시하고 연산자를 나중에 표기하는 방법이다.컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하..
