알고리즘

[알고리즘] 최대공약수와 최소공배수 - 간단하게 구현해보기 (+ 유클리드 호제법 알고리즘) (C++)

최대공약수란 무엇인가? 최대공약수는 초등학교 수학 시간에 배우는 내용으로, 아마 이 글을 보시는 여러분이라면 이미 아시겠지만, 그 개념을 한 번 더 짚고 넘어가보자. 쉬운 이해를 위해 실제 정의가 아닌 초등학교 교과서에 제시된 내용을 참고하였다. n의 약수 : n을 나누어 떨어지게 하는 수 a, b의 공약수 : a와 b의 공통된 약수 a, b의 최대공약수 : a와 b의 공통된 약수 중 가장 큰 수 이 개념을 이용하여 반복문으로 다음과 같이 최대공약수를 구하는 함수 코드를 쓸 수 있다. #include #include // 최대공약수를 계산하는 함수 long getBCD (long a, long b) { for(int div = min(a, b); div > 0; div--) { if((a % div ==..

[알고리즘] 버블 정렬(Bubble Sort) 알고리즘 쉽게 구현해보기 (C++)

이 글은 프로그래밍에 능숙하지 않으신 분들도 어렵지 않게 이해할 수 있도록 최대한 쉽게 풀어 설명한 글입니다. 왜냐하면 저도 초보자거든요. 버블 정렬이란 무엇인가? 버블 정렬은 대표적인 정렬 알고리즘 중 하나로 원소를 정렬하는 모습이 마침 거품이 올라오는 모습같다고 해서 붙여진 이름이다. 버블 정렬은 아래와 같은 알고리즘으로 동작한다. 『 데이터의 수를 N이라고 하자. 아래의 과정을 N번 반복한다. 배열의 0번 칸의 숫자가 1번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다 배열의 1번 칸의 숫자가 2번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다 ... 배열의 N-2번 칸의 숫자가 N-1번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다. 』 즉, 한 번의 순환이 끝나면 조사한 모든 원소 중 가장..

[백준 2309번] #1. 일곱 난쟁이 - 처음으로 해본 PS (C++)

처음으로 백준 온라인 저지에서 문제 같은 문제를 풀어보았습니다. 어떤 문제로 시작하는 것이 좋을까 구글링 하다가 한국정보올림피아드 초등부 문제부터 풀어보는 것이 좋다고 해서 무작정 찾아 들어가 푼 문제입니다. 알고 보니 이 문제는 완전 탐색(Brute Force) 문제라던데 필자는 아직 안 배운 내용이라 그냥 선택 정렬 알고리즘으로 풀었습니다. 나중에 실력을 더 쌓고 완전 탐색으로 다시 한 번 풀어보겠습니다. 어쨌든 처음으로 푼 문제라는 것이 중요하니까!! 문제 www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무..

[알고리즘] 선택 정렬(Selection Sort) 알고리즘 쉽게 구현해보기 (C++)

이 글은 프로그래밍에 능숙하지 않으신 분들도 어렵지 않게 이해할 수 있도록 최대한 쉽게 풀어 설명한 글입니다. 선택 정렬이란 무엇인가? 선택 정렬 알고리즘은 기본 정렬 알고리즘 중 하나로 다음 아래의 과정을 반복하는 알고리즘이다. 1. 배열의 주어진 범위에서 최솟값의 위치를 찾는다. 2. 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꾼다. 3. 이후, 해당 범위의 가장 앞 자리를 제외한 나머지 범위에 대해 위의 과정을 반복한다. 위의 과정을 모두 마치면 배열 내 정수의 원소가 오름차순(점점 커지는 순)으로 정렬된다. 선택 정렬 알고리즘 구현해보기 먼저, 메인 함수에는 정수형 배열에 원소값을 입력 받고 함수로 구현한 알고리즘을 통해 배열 원소를 오름차순으로 재배열 한 후 반복문으로 각 원소 값을 출력하는..