주노 님의 블로그

20240718 본캠프 4일차 TIL 본문

TIL

20240718 본캠프 4일차 TIL

juno0432 2024. 7. 18. 21:10

본캠프 4일차 내용 간단요약

  • 09:00 ~ 10:00 : 아침회의
  • 10:00 ~ 11:00 : 프로젝트 구현
    마무리 및 커밋
  • 11:00 ~ 12:00 : 1on1작성
    웹 개발
  • 12:00 ~ 13:00 : 점심시간
  • 13:00 ~ 14:00 : 시연 영상 준비
  • 14:00 ~ 16:00 : 코드카타
    알고리즘(39~40), SQL (53), 최대공약수와 최소공배수 유클리드호제법.
  • 17:00 ~ 18:00 : 팀원 회의
  • 18:20 ~ 19:20 : 저녁시간
  • 19:20 ~ 20:00 : 개인 공부
  • 20:00 ~ 21:00 : TIL작성

아침 회의 ~ 점심회의

더보기

A. ppt공유 관련
철민님이 ppt를 만들어 공유한다.


B. ppt발표자료 관련
1. 서비스가 달성하고자 하는 목표 : 우리를 소개할수 있는 페이지를 제공하는것 이다.
2. 핵심 기능 : 팀 소개하는 기능이다
3. 진행과정 - 어떤 방식으로 버전관리, 협업을 하였으며, 어떻게 회의를 하였고 역할분담하였는지
캘린더 같은 부분을 캡처한다.
4. 기술적으로 새롭게 배운 것에 대한 설명
5. 어려웠던점 해결한 내용
6. 앞으로의 각오 및 소감
3~5 는 각자 생각을 적어 10시 30분에 공유한다


C. 페이지가 완성 된후, 각자 프로필을 등록한 후 확인한다.

 

질문사항 : 
INSTAGRAM사이트
주의사항 : 전체 코드가 아닐수도있다.
https://www.free-css.com/
주의사항 : 저작권
다음 회의 17:00분

 

13시 회의

 

1. PPT 피드백
철민님께서 작성하신 PPT를 바탕으로 피드백을 진행함

 

2. GITHUB PULL관련
PULL이나 CLONE을 했을때 CSS가 적용되지 않는 문제 발생
아마도.. 경로 문제인것 같다.
/css/main.css에서 ./css/main.css로 변경하니 되긴함

 

3. 자기소개 자료 등록하기
가능한 한 빠르면 좋지만, 5시까지

 

4. 시연 영상 촬영자 : 조준호
시연 영상 촬영후 금일안으로 피드백 받을 예정

 


코드카타 - 유클리드호제법

더보기

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
두 수는 1이상 1000000이하의 자연수입니다.

 

알고리즘 문제에 수학만 나오면 시간을 엄청 잡아먹는 나

놀랍게도 한시간 정도 쓴듯 이문제에만..

 

약수 : 어떤 정수에 나누어 떨어지는 수

최대공약수 : 두개 이상의 정수의 공통된 약수 중에서 가장 큰 값

최소공배수 : 두개 이상의 정수의 공통된 배수 중에서 가장 큰 값

 

72와 60의 최대공약수 : 2*2*3 =12

72와 60의 최소공배수 : 2*2*3*6*5 = 360이다

 

최대공약수와 최소공배수를 자바로 어떻게 구현할 수 있을까?

import java.util.ArrayList;
import java.util.List;

public class GCDByPrimeFactors {

    public static void main(String[] args) {
        int a = 72;
        int b = 60;
        System.out.println(a + "와 " + b + "의 최대공약수: " + gcdByPrimeFactors(a, b));
    }

    public static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        int divisor = 2;
        while (divisor <= n) {
            if (n % divisor == 0) {
                factors.add(divisor);
                n /= divisor;
            } else {
                divisor++;
            }
        }
        return factors;
    }

    public static int gcdByPrimeFactors(int a, int b) {
        List<Integer> factorsA = primeFactors(a);
        List<Integer> factorsB = primeFactors(b);

        List<Integer> commonFactors = new ArrayList<>();
        for (int factor : factorsA) {
            if (factorsB.contains(factor)) {
                commonFactors.add(factor);
                factorsB.remove(Integer.valueOf(factor));
            }
        }

        int gcd = 1;
        for (int factor : commonFactors) {
            gcd *= factor;
        }

        return gcd;
    }
}

 

이렇게 무지막지하게 길어지게 된다.

 

수학자들은 최대공약수를 구하는데 아주 간편한 계산식을 발견했다

유클리드 호제법이라는 공식이다

예 글씨 못씁니다.

 

선형대수학에서 베주계수를 찾으려고 유클리드 호제법을 이용한것이 떠올랐다.

유클리드 호제법은 두 수의 최대공약수를 찾는 방법이다

 

주어진 두 수 a와 b에 대하여 a를 b로 나눈 나머지를 구하고.

이 나머지를 b라고 하고 원래의 b값은 새로운 a가 되며

나머지가 0이 될때까지 반복을 한다.

 

a=b*몫+나머지1

b=나머지1*몫+나머지2

나머지1=나머지2*몫+나머지3

 

이런식으로 계산하여 마지막 나머지가 없을때 마지막으로 나온 나머지값(a)이 최대공약수 이다.

 

a=b*몫+나머지1

b=나머지1*몫+나머지2

나머지1=나머지2*몫+나머지3

 

이런식으로 진행된다면 b의값은 두번 사용한다 b의값을 임시 저장할 temp 변수에 넣어두고

b=a%b(나머지 1의값)

a=temp (다음번에 돌아갈 b)

이렇게 되는것이다 우리는 나머지값만 파악하면 된다.

 

따라서 나머지가 0이될때까지 반복문을 돌면된다

    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b; // 현재 b 값을 임시 저장
            b = a % b;    // a를 b로 나눈 나머지를 b에 저장
            a = temp;     // 이전 b 값을 a에 저장
        }
        // 반복이 끝나면 a에 최대공약수가 남는다
        return a;
    }

이렇게 구현하면 최대공약수가 나오게된다.

 

최소공배수는 a*b/gcd(a,b)가 된다

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0] = gcd(n,m);
        answer[1]=lcm(n,m,answer[0]);
        return answer;
    }
    public int gcd(int a, int b)
    {
        while (b!=0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    public int lcm(int a, int b, int gcd)
    {
        return (a*b)/gcd;
    }
}

 

 

'TIL' 카테고리의 다른 글

20240722 본캠프 6일차 TIL  (0) 2024.07.22
20240719 본캠프 5일차 TIL  (0) 2024.07.19
20240717 본캠프 3일차 TIL  (0) 2024.07.17
20240716 본캠프 2일차 TIL  (0) 2024.07.16
20240715 본캠프 1일차 TIL  (0) 2024.07.15