행렬의 덧셈 행렬의 덧셈 https://programmers.co.kr/learn/courses/30/lessons/12950 코딩테스트 연습 - 행렬의 덧셈 행렬의 덧셈은 행과 열의 크기가 같은 두 행렬의 같은 행, 같은 열의 값을 서로 더한 결과가 됩니다. 2개의 행렬 arr1과 arr2를 입력받아, 행렬 덧셈의 결과를 반환하는 함수, solution을 완성해주세요 programmers.co.kr 자료구조 와 알고리즘/프로그래머스 2022.05.08
x만큼 간격이 있는 n개의 숫자 x만큼 간격이 있는 n개의 숫자 https://programmers.co.kr/learn/courses/30/lessons/12954 코딩테스트 연습 - x만큼 간격이 있는 n개의 숫자 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요. programmers.co.kr 자료구조 와 알고리즘/프로그래머스 2022.05.08
직사각형 별찍기 직사각형 별찍기 https://programmers.co.kr/learn/courses/30/lessons/12969 코딩테스트 연습 - 직사각형 별찍기 이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다. 별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요. 제한 조건 n과 m은 각각 1000 이하인 자연수 programmers.co.kr 자료구조 와 알고리즘/프로그래머스 2022.05.08
std::list std::list singly-linked list는 std::forward_list 참고 이중 연결 리스트(doubly-linked list) 구조로 되어 있다. 양방향으로 데이터를 추가/삭제 할 수 있다. 정방향, 역방향으로 리스트를 이동할 수 있다. size(), push_back(), pop_back() 등 연산은 O(1) 시간복잡도를 가진다. 임의의 원소를 접근시 O(N) 시간복잡도를 가진다. https://en.cppreference.com/w/cpp/container/list list 사용예제 #include #include using namespace std; int main() { std::list list1 = {1, 2, 3, 4, 5}; list1.push_back(6); list1.. 자료구조 와 알고리즘/c++ 2022.04.24
std::vector std::vector 벡터에 새로운 원소를 추가할 경우 동작 push_back, insert 원소를 삽입할때 공간이 남아 있다면 O(1)의 시간이 걸린다. 하지만 공간이 없을 경우 아래의 로직이 수행된다. 2*size 크기의 메모리를 새로 할당 새로 할당한 메모리로 기존 원소를 전부 복사/이동 데이터 포인터를 새로 할당한 메모리 주소로 지정 원소를 추가하고 벡터크기를 1만큼 증가한다. 이 경우 O(n)의 시간복잡도이다. https://en.cppreference.com/w/cpp/container/vector 예제 초기화 방법 // 크기가 0인 벡터 선언 std::vector vec1; // 지정한 초깃값으로 벡터 선언 std::vector vec2 = {1, 2, 3, 4, 5}; // 크기가 10인 .. 자료구조 와 알고리즘/c++ 2022.04.23
std::array std::array std::array는 고정 크기 배열을 캡슐화하는 컨테이너이다. 원소의 타입과 배열 크기를 매개변수로 사용하는 클래스 템플릿이다. c 스타일 배열처럼 쓸수 있는 []연산자 제공한다. []연산자는 빠른 동작을 위해 전달된 인덱스값이 배열의 크기보다 큰지 작은지 검사를 하지 않는다. at(int index)를 사용할 경우 index 값이 유효하지 않을 경우 std::out_of_range 예외를 발생시킨다. 반복자를 지원한다. 범위기반 (ranged) for문을 사용 할 수 있다. https://en.cppreference.com/w/cpp/container/array 예제 c 스타일 배열 void array1() { int datas[] = {1, 2, 3, 4, 5}; int size.. 자료구조 와 알고리즘/c++ 2022.04.23
삽입 정렬 (Insertion Sort) 시간 복잡도는 O(n^2) 이다. 코드 void InsertionSort(int[] array) { int k = 0; int j = 0; for (int i = 1; i 0 && array[j - 1] > k) { array[j] = array[j - 1]; --j; } array[j] = k; } }테스트 코드 int[] array = { 10, 5, 7, 2, 8, 4, 1 }; InsertionSort(array);풀이 i = 1로 for loop가 실행된다. 이때 k = 5, j = 1 이 된다. while 문의 조건식에 따라 j가 0보다 크고, k보다 array[j - 1] 가 클때까지 while.. 자료구조 와 알고리즘 2021.06.16
거품정렬 Bubble Sort 두 인접한 원소를 비료하여 최대값을 배열의 제일 뒤로 보낸다. 시간 복잡도는 O(n^2) 이다. 코드 void BubbleSort(int[] array) { for (int i = 0; i array[j]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } }결과 int[] array = { 10, 5, 7, 2, 8, 4, 1 };를 정렬 처리를 하면 다음과 같이 처리가 된다. 1회차 5 10 7 2 8 4 1 5 7 10 2 8 4 1 5 7 2 10 8 4 .. 자료구조 와 알고리즘 2021.06.09
배열 Array 특징 배열의 크기 변경은 O(n) 삽입, 삭제의 경우 O(n) 임의의 접근은 O(1) 구현 생성자 배열의 크기를 인자값으로 받아 배열을 생성한다. public Array(int size) { _size = size; _array = new T[_size]; } 크기 변경 새로운 배열의 크기를 인자값으로 받는다. 새로운 배열을 생성하고, 기존 배열의 값을 복사한다. 기존배열에 새로운 배열을 참조한다. public void Resize(int newSize) { T[] newArray = new T[newSize]; int count = Mathf.Min(newSize, _size); for(int i = 0; i < count; ++i) { newArray[i] = _array[i]; } _size = n.. 자료구조 와 알고리즘 2021.06.09