DAMPER's blog

STL(Standard Template Library) 이란? C++ 표준 템플릿 라이브러리로, 자료구조와 알고리즘 등을 템플릿으로 제공하는 라이브러리를 말합니다. STL의 구성요소로는 Container, Iterator, Algorithm, Function Object 등등 다양한 것들이 있지만 객체를 저장하는 Container (자료구조) 컨테이너의 요소를 가리키는(요소에 접근할 수 있는) Iterator 이 두가지를 중점으로 설명하겠습니다. 이 글은 간략하게 자주사용하는 것들 위주로 작성되므로, 더 다양한 정보를 원하는 경우 아래 레퍼런스 사이트를 참고하시기 바랍니다. https://en.cppreference.com/ cppreference.com Null-terminated strings: by..

저번 글까지는 맛보기였고 지금부터가 진짜입니다. 이번 시간에 진행할 내용은 재귀함수 입니다. 재귀함수는 알고리즘에 있어서 매우매우 중요합니다. 여러 알고리즘들이 재귀함수를 베이스로 가지고 있기도 하고, 재귀 함수 대한 이해 없이는 진행할 수 없는 알고리즘도 수없이 많습니다. 재귀함수는 자기 자신을 호출하는 함수입니다. 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현이 가능합니다.(물론 그 반대도 가능합니다.) 우리가 어떤 문제를 재귀함수로 푼다는 것은, 귀납적인 방법으로 문제를 푼다는 뜻입니다. 수학적 귀납법을 생각해보면 1. 기본 가정 2. 귀납 가정 3. 귀납 증명 이 세가지 단계를 통해 우리는 귀납적으로 증명할 수 있습니다. 예를 들어, \( 1+3+5+ ... + (2n-1) = n^{2} \..

이번 시간에 다뤄볼 알고리즘은 저번 시간에 이어 기본 정렬 알고리즘인 Bubble Sort 입니다. Bubble Sort는 Selection Sort와 함께 가장 기본적인 정렬 알고리즘에 속합니다. Bubble Sort의 동작 과정 1. 첫번째 수 부터 N-1 번째 수 까지 가면서 해당 수와 바로 다음 수를 비교한다. 2. 해당 수 보다 바로 다음 수가 더 작다면, 둘의 자리를 바꿔 큰 수가 뒤에 오도록 한다. 3. N번째 수에 도달하게 되면 그 자리에는 가장 큰 수가 오게된다. 4. 1~3 과정을 N-2번째 수 까지, N-3번째 수까지 ... ... 첫번째 수 까지 하게되면 모든 수가 오름차순으로 정렬된다. 1, 2, 3번과정을 수행하면 다음과 같이 진행됩니다. 여기서 초록색 부분은 현재까지 정렬된 구..

이번 시간에는 기본적인 정렬 알고리즘을 배울겁니다. 정렬 알고리즘은 정말 여러가지 있지만 오늘 다뤄볼 정렬은 Selection Sort (선택정렬) 입니다. 첫 시간이기에 쉬운 정렬 알고리즘을 다룹니다. 정수를 오름차순으로 정렬하므로 내림차순이나 다른 특정한 순서로 정렬하고 싶으면 조건을 바꾸시면 됩니다. 먼저 Selection Sort 입니다. Selection Sort 는 \( n \) 개의 수 중에 가장 작은 수를 찾아(혹은 가장 큰 수를 찾아) 아직 정렬되지 않은 부분의 맨 앞자리에 위치시키는 방법으로 정렬을 수행합니다. 위와 같이 정렬을 하고자 할 때, 1. 5, 1, 3, 4, 2 를 모두 확인하면서 가장 작은 수를 찾습니다. -> 이 때 가장 작은 수는 1 입니다. 2. 그럼 이 1과, 현재..

전북대학교 알고리즘 동아리 'COALA'에서 진행하는 기초 알고리즘 튜터링 내용을 기록합니다. 이 튜터링을 진행하기에 앞서 필요한 지식은 다음과 같습니다. 1. C/C++ 기본 문법에 대해 알고 있어야합니다. 2. 함수 사용 및 재귀함수가 무엇인지 알고 있어야 합니다. 알고리즘 문제를 잘 해결하기 위해서는 3가지가 필요합니다. 1. 여러 알고리즘, 자료구조 등 배경지식이 필요합니다. 2. 배경지식을 현재 문제 상황에 맞게 잘 선택, 변형할 줄 아는 능력(문제해결능력)이 필요합니다. 3. 생각한 풀이를 코드로 나타낼 수 있는 능력(구현력)이 필요합니다. 우리는 이 세가지 능력을 기르는 연습을 해야합니다. www.acmicpc.net Baekjoon Online Judge Baekjoon Online Jud..