전체 글

비교 방법 1. 각각 1000, 10000, 100000 크기의 배열 A, B에 0 ~ 999 사이의 난수를 채운다. (단, 동일한 난수로 채운다.) 2. 정렬 안된 상태, 정렬된 상태, 역순 정렬된 상태에서 선택 정렬과 삽입 정렬을 하여 시간을 비교한다. 사용 코드 #include #include #include #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void bubble(int *L, int n) { for (int i = 0; i < n - 1; i++) for (int j = 0; j < n - 1 - i; j++) if (L[j] < L[j + 1]) swap(&L[j], &L[j + 1]); } voi..

42 서울이란 2019년 대한민국 정부가 소프트웨어 인재 양성, 새로운 교육 시스템의 개발, 소프트웨어 개발자 생태계 활성화를 그 미션으로 하는 이노베이션 아카데미 재단을 설립했다. 프랑스에 위치한 세계적으로 유명한 IT 인재 양성 기관인 에꼴 42(Ecole 42)와 계약을 체결해 교육 시스템을 가져왔다. 교육 시스템은 교수도, 교재도, 학비도, 학위도 없다. 자기 주도 학습으로 진행되며 개인이 공부하며 문제 해결 능력을 기르는 게 중요하다고 한다. 지원 자격은 고등학교 졸업자면 성별, 경력, 국적에 상관없이 누구나 지원 가능하다. 대부분 20대가 주를 이루지만, 다른 연령대의 사람들도 많이 만날 수 있다고 한다. 정부 주도로 설립한 교육 기관이다 보니 운영을 정부의 예산으로 한다. 물론 여기에는 학생..

문제 [문제] 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) [출력] 상근이가 배달하는 봉지의 최소 개수를 출력..

Code golf란 Golf scripting이라고도 부른다. 알고리즘이 주어졌을 때 가장 짧은 코드로 구현하는 방법이다. 이름은 가장 낮은 점수를 획득해야 하는 골프와 비슷하다고 하여 지어졌다. 숏 코딩이라고도 부르는데 대부분 실용적으로 사용하지는 않고, 알고리즘의 이해나 재미로 해보는 경우가 많다. 골프 쳐보기 C 언어에서 두 정수의 값을 입력받아서 합을 출력하는 코드는 다음과 같다. #include int main() { int a, b; scanf("%d%d", &a, &b); printf("%d", a + b); return 0; } 116byte 이제 이 코드를 가지고 골프를 쳐보자. 표준처럼 main 함수를 int main()으로 정의했는데 사실 main()으로만 정의해도 동작한다. K&R이..

문제 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } [문제] 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. - fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. - fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. - 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. - f..

Memoization(메모이제이션)이란 동적 계획법(dynamic programming)의 핵심 기술로 동일한 계산을 반복해야 할 때, 이전에 계산한 값들을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 방법이다. 보통 예시로 피보나치 수열을 사용한다. 피보나치 수열 피보나치 수열(Fibonacci sequence)은 제0항을 0, 제1항을 1로 두고, 제2항부터는 바로 앞의 두 수를 더한 수로 놓는다. 제0항부터 제10항까지 표현하면 다음과 같다. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 $$ 이는 C 언어에서 재귀 함수를 사용해서 다음과 같이 구현할 수 있다. int fibonacci(int n) { if (n == 0) ret..

문제 [문제] 동규는 세수를 하다가 정렬이 하고싶어졌다. 숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다. 숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오. [입력] 3 1 2 [출력] 1 2 3 [알고리즘 분류] 정렬 풀이 swap을 이용해서 간단하게 세 수를 정렬한다. 더보기 #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int main(void) { int L[3]; for (int i = 0; i L[1]) swap(&L[0], &L[1]); if (L[1] > L[2..

C 언어를 공부하다가 구조체라는 개념을 접하게 되고, C++ 언어를 공부하다가 클래스라는 개념을 접하게 된다. 절차 지향 언어에서 객체 지향 언어로 넘어가게 되면 클래스와 객체가 아주 중요한 개념이라는 것을 알게 되는데 사실 C 언어에서 배운 구조체와 큰 차이가 없다. 구조체와 클래스 #include using namespace std; struct Point { int xpos; int ypos; }; int main(void) { Point point = {1, 2}; cout

Summary 빠르게 발전하는 프로세서의 속도를 메모리가 따라잡지 못했다. 프로세서의 처리 속도가 아무리 빨라도 메모리가 이 속도를 따라오지 못하면 결국 전체 시스템의 속도는 느려진다. 이를 개선하기 위해 프로세서와 메모리 사이에 캐시(cache)를 도입했다. 캐시는 프로세서와 메모리 사이에서 동작하는 작고 빠른 메모리이다. 프로세서가 메모리에 있는 데이터를 가져오는데 걸리는 시간을 줄이기 위해서 사용할 정보를 캐시에 미리 저장해놓고 꺼내다 사용한다. Conflict miss 캐시에 필요한 데이터가 없으면 미스(miss)라고 한다. 이런 경우 다음 캐시나 메모리에 접근해서 데이터를 가져와야한다. 반면에 필요한 데이터가 있는 경우는 히트(hit)라고 한다. 미스는 크게 네 가지로 분류하는데 그 중 가장 많..

시간 복잡도 자료구조나 알고리즘을 배우면 기본적으로 시간 복잡도라는 개념이 나온다. 시간 복잡도는 컴퓨터 프로그램의 입력 값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 주로 빅-오 표기법을 사용하는데 O(n), O(n^2), O(n^3) 등이 있다. 예를 들어, 만약 크기 n의 모든 입력에 대해 알고리즘에 필요한 시간이 최대 5n^2 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n^2)이다. 이런 시간 복잡도를 가지는 프로그램을 구현해서 직접 실행 시간을 확인해보고, 측정하는 방법도 알아보자. C 언어를 통해 구현하고, 구현에 필요한 난수 발생 함수와 시간 측정 함수도 같이 작성할 예정이다. 난수 발생 함수 C 언어에서는 시스템 라이브러리를 통해 난수 발생 함수를 제공한다. ..