에라토스테네스의 체란? 에라토스테네스의 체란 소수를 판별할 때 사용하는 알고리즘으로 고대 그리스 수학자 에라토스테네스가 발견했다. 여기서 말하는 소수란, 1과 자기 자신만을 약수로 가지는 수를 말한다. 에라토스테네스의 체 원리 1) 아래 그림과 같이 1에서 100까지의 수가 있다. 2) 1은 소수가 아니기 때문에 제외하고 2부터 생각해보자. 2는 소수에 해당하기 때문에 소수임을 체크해주고 2의 배수들은 소수가 아니기 때문에 제외시킨다. 3) 그다음 수인 3을 보면 제외되지 않았기 때문에 소수이다. 그리고 3의 배수를 모두 제외시킨다. 4) 그다음 수인 4는 제외됐으므로 5를 확인한다. 5는 제외되지 않았기 때문에 소수이다. 5의 배수까지 모두 제외시키면 아래와 같다. 5) 이렇게 계속해서 반복하다 보면 ..
유클리드 호제법이란 무엇인가? 유클리드 호제법(Euclidean Algorithm)은 두 자연수의 GCD(최대공약수 - Greatest Common Devisor)를 구하는 알고리즘이다. 서로 호(互) 덜 제(除) 법 법(法) 유클리드 호제법의 원리 두 개의 자연수 A, B가 있다. (A > B) 그리고 A를 B로 나눈 나머지 R이 있다. R이 0이라면, A와 B의 최대공약수는 B이다. R이 0이 아니라면, A와 B의 최대공약수는 B와 R의 최대공약수와 같기 때문에 A에는 B, B에는 R을 대입한 후 1번으로 돌아간다. 재귀로 구현하기 C / C++ int get_gcd(int A, int B) { int R = A % B; if(R == 0) return B; else return get_gcd(B, ..
완전 탐색, 브루트 포스란 무엇인가? 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 브루트 포스의 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 브루트 포스의 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 브루트 포스의 종류 브루트 포스는 크게 선형구조와 비선형 구조로 나눌 수 있다. 선형 구조 ..
재귀함수란 무엇인가? 자기 자신을 호출하는 함수를 재귀함수(Recursive Function)라고 하며 이때 하는 호출을 재귀호출(Recursive Call)이라고 한다. 팩토리얼, 하노이 탑과 같은 문제에서 많이 사용된다. 재귀 함수의 장점 직관적이며 간단하게 구현할 수 있다. 깊이 우선 탐색, 백트래킹, 분할 정복 등 많은 알고리즘에서 사용되기도 해서 기초가 되는 개념이다. 재귀 함수의 단점 재귀함수의 종료 조건을 잘 설정해주지 않으면 재귀함수를 빠져나오지 못하게 되면서 무한루프에 빠질 수 있다. 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다. 불필요한 반복 연산을 하게 될 가능성이 있다. 팩토리얼 문제 재귀함수로 해결하기 팩토리얼을 구하는 함수가 있다고 생각해보자. 5팩토리얼을 재귀..
BEFORE START 2020년 11월 5일 목요일, 6시에 퇴근 후에 저녁을 먹고 카페로 가서 7시 30분부터 진행하는 월간 코드 챌린지 시즌 1의 마지막 테스트에 참여하였다. 월간 코드 챌린지 시즌 1은 9월, 10월, 11월 각각 4문제씩 출제하여 총 5문제 이상 풀어내면 이벤트에 응모할 수 있고, 경품은 키보드, 굿즈, 기프티콘, 편의점 상품권 등이 있었다. 약 6~7천 명 정도 응시를 하는데 경품이 추첨이 100명이라 약간 기대할 수 있을지 모르겠다. (치킨 먹고싶다) 하지만 지금 나는 9월에는 개인 사정으로 응시를 못했었고, 10월에는 4문제 중 2 솔, 나머지 두 문제는 부분점수를 받아 이번 11월 테스트에서 최소 3 솔은 해야 하는 상황이었다. 경품 응모 조건을 채우는 것을 목표로 가볍게..
BEFORE START 2020년 10월 8일 목요일, 회사 끝나고 프로그래머스에서 진행하는 월간 코드 챌린지 시즌1에 참여하였다. 9월부터 11월까지 매달 4문제씩 출제되고 총 12문제 중 5문제 이상 풀면 이벤트에 응모할 수 있는 이벤트다. 나는 9월에 개인 사정으로 인해 참여를 못했다. 때문에 8문제 중 5문제 이상 풀어내야 하는 상황.. 10월 / 11월 각각 최소 2~3문제씩은 풀어야 하는데 잘할 수 있을지 모르겠다. 이벤트에 응모하는걸 목표로 10월 11월에 도전해보자. 오후 7시 30분부터 시작이었는데 접속이 20분가량 안 돼서 20분이 연장되어 오후 10시 50분에 종료되었다. 오늘은 시험을 치는 사람들이 많았나 보다.. 나 같은? 언어는 Python3를 사용했다. 진행 1번 문제는 주어진..
** C / C++17, Java, Python 언어를 기반으로 진행했으며 모든 문제는 BOJ에서 풀어보실 수 있습니다.** 모든 코드는 불펌을 금지하며 학습을 목적으로 글을 작성하였습니다. 코드 작성자 : 본인 (백준 ID: happiness96) 알고리즘을 시작하기 전에 알고리즘을 시작하기 위해서는 먼저 프로그래밍 언어에 대한 기초 지식이 필요하다고 하였다. 자신이 프로그래밍 언어에 대한 기초 바탕이 돼있는지 확인하기 위해 간단히 몇 문제를 풀어볼 것이다. 앞서 조건문과 반복문을 잘 이해하고 있는지 테스트해보는 문제를 풀어보았다. 그렇다면 이번에는 무엇일까? 아마 PS를 하면서 런타임 에러를 가장 많이 발생시키는 녀석이 바로 이 녀석일 것이다. 손 풀기 정도로 생각하고 아직 이 정도도 어렵거나 벅차다..
** C / C++17, Java, Python 언어를 기반으로 진행했으며 모든 문제는 BOJ에서 풀어보실 수 있습니다.** 모든 코드는 불펌을 금지하며 학습을 목적으로 글을 작성하였습니다. 코드 작성자 : 본인 (백준 ID: happiness96) 알고리즘을 시작하기 전에 알고리즘을 시작하기 위해서는 먼저 프로그래밍 언어에 대한 기초 지식이 필요하다고 하였다. 자신이 프로그래밍 언어에 대한 기초 바탕이 돼있는지 확인하기 위해 간단히 몇 문제를 풀어볼 것이다. 손 풀기 정도로 생각하고 아직 이 정도도 어렵거나 벅차다면 프로그래밍 언어를 더 공부해야 할 때이다. 문제 목록 [2557번] Hello World [1000번] A + B [9498번] 시험 성적 [2884번] 알람 시계 [10817번] 세 수 ..
알고리즘.. 사실 나는 알고리즘이라는 분야를 조금 늦게 접한 편이다. 24살.. 5학년 때 ㅠㅠ 개인적으로는 미리 준비하지 못한 것에 대한 미련이 없기 때문에 지금은 취미로 알고리즘 공부를 하고 있다. 마냥 알찬 삶을 살아온 것이 아니라서 실력으로 보면 마냥 허접하다. 직장 생활을 하면서도 알고리즘 공부를 놓지 못하는 이유는 그만한 매력을 느끼고 있기 때문이 아닐까 생각한다. ㅎㅎ 알고리즘에 대해 이것저것 찾아보신 분들이라면 세상에는 수많은 괴물들이 존재하고 있다는 사실을 알고 있을 것이다. 하지만 기죽을 필요는 전혀 없다. 이 글을 보고있는 당신이 "지금 알고리즘 공부를 하기에 늦지 않았을까?"라고 고민한다면 그런 생각할 시간에 문제 하나를 더 푸는 것을 추천한다. 실은 나보다 훨씬 더 유능하고 똑똑한..