TIL - 23.12.20

내일 학교 기말 고사가 끝나기 때문에 금요일부터는 개발 공부에 집중할 수 있다. 시험기간과 캠프 일정이 겹치는 건 어느정도 감수하고 있었지만 막상 두 공부를 병행하려다보니 쉽지않다. 남들보다 늦게 캠프 공부를 해야 하니 좀 더 열심히 해야겠다.

 

오늘은 코드카타 문제를 해결하면서 공부한 여러 알고리즘이나 자료 표현 방법에 대해 작성한다.

 

첫번째로 푼 문제는 행렬의 덧셈이였다. 행렬은 대학교에서 공부하면서도 어려워했던 문제였지만 코드로 구현하려 하니 좀 더 난해함을 느꼈다.

 

컴퓨터 언어에서는 행렬을 배열을 인수로 가진 배열로 표현한다.a = [[1,2], [2,3]] 이런식으로 2x2 행렬을 계산한다.

 

행렬에서 원하는 위치를 선택하려면 a[i][j] 처럼 인덱스 2개를 같이 쓰면서 표현한다. 처음에 행렬의 덧샘을 구현하려고 할 땐 answer += a[i][j] 처럼 작성했는데, 이런식으로 하면 결과값이 1차원 배열로 출력됐다. answer 배열에 각 행렬의 위치에 직접적으로 대입해야 결과값도 행렬의 형태로 출력되었다.

 

두번째 문제는 최소공배수와 최대공약수를 구하는 문제였다. 최소공배수는 주어진 두 수를 나누면서 나머지가 0인 수 중 가장 작은 수를 선택하는 방식으로 해결했지만 최소공배수는 어떻게 해결할지 감이 안잡혔다. 예전에 학교에서 배운 최대공약수를 구하기 위해 공약수로 나눠가는 방법이 생각나서 코드를 구현했지만 코드가 너무 길어지는 문제가 있었다.

 

다른 방법을 찾아보던 중 유클리드 호제법이라는 알고리즘을 찾았다. 유클리드 호재법은 다음과 같다.

 

1. 두 정수 a와 b에 대해서, a를 b로 나눈 나머지를 구합니다. 나머지를 r이라고 하자.

2. 나머지 r이 0이라면, b가 최대공약수입니다. 따라서 알고리즘이 종료된다.

3. 나머지 r이 0이 아니라면, a를 b로, b를 r로 대체하고 1단계로 돌아간다.

 

두 수의 최소공배수를 구하는 알고리즘이기 때문에 수가 늘어나면 사용할 수 없지만 코드를 간결하게 작성할 수 있다.

 while (numB != 0) {
        val temp = numB
        numB = numA % numB
        numA = temp
}