C++

[Algorithm][투 포인터] 백준 1806 - 부분합

알고리즘 분류 투 포인터 시간 복잡도 \( O(N) \) 문제 링크 https://www.acmicpc.net/problem/1806 이번 문제의 알고리즘 종류는 투 포인터입니다. 주어진 배열에서 조건을 만족하는 연속된 수들 중 가장 짧은 길이를 알아야 합니다. 문제의 제목은 부분합이지만 실제로 이 문제를 푸는데 지난번에 다뤘던 부분합 알고리즘이 사용되진 않습니다. 왜냐하면 부분합 알고리즘은 각 지점마다 누적된 합을 구해놓고 특정 구간의 합만 구하면 되지만 이번 문제는 조건을 만족하는 모든 구간을 알아봐야하기 때문입니다. 투 포인터의 핵심은 "배열이 끝날 때까지 크면 줄이고 작으면 늘린다"입니다. 투 포인터는 배열을 처음부터 탐색하게 되는데 특정 구간의 시작점을 나타내는 S와 끝 지점을 나타내는 E가 있..

[Algorithm][위상 정렬] 백준 2252 - 줄 세우기

알고리즘 분류 위상 정렬 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/2252 선행되어야 할 인덱스들이 주어지면서 가능한 순서를 답으로 제출하는 위상 정렬의 문제입니다. 입력으로써 특정 인덱스 2개가 주어지면 첫 번째 숫자와 두 번째 숫자는 꼭 지켜야 할 순서입니다. 테스트 케이스 2번을 예시로 든다면 아래 그림처럼 4가 2를 가리키고 3이 1을 기리 키는 구조가 됩니다. 이 두 관계를 제외하고는 각 숫자들은 서로 연관되지 않습니다. 위상 정렬의 핵심은 "간선이 없는 노드를 처리하자" 입니다. 여기서 간선이 없는 노드의 뜻은 "가리킴을 당하지 않는 노드"입니다. 그래서 저의 풀이는 Queue를 사용했고 처리하는 과정에서 간선이 없는 노드가 생..

[C++] Split #2 - multiple delimiter split 함수 구현

split string이 주어져 있을 때 내가 원하는 글자를 기준으로 잘라 배열에 저장시키는 기능. strtok( 문자열의 시작 주소, 찾기 시작할 위치 ) String 함수로써 string 글자에서 원하는 글자를 찾아 시작 위치를 반환받을 수 있습니다. ( Overloading 되어있기 때문에 parameter가 더 있음 ) 관련 글 [C++] Split #1 - String delimiter split 함수 구현 이번에는 지난번 글에 이어서 C++에서의 split 기능을 두번째로 구현해보겠습니다. 이번 글에서 구현할 split은 이전 글에서도 언급했지만 다수의 delimiter를 기준으로 String을 나눠주는 기능입니다. 이러한 기능의 split은 얼핏 기억을 떠올려보면 사칙연산의 식이 input으..

[C++] Split #1 - String delimiter split 함수 구현

split string이 주어져 있을 때 내가 원하는 글자를 기준으로 잘라 배열에 저장시키는 기능. find( 찾을 글자, 찾기 시작할 위치 ) String 함수로써 string 글자에서 원하는 글자를 찾아 시작 위치를 반환받을 수 있습니다. ( Overloading 되어있기 때문에 parameter가 더 있음 ) 관련 글 [C++] Split #2 - multiple delimiter split 함수 구현 이번에는 C++에서 split 기능을 구현해보겠습니다. C++로 string 알고리즘 문제를 푼 사람들은 알 겁니다. 다른 언어에 비해 C++가 string 관련 함수가 아주 빈약하다는 것을... 저도 마찬가지로 string 알고리즘 문제를 풀 때마다 "C++ split" 이라는 키워드로 구글링을 했..

[C++] 2차원 배열 행렬 바꾸기

2차원 배열 행렬 바꾸기 2차원으로 선언된 배열을 2중 for문을 이용하여 행렬을 바꿀 수 있습니다. memmove( 배열 A 시작 주소, 배열 B 시작 주소, 크기 ) 배열간의 값 복사를 할 수 있는 함수로 B의 배열 값들을 A로 복사하는 기능을 제공합니다. 관련 글 [C++] 2차원 배열 90도 회전 지난번에 올렸던 2차원 배열 90도 회전에 이어서 이번에는 2차원 배열 행렬 바꾸기를 소개하겠습니다. 사실 행렬 바꾸기는 90도 회전에 비해서 상당히 간단합니다. 하지만 유용한 함수를 사용하지 않으면 2중 for문이 반복적으로 사용되기 때문에 지저분한 코딩이 될 수 있습니다. 그래서 90도 회전과 마찬가지로 memmove() 함수를 사용하면서 코드를 비교적 깔끔하게 작성할 수 있습니다. 행렬 바꾸기의 좌..

[C++] 2차원 배열 90도 회전

2차원 배열 90도 회전 2차원으로 선언된 배열을 2중 for문을 이용하여 90도 회전 시킬 수 있습니다. memmove( 배열 A 시작 주소, 배열 B 시작 주소, 크기 ) 배열간의 값 복사를 할 수 있는 함수로 B의 배열 값들을 A로 복사하는 기능을 제공합니다. 관련 글 [C++] 2차원 배열 행렬 바꾸기 알고리즘 문제를 풀다보면 2차원 배열을 계속해서 회전시켜야할 때가 있습니다. 90도, 180도, 270도 회전을 시킬 때 각각을 구현하여 문제를 해결할 수 있겠지만, 90도 회전하는 법을 알면 함수로 선언 후 반복적으로 이용하면 됩니다. 이렇게 하는 것이 코드도 깔끔해지고 시간도 절약할 수 있습니다. 2차원 배열을 90도 회전시키는 방법은 2중 for문을 이용해 행렬을 서로 바꿔주면 쉽게 해결할 수..

[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을 정한 후 두 그룹으로 나눈다는 것에서 병합 정렬과 비슷하게 보이지만..