▼ Why ? What ? 1일 1알고리즘 스터디를 진행하다가 소수와 약수를 구해야 하는 문제들을 해결하면서, 내가 해결한 방법보다 훨씬 더 효율적이고 빠르게 소수와 약수를 구할 수 있는 방법을 알게 되었고, 기억해두면 나중에 유용하게 사용할 일이 있을 것 같아서 이렇게 정리해두게 되었다.▼ 에라토스테네스의 체 알고리즘 에라토스테네스의 체 ?고대 그리스의 수학자 에라토스테네스가 만들어낸 "소수(Prime Number)를 찾는 방법"이라고 한다.➙ 특정 정수 이하의 모든 소수를 찾기 위해서 소수를 찾는 것이 아니라 소수의 반대인 합성수(Composite Number)를 제거하는 원리 ! 에라토스테네스의 체 알고리즘를 이용한 "소수" 찾기자연수 `n`이 주어졌을 때, `2`부터 `n`까지의 모든 수가 소수가..
▼ Why ? What ? 이번 주는 벌써 GDSC 알고리즘 스터디 마지막 주차이고, 마지막 주차인 만큼 '동적 프로그래밍(Dynamic Programming)' 이라는 것에 대해 공부해볼 것이다. 사실 이 DP라는 알고리즘은 처음 들었을 땐 감도 안잡히기도 하고 분할-정복(Divide-Conquer) 알고리즘과 그리디(Greedy) 알고리즘과 어떤 차이가 있는지 헷갈려서 따로 공부한 적이 있었다. 그렇게 비교하면서 공부하고 DP 알고리즘을 적용해서 문제를 해결하는 과정을 찾아보니 개념은 얼추 이해가 되는 것 같아서, 이번 주차엔 개념은 가볍게 복습해보고 관련 문제를 스스로 풀어보는 데 집중을 해보려고 한다. 이 DP 알고리즘이 Greedy 알고리즘 처럼 문제를 많이 풀어보는 것도 중요하지만, 그렇다고 ..
▼ Why ? What ? 이번 주차엔 매우 중요한 알고리즘 중 하나인 '그리디(Greedy) 알고리즘' 에 대해 복습해보고, 관련 문제를 풀어보는 시간을 가졌다. 이 그리디 알고리즘에 대해선 PCCP 알고리즘 특강 때 알게 돼서 그당시엔 많이 생소한 알고리즘이었는데, 최근에 "알고리즘" 강의 시간에도 배우기도 했고 최근에 자주 접하게 되는 알고리즘이라 개념적으로는 많이 친숙해진 알고리즘인 것 같다. (근데, 개념만 계속 공부해보고 관련 문제는 많이 안풀어본 듯...) 그리디 알고리즘은 공부하면 할수록, 관련 문제를 많이 풀어보고 어떤 문제가 그리디 알고리즘을 적용하기에 적합한 문제인지 감을 잡는 연습이 중요하다는 생각이 들어서, 이제 개념만이 아니라 관련 문제들을 풀어보는 연습이 필요할 것 같다 ! ▼..
▼ Why ? What ? 오늘 "알고리즘" 강의 시간에 배운 '버블 정렬(Bubble Sort)', '선택 정렬(Selection Sort)', '삽입 정렬(Insertion Sort), '쉘 정렬(Shell Sort)' 에 대해 배웠다. 사실 '버블 정렬' 이나 '선택 정렬', 그리고 '삽입 정렬' 과 같은 기법은 '퀵 정렬(Quick Sort)' 나 '합병 정렬(Merge Sort)' 에 비해 간단하고 기본적인 정렬이기 때문에 잘 알고 있지만, 오늘 처음 알게된 '쉘 정렬(Shell Sort)' 라는 것이 '삽입 정렬' 을 활용하는 정렬 기법이기도 해서 같이 복습하고 정리해보려고 한다. 그리고 각 정렬마다 요구되는 시간복잡도에 대해서도 생각해보려고 한다. ( '퀵 정렬(Quick Sort)', '합..
▼ Why ? 지금 수강하고 있는 "알고리즘" 강의 시간에 분할정복 알고리즘과 그리디 알고리즘에 이어서 동적 프로그래밍(DP) 알고리즘까지 배우게 됐다. 근데 이 세 알고리즘이 어떤 부분에서 차이가 있는지, 그리고 "동전 거스름돈(Coin Change)" 같은 문제를 해결할 때 '그리디 알고리즘' 으로 해결하는 방식과 'DP 알고리즘' 으로 해결해보는 방식을 비교해보라고 하셨는데, 동시에 생각해보니까 좀 헷갈리기도 하는 것 같고 워낙 중요한 알고리즘이다보니 나중에 찾아보기 쉽도록 이번 기회에 따로 정리해놓으려고 한다. 그리고 DP를 사용해야 하는 조건인 '최적 부분 구조' 와 '중북된 서브 문제' 에 해당하는 것이 무엇인지도 Coin Change 문제를 기반으로 공부해봤다.▼ What ?분할정복, 그리디..
▼ What ? 이번 주차엔 흔히 "브루트 포스(Brute Force)" 라고 알려진 '완전 탐색' 알고리즘에 대해서 공부해보고 관련 문제도 풀어보려고 한다. 가장 기초적이고 기본적인 알고리즘이기 때문에 "이산수학" 시간에도 배웠던 개념이고 DFS, BFS를 포함하는 중요한 파트이다. 또한, "Dynamic Programming (DP)" 처럼 어떻게 설계를 하냐에 따라 효율성이 매우 크게 달라질 수 있고, 사용해선 안되는 경우에 사용하게 되면 엄청난 메모리가 소모되고 오버헤드가 발생할 수 있는 알고리즘이기 때문에, 기본적인 알고리즘이라고 절대 가볍게 짚고 넘어가선 안된다. ▼ 완전 탐색 완전 탐색 ? 모든 경우의 수를 다 체크해서 주어진 문제의 '최적의 해' 를 찾는 기법으로, 다른 알고리즘들과 달리 ..
