Computer Science

[C++] 2차원 배열 특정 값 초기화

2차원 배열 값 할당 2차원으로 선언된 배열을 fill 함수를 사용하여 특정 값을 할당시킬 수 있습니다. fill( 시작 주소, 끝 주소, 값 ) fill() 함수를 적용시켰을 때 배열의 값이 바뀌는 범위는 [시작주소, 끝 주소) 입니다. C++에서 배열 값을 특정 값으로 설정하는 함수들이 존재합니다. 대표적으로 memset(), fill() 함수가 있습니다. 하지만 memset()의 경우 초기화시킬 수 있는 값은 0과 -1로 제한이 됩니다. 알고리즘 문제를 풀 때 보통 0으로 초기화시키는 경우가 많아서 memset()을 흔히 사용하긴 하지만, 가끔씩 0과 -1이 아닌 값으로 초기화시키고 싶을 때가 있습니다. 이럴 때 memset() 함수를 사용하지 못하는 점이 아쉽긴 합니다. 하지만 memset()을 ..

[Algorithm] Sort #6 - 퀵 정렬 Quick Sort

퀵 정렬이란? Pivot을 기준으로 작은 값, 큰 값들로 나눠 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n \log n) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort 평균 시간 복잡도가 \( O(n \log n) \)인 정렬 알고리즘 중 마지막은 퀵 정렬입니다. Pivot을 정한 후 두 그룹으로 나눈다는 것에서 병합 정렬과 비슷하게 보이지만..

[C++] 구조체 생성자 오버로딩 Struct Constructor Overloading

구조체 생성자란? 구조체를 생성과 동시에 내부 변수들의 값을 초기화 시키는 함수. C++에는 구조체와 비슷한 클래스가 존재하기 때문에 OOP(Object Oriented Programming)를 위해선 보통 클래스를 사용합니다. 하지만 프로젝트가 아닌 일반적인 알고리즘 문제를 풀 때는 구조체를 많이 사용하는데, 이를 위한 기능들을 소개해드리겠습니다. 일반적인 생성자를 따로 선언하지 않는 경우에는 아래와 같이 사용합니다. 하지만 알고리즘 문제를 풀다보면 vector, queue, stack 등 여러가지 자료구조에 구조체 템플릿을 선언해야할 때가 있습니다. 위와 같은 방법을 사용하게 되면 구조체 임시 변수를 하나 선언해놓고 값을 넣은 후, 자료구조에 다시 넣어줘야하는 번거러운 작업이 필요합니다. #inclu..

[Algorithm] Sort #5 - 힙 정렬 Heap Sort

힙 정렬이란? 힙 자료구조의 루트를 뽑아 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n \log n) \) 최악 : \( O(n \log n) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 병합 정렬에 이어서 평균 시간 복잡도가 \( O(n^2) \)인 정렬 알고리즘 중 두번째는 힙 정렬입니다. 자료구조 중에서 힙(heap)의 특성을 이용해 정렬을 구현한 알고리즘입니다. 선..

[Algorithm] Sort #4 - 병합 정렬 Merge Sort

병합 정렬이란? 리스트를 분할하고 다시 역순으로 병합하면서 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n \log n) \) 최악 : \( O(n \log n) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 이전 글에서 소개한 버블 정렬, 선택 정렬, 삽입 정렬은 모두 평균 시간 복잡도가 \( O(n^2) \)인 알고리즘들입니다. 이제부터 소개해드릴 정렬 알고리즘들은 \( O(..

[Algorithm] Sort #3 - 삽입 정렬 Insertion Sort

삽입 정렬이란? 기준 숫자를 정렬된 리스트에 삽입해 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 정렬 알고리즘에 있어 기본인 버블 정렬, 선택 정렬 다음으로는 삽입 정렬입니다. 알고리즘 삽입 정렬의 알고리즘은 다음과 같습니다. 기준 값을 정한다.. 기준 값을 정렬된 원소들과 하나씩 비교해 알맞은 자리에 ..

[Algorithm] Sort #2 - 선택 정렬 Selection Sort

선택 정렬이란? 최소값 탐색 후 가장 앞 자리로 옮기며 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n^2) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 알고리즘의 기본이라고 할 수 있는 정렬에서 두 번째는 선택 정렬입니다. 알고리즘 선택 정렬의 알고리즘은 다음과 같습니다. 리스트에서 최소값 원소를 찾는다. 최소값과 첫번째 원소의 위치를 바꾼다. (이미..

[Algorithm] Sort #1 - 버블 정렬 Bubble Sort

버블 정렬이란? 첫 번째 원소부터 인접한 두 원소를 검사하여 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n^2) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 알고리즘의 기본이라고 할 수 있는 정렬에서 첫 번째는 버블 정렬입니다. 알고리즘 버블 정렬의 알고리즘은 다음과 같습니다. 현재 원소를 기준으로 다음 원소와 비교한 뒤 정렬한다. 1의 과정을 ..