TIL 2022-04-24-일

그린·2022년 4월 24일
0

TIL

목록 보기
30/47

1. 오늘 학습한 내용

소수(에라토스테네스의 체), 백트래킹 문제 백준 1929,15650,15651번 문제

2. 알게 된 내용

1929번 소수 구하기

  • 0과 1은 소수가 아니므로 이 둘은 소수가 아니라고 미리 초기화해두어야 한다.
  • 2는 소수이지만, 2보다 큰 2의 배수들은 소수가 아니므로 이 점을 잘 염두해서 구현해야 한다. 2도 소수라고 출력이 되도록 신경써야 한다!

15650번 N과 M (2)

  • 수열에서 앞의 자리 수보다 큰 수를 출력하면 되는 것이다. 나는 N과 M (1) 문제에서 했던 것처럼 방문 여부를 담는 배열을 만들어서 풀이를 진행했지만, 그냥 앞 수보다 더 큰 수만 출력하면 되는 원리이므로 더 큰 수만 바로 불러와서 실행한다면 방문 여부를 따질 필요는 없다. 메모리 낭비 + 시간 낭비이다. 따라서 현재 몇 번째 위치인지를 담는 at이라는 변수를 두고 이 함수를 다시 호출할 때는 at + 1을 인자로 호출하면 이 at의 값보다 큰 수들을 불러와서 실행할 수 있다.
    static void func(int at, int depth) { // at은 현재 위치 (어디서부터 시작하는지를 의미하는 변수)
        if (depth == M) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = at; i <= N; i++) {
           arr[depth] = i;
           func(i + 1, depth + 1);
        }
        return;
    }

출처 : https://st-lab.tistory.com/115

15651번 N과 M (3)

앞의 문제들보다 더 간단한 문제들인 것 같아서 빨리 끝날 수 있을 것 같았는데 시간초과가 뜨는 문제가 있었다. 그래서 sout 프린트를 BufferedWriter들로 다 고쳤고, 처음에는 한 줄을 작성할 때마다 flush해서 출력하도록 하였다. 하지만 또 시간초과가 떴고, 질의응답을 찾아보았는데 이렇게 자주 flush를 해주는 것은 버퍼를 자주 비우는 것이여서 BufferedWriter의 장점을 잘 이용하지 못하는 것이라고 한다. 그래서 일단 한방에 다 쭉 작성한 후 이 함수 호출이 완전히 끝났을 때 한방에 flush 해주는 방식으로 수정했더니 맞았습니다가 나왔다.

출처 : https://www.acmicpc.net/board/view/58635

profile
기록하자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN