순열과 조합 실생활 예 순열과 조합의 차이는 순서를 정하느냐 그렇지 않느냐의 차이입니다. 순열 : 중국집 메뉴 5개 중 2개의 메뉴를 순서대로 먹는 경우의 수 조합 : 중국집 메뉴 5개 중 2개의 메뉴를 주문하는 경우의 수 순열이란? 순열이란 서로 다른 n개중 r개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 예를 들어 어느 중국집에 5개의 메뉴(a,b,c,d,e)가 있다고 해봅시다. 이때 5개의 메뉴(a,b,c,d,e)중 2개의 메뉴를 순서대로 먹는 경우의 수는 몇가지가 있을까요? 먼저 첫번째로 먹을 메뉴를 정하려면 이때 첫번째 메뉴가 될 수 있는 경우의 수는 5가지 입니다. 그리고 나서 첫번째 메뉴로 지정된 메뉴를 제외한 나머지 4가지의 메뉴로 두번째로 먹을 메뉴를 선택한다고 가정하면 이때의 ..
팩토리얼 ( ! ) 팩토리얼이란 서로 다른 n개를 나열하는 경우의 수를 의미합니다. 기호로는 n! 이렇게 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱합니다. 순열 ( nPr ) 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) 조합 ( nCr ) 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 중복 순열 ( nπr ) 중복 순열이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) 중복 조합 ( nHr ) 중복 조합이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 같은 것이 있는 순열 순열이 같은 것이 포함된 원소들을 나열하는 ..
에라토스테네스의 체란? 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이며 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식이며 일종의 노가다 방식이라 상당히 무식한 방법이지만 이 방식이 프로그래밍에서는 상당히 효율적인 방법론이 됩니다. 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧습니다. 특정 범위에서의 모든 소수를 찾을때 가장 효율적인 알고리즘 에라토스테네스..
유클리드 호제법이란? 유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘입니다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 (C / C++) 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) r..
컴퓨터를 오랜 기간 사용하다 보면 항상 부족한 용량에 시달리는 경우가 많습니다. 이럴 때 SSD를 추가로 달아 용량을 늘려주면 좋은데요. 최근에는 SSD 가격도 많이 떨어져 부담 없는 선에서 컴퓨터 용량을 추가할 수 있으니 저장공간이 부족하시다면 한번 시도해보는 것도 괜찮을 것 같습니다. 저는 이번에 LG 2020그램을 사전 구매하며 사은품으로 받은 1TB짜리 SSD를 추가하였습니다. 2020년도 2월 기준 1TB SSD는 제조사마다 다양하지만 가장 많이 쓰는 삼성 SSD의 경우 약 26만 원 정도 하네요. ※ 노트북용 SSD는 아래 링크에서 쿠팡 최저가로 구매하실 수 있습니다. 노트북 SSD 업그레이드 진행 방법 SSD추가는 노트북마다 조금씩 상이하겠으나 노트북 뒤 하판을 뜯어 추가 SSD 슬롯에 추가..
램(RAM)은 하드디스크로부터 일정량의 데이터를 복사해 임시 저장한 후, 이를 필요 시마다 CPU에 빠르게 전달하는 역할을 합니다. 램(RAM)의 용량이 충분하다면 속도가 느린 하드디스크를 배제하고 CPU와 램끼리만 데이터를 교환하므로 전반적인 작업을 고속으로 처리할 수 있습니다. 램(RAM)의 용량이 작으면 하드디스크와 CPU끼리의 데이터 교환 작업을 해야 하므로 전반적인 작업 속도가 크게 저하됩니다. 특히 여러 개의 프로그램을 동시에 띄워놓고 작업할 때에는 작업 속도의 체감이 많이 됩니다. 요즘은 대부분 8GB의 램(RAM)을 사용하지만 무거운 프로그램, 혹은 프로그램을 여러개 띄워놓고 작업하실 분이시라면 램(RAM)을 업그레이드 시키는것이 좋습니다. 램(RAM)의 용량은 클수록 유리하지만 저는 16..
세상에는 코딩을 잘하는 사람들이 참 많다. 그중에서는 얼마 배우지도 않았는데 이해력이 남들보다 훨씬 빠른 사람들, 흔히들 코딩에 재능이 있다고 하는 사람들도 있다. 나는 코딩을 잘하는 사람들을 열심히 관찰하고 따라 해보려 노력하고 있다. 오늘은 내가 지금까지 그들을 관찰하며 느꼈던 코딩을 잘하는 방법에 대해 이야기해보려 한다. 혼자서 해결하는 능력 프로그래밍이란 끊임없이 오류와 마주치고 그 오류를 해결하는 과정의 연속이다. 이 오류들을 혼자서 해결할 수 있느냐 없느냐에서 실력이 갈린다. 가끔 『모르면 물어봐야지』라는 생각을 가진 개발자들이 있다. 나는 이 생각에는 동의하지 않는다. 이러한 생각은 사람을 의존적으로 만들어 문제를 스스로 해결할 수 있는 능력의 발전을 막기 때문이다. 영화를 제대로 보려면 중..
이진탐색이란? 이진탐색(이분검색)은 말 그대로 검색할 자료를 반씩 나누어 그 중간값을 찾는 대상값과 비교하는 작업을 반복하여 자료를 찾는 검색을 뜻하며 빠른속도로 자료를 찾을 수 있습니다. 단 이진탐색을 하기위해서는 데이터가 정렬되어있어야 합니다. 이진탐색 과정 이진탐색을 할 데이터들이 위와 같이 정렬되어있다고 가정하고 숫자 7을 찾는 이진탐색과정을 알아보겠습니다. 1. 첫번째 주소와 마지막 주소의 위치를 활용하여 중간 위치를 계산합니다. 중간위치 = (0+9)/2 = 4.5 -> 소수점절삭 -> 4 2. 중간위치 4번째주소에 있는 값 8이 찾으려는 값인지 확인합니다. 7은 8보다 작으므로 찾으려는 값의 범위는 0~4번째 주소입니다. 3. 찾으려는 범위의 첫 번째 주소와 마지막 주소의 위치를 이용하여 중..
입력받은 그레이코드를 2진수로 변환하기 그레이 코드를 이진수로 변환할 때는 첫번째 이진수는 그레이 비트를 그대로쓰고, 두번째 이진수 비트부터는 왼쪽에 구해놓은 2진수와 변경할 그레이코드를 XOR연산하여 씁니다. [C언어] 입력받은 2진수를 그레이코드로 변환하기 C언어 / C++ 코드 #include main(){ int i; int input[4], cont[4]; printf("그레이코드: "); for(int i=0; i
입력받은 이진수를 그레이코드로 변환하기 이진수를 그레이 코드로 변환할때는 첫번째 그레이 비트는 이진수 비트를 그대로 내려쓰고, 두번째 그레이 비트부터는 변경할 이진수의 해당번째 비트와 그 왼쪽의 비트를 XOR연산을 하여 내려적습니다. [C언어] 입력받은 그레이코드를 2진수로 변환하기 C언어 / C++ 코드 #include main(){ int i; int input[4], cont[4]; printf("이진수 입력 :"); for(int i=0; i
입력받은 이진수의 보수구하기 1의 보수는 0은 1로 1은 0으로 변경하면 되고, 2의 보수는1의 보수에 1을 더하면 됩니다. 즉 01100의 1의 보수는 10011이고, 2의 보수는 10100입니다. 이 로직을 어떻게 알고리즘으로 구현하느냐가 관건인데요. 1의 보수를 if문을 통해서 구해도 되지만 0은 1로, 1은 0으로 변환할때는 1에서 변환할 값을 그냥 빼주면 1의 보수를 좀 더 간편하게 구하실 수 있습니다. 2의 보수를 구할때는 1의 보수에 1을 더하면 되는데 이진수의 각자리가 배열의 각 요소에 분리되어 있으므로 맨 오른쪽 배열의 값에 1을 더해서 만약 맨 오른쪽 배열의 수가 1을 초과하면 앞자리 수로 1을 반올림 해줍니다. C언어/C++ 코드 #include main() { int a[5],b1[..
입력 받은 10진수를 2진수로 변환하기 10진수를 2진수로 변환하려면 10진수를 2로 나누어 몫 과 나머지를 구한 후 나머지는 출력할 배열에 저장하고 몫은 또 2로나누어 나머지를 구하여 출력할 배열에 저장하는 과정을 몫이 0이 될때까지 무한반복 후 몫이 0이되었을경우 저장한 출력배열을 거꾸로 출력시키면 됩니다. C언어 / C++ 코드 #include main() { int num, num2, b, mok, nmg, i; int a[10]; scanf("%d",&num); num2 = num; b = -1; do{ b++; mok = num/2; nmg = num-mok*2; a[b] = nmg; num = mok; }while(mok!=0); printf("%d를 2진수로 변환한 값 = ",num2); ..
정수를 입력받아 소인수를 구해 출력하기 어떤 수를 소인수 분해하려면 입력받은 수를 2부터 차례대로 입력받은 수(NUM)의 제곱근까지의 숫자로 나누어 떨어지는지를 계산하시면 됩니다. 제곱근까지의 수 중 입력받은 수(NUM)을 처음으로 나누어 떨어지게 하는 수가 있으면 그 수는 소수이고, 입력받은 수(NUM)는 소인수가 됩니다. 소인수를 구했으면, 그때의 몫을 입력받은 수(NUM)에다가 치환하고 다시 NUM의 제곱근까지의 숫자로 나누는 작업을 반복합니다. 만약 제수가 NUM의 제곱근보다 커지면 그떄는 몫인 NUM자체가 그 수의 소인수가 됩니다. C언어 / C++ 코드 #include #include main() { int num,b,c,d,mok,nmg; int a[100]; scanf("%d",&num);..