이왕 발 디딘 이승, 원없이 즐겨야하지 않겠소?

▪️ 벡터의 덧셈 대응되는 성분을 더하면 두 개의 벡터를 더할 수 있다. 이때, 더하고자 하는 벡터는 반드시 동일한 차원을 가져야 한다. 교환법칙과 결합법칙이 성립한다. u+v=(ux+vx,uy+vy,uz+vz)u+v=(ux+vx,uy+vy,uz+vz) 교환법칙 성립: u+v=v+uu+v=v+u 결합법칙 성립: (u+v)+w=u+(v+w)(u+v)+w=u+(v+w) 아래의 그림은 벡터의 덧셈의 기하학적 보간을 보여주고 있다. ▪️ 벡터의 뺄셈 벡터의 덧셈과 비슷하게 벡터의 대응되는 성분을 빼는 방법으로 벡터의 뺄셈을 수행할 수 있다. 벡터는 반드시 동일한 차원을 가져야 한다. u−v=u+(−v)=(ux−vx,uy−vy,uz−vz)u−v=u+(−v)=(ux−vx,uy−vy,uz−vz) 아래의 그림은 벡터 ..

Study/Discrete math 2022. 6. 9. 12:14

📝 벡터(vector) - 기하학적으로 벡터를 방향을 가진 선분 즉, 화살표로 표현한다. - 벡터의 속성은 ‘길이(혹은 크기)’와 ‘가리키는 방향’ - ‘위치’는 벡터의 속성이 아니다. 따라서 다른 위치에 있더라도 동일한 길이와 방향을 가리키는 두 개의 벡터는 동일한 것으로 취급된다. 예를 들어, 아래의 그림에서 벡터 u와 v는 동일하다. - 크기와 방향을 모두 갖는 물리량을 모델링하는 데 유용하다. ex) 빛이 비추는 방향, 다각형의 방향, 3D 세계에서의 카메라가 보고 있는 방향 등 보통 벡터를 표시할 때는 굵은 소문자를 이용하지만 굵은 대문자를 이용하는 경우도 있다. 다음은 각각 2차원, 3차원, 4차원 벡터의 표시 예이다. 혹은 화살표를 사용하여 표기하기도 한다: →aa→ u=(ux,uy),N=(..

Study/Discrete math 2022. 6. 9. 12:14

📝 내적(Inner Product or Dot Product) - 내적은 벡터 대수학에서 정의하는 두 가지 곱셈 중 하나이다. - 두 벡터 사이의 연산이지만, 내적의 결과는 벡터가 아닌 스칼라 값이다. - 벡터의 내적을 구하는 공식은 다음과 같다. ① u⋅v=uxvx+uyvy+uzvzu·v=uxvx+uyvy+uzvz ② u⋅v=||u||||v||cosθu·v=||u||||v||cos⁡θ ①는 두 벡터의 각은 모르고 벡터의 성분만을 알고 있을 경우 사용할 수 있는 공식이며, ②은 두 벡터의 각과 크기를 알고 있을 경우 사용할 수 있는 공식이다. ①의 식은 분명한 기하학적 의미를 보여주고 있지 않다. 코사인 법칙을 이용하면 u⋅v=||u||||v||u·v=||u||||v||의 관계를 발견할 수 있으며, 이는..

Study/Discrete math 2022. 6. 9. 12:12

구현의 두번째, 이동 알고리즘이다. 내가 생각하기엔 이동 알고리즘부터 본격적인 구현의 내용이라 생각한다. 이동 알고리즘의 최종적인 목표는 2차원 or 3차원 상의 좌표에서, 1명 or n명의 이동을 코드로 나타내는 것이다. 1. 이동 알고리즘 1-1. 1차원 이동 아래와 같은 맵에서 사람이 오른쪽으로 이동하는 모습을 코드로 구현하면 어떻게 해야할까? 일단 맵을 표현하는 방법은 여러가지가 있지만, 이 게시물에서는 1차원, 2차원 맵 모두 배열로 표현했다. int arr[6] = { 1, 0, 0, 0, 0, 0 }; Colored by Color Scripter 위 코드처럼 사람이 있는 곳을 1, 사람이 없는 곳을 0이라 표시했다. arr[0] = 0; arr[1] = 1; 사람을 오른쪽으로 이동시키기 위..

Study/Algorithm 2022. 3. 21. 01:40

이번 게시물에서는 구현의 첫번째인 회전 알고리즘에 대해 작성해보려 한다. 사실 회전 알고리즘은 너무 간단한 내용이라 게시물로 따로 정리할까 말까 고민하기도 했다..... 체계적으로 정리하기에 간단한 내용이라도 나눠서 정리하는게 낫다 생각해서 '회전 알고리즘'에 대해 따로 정리하기로 했다. 1. 회전 알고리즘 회전 알고리즘은 말 그대로 '회전'에 대한 내용이다. 코딩테스트에서 아래와 같은 회전판이 나온다면 코드로 어떻게 구현할지에 대한 내용이다. 여러가지 방법이 있겠지만, 이 게시물에서는 1차원 배열로 나타내는 방법을 작성하려 한다. 1 int arr[4] = { 1, 2, 3, 4 }; cs 1차원 배열로 나타내면 단순하게 다음과 같이 나타낼 수 있다. 처음에 말했던 것처럼 진짜 엄청 쉽다...... 그..

Study/Algorithm 2022. 3. 21. 01:36

이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다. 동적계획법을 기반으로 구현되는 알고리즘이다. 위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다. 시간복잡도는 3개의 반복문을 통해 O(n^3) 이다. 플로이드 알고리즘은 3개의 반복문이면 구현된다. 코드를 보면 굉장히 짧고 간단하다. for (int k = 0;..

Study/Algorithm 2022. 3. 19. 23:16

이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다. 누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다. 빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다. 이유는 분할 정복 방식을 따르기 때문이다. 퀵 정렬 - http://mygumi.tistory.com/308 1. 합병정렬이란 무엇인가? 2. 합병정렬은 어떻게 구현하는가? 3. 합병정렬의 유용한 예는 언제인가? 합병정렬은 분할 정복 방법을 통해 구현된다. 분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다. (* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.) 시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다. 또한 안정 정렬로 속한다. (안정 정렬의 의미를 모..

Study/Algorithm 2022. 3. 19. 23:15

이 글은 힙 정렬(heap sort), 힙 소트 라고 불리는 정렬 알고리즘을 다룬다. 누구나 한번쯤은 들어봤고, 구현해본 정렬 중 하나이다. 빠른 정렬에 분류되고, 시간복잡도가 같은 퀵정렬과 합병정렬과 함께 언급된다. 퀵정렬 - http://mygumi.tistory.com/308 합병정렬 - http://mygumi.tistory.com/309 참고 링크 - https://www.geeksforgeeks.org/heap-sort/ 1. 힙 정렬이란 무엇인가? 2. 힙 정렬은 어떻게 구현하는가? 3. 힙 정렬은 어디에서 사용하는가? 힙 정렬은 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다. 완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다. 힙..

Study/Algorithm 2022. 3. 19. 23:13