[백준] 2018 SW 역량 테스트 준비 - 기초 간단 풀이

백준 알고리즘 링크 (2018 SW 역량테스트 준비-기초)

2018 SW 역량 테스트 준비 - 기초 문제들과 그에 대한 간단한 풀이 방식을 기록한 글입니다.

• 수학

  • 나머지, 10430

    • 그냥 문제에서 시키는 대로 하면 된다

  • 최대공약수와 최대공배수, 2609

    • 간단하게 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제
    • while 문으로 GCD 를 구한 후
    • 두 수의 곱을 GCD 로 나눠주면 LCM 을 구할 수 있다

  • 소수 찾기, 1978

    • 소수는 n의 배수가 아니어야 한다. 입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다. 그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.
    • 위 증명을 사용해보려고 했는데, 실패가 떠서 그냥 소수만 판별
    • 아리스토테네스의 체 라는 알고리즘이 있으니 이것도 한번 익혀두면 좋을 듯 함 (누구는 노가다 방식이라 한다)
    • 근데 사실 소수에 대한 공식(?)은 아직 나와있지 않으므로 이렇게 시간복잡도를 최대한 줄여서 구하는 수 밖에 없을 것 같다.

  • 골드바흐의 추측, 6588

    • 아리스토테네스가 아니라 에라스토테네스다.
    • 백만개의 배열을 초기화 하는것은 시간초과의 문제가 아닌 듯 하다.
    • boolean 배열은 기본으로 false 를 초기화 한다. 그럼 Boolean 으로 만들고 true 로 초기화시키는게 더 나은가?
    • 뭔가 나도 맞는 방식으로 한 것 같은데 시간초과가 난다.
    • 문제의 함정때문이라고 생각하고 있는데, 주어지는 데이터 (8이상의 짝수데이터) 를 구성하는 홀수(A), 소수(B) 가 여러개 일 경우 B-A 가 최댓값인 경우를 선택하라고 했는데 이것때문에 반복문을 전부 도느라 시간초과가 나는 것 같다.
    • 사실은 제일 처음나온 홀수,소수 조합이 가장 작은 홀수일테고, 가장 큰 소수일텐데, 망할

• 브루트 포스

• 브루트 포스 (N과 M 연습)

• BFS

• 다이나믹 프로그래밍