If you accept that counterclockwise rotation by $\theta$ is a linear transformation, then the transformation is determined by its effect on the standard basis vectors $(1,0)$ and $(0,1)$. So, let's look at where those vectors are sent.
The formulas come from the trigonometry going on, and I encourage you to draw this out at least once. The vector $(1,0)$ points straight right along the $x$-axis, and after applying the transformation (rotating it by $\theta$), we get a new vector, still on the unit circle, with angle $\theta$ from the $x$-axis. Essentially by definition of cosine and sine, this means that the new $x$ coordinate is $\cos(\theta)$, and the new $y$ coordinate is $\sin(\theta)$
Similarly, when we look at what happens to $(0,1)$ on that picture, we see that it gets sent to a vector with $x$-coordinate $-\sin(\theta)$ and $y$-coordinate $\cos(\theta)$.
That means that the transformation by $\theta$ degrees can be enacted by the matrix $\begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix}$
Consequently, we can figure out what this transformation does to an arbitrary vector $(x,y)^T$ by left-multiplying it by this matrix to get (assuming I did this right) $\begin{pmatrix} x \cdot \cos(\theta) - y \cdot \sin(\theta) \\ x \cdot \sin(\theta) + y \cdot \cos(\theta) \end{pmatrix}$
You could also check this in a less linear-algebra-ish way by just thinking about the rotation of the arbitrary vector to start with, but I think if you understand one way you'll be close to understanding the other.
Also, you can come up with the matrix for clockwise rotation in a similar way: it sends $(1,0)$ to $(\cos(\theta), -\sin(\theta))$ and sends $(0,1)$ to $(\sin(\theta),\cos(\theta))$, so the corresponding matrix for the transformation is $\begin{pmatrix} \cos(\theta) & \sin(\theta) \\ -\sin(\theta) & \cos(\theta) \end{pmatrix}$
and the result of applying this matrix to an arbitrary vector $(x,y)^T$ is $\begin{pmatrix} x \cdot \cos(\theta) + y \cdot \sin(\theta) \\ -x \cdot \sin(\theta) + y \cdot \cos(\theta) \end{pmatrix}$
As far as why you're getting the wrong answer: I strongly suspect that you're using a calculator that expects radian inputs to the trig functions. You're probably plugging in 45 thinking that's 45 degrees, but it's interpreting it as 45 radians and giving you a weird answer. Either try again using $\pi / 4$ radians, or change your calculator to work with degrees.