글 읽기 - C#) 최소공배수 메모리 초과 질문 (해결됨)

paraworld 3년 전 0

a와 b중 아무거나 하나 잡아서 a * b까지의 a의 배수를 dictionary(해시)에 넣은 다음

a * b까지의 b의 배수를 확인하면서 key값이 충돌하는 첫번째 부분을

최소공배수로 반환하는 식으로 짰습니다. 그런데 메모리 초과라고 하네요.

dictionary 개수의 최악의 경우가 45000 * 2 = 9만개, 테스트 케이스마다 dictionary를 초기화시킵니다.

제 머리로는 메모리 초과가 뜨는 이유를 모르겠습니다. 알려주시면 감사하겠습니다.

======================================================

https://usroom.tistory.com/entry/%ED%9A%A8%EA%B3%BC%EC%A0%81%EC%9D%B8-C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EA%B4%80%EB%A6%AC-%EA%B8%B0%EB%B2%95

해결했습니다.

매 루프마다 new로 dictionary를 찍어내는게 문제였습니다.

900개짜리 데이터를 만들어 넣어본 결과입니다. 노란색이 GC입니다.

new를 루프마다 떡칠한거

밖으로 빼고 Clear()를 돌린거

using System;
using System.Collections.Generic;
using System.Text;

// CapitalLetters for class names and methods, camelCase for variable names.
// Write your code clearly enough so that it doesn't need to be commented, or at least, so that it rarely needs to be commented.

namespace Testpad
{
    public class BaekJoon1934
    {
        static void Main()
        {
            StringBuilder sb = new StringBuilder();

            int t = int.Parse(Console.ReadLine()); // test case의 개수

            string[] inputs;

            for (int i = 0; i < t; i++)
            {
                inputs = Console.ReadLine().Split(" ");
                int a = int.Parse(inputs[0]);
                int b = int.Parse(inputs[1]);

                // a, b의 배수들 목록
                Dictionary<int, bool> numbers = new Dictionary<int, bool>(); // 45000^2는 간신히 int범위 안임.

                // a의 배수들을 저장
                for (int j = a; j <= a * b; j += a)
                {
                    numbers.Add(j, false);
                }

                // b의 배수들을 확인
                for (int j = b; j <= a * b; j += b)
                {
                    if (numbers.ContainsKey(j) == true)
                    {
                        sb.Append(j);
                        sb.AppendLine();
                        break;
                    }
                }
            }

            Console.Write(sb.ToString());
        }
    }
}

zzzz465 3년 전 0

numbers = new Dictionary<int, bool>()을 매 루프마다 해주는데

이전 딕셔너리가 GC되지 않은거 아닐까요, numbers.Clear()를 사용해보세요

paraworld 3년 전 0

https://www.acmicpc.net/source/19669050

그거 추가해도 메모리 초과가 뜹니다..

paraworld 3년 전 0

해결했습니다. GC 문제였네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C#) 최소공배수 메모리 초과 질문 (해결됨)

paraworld 3년 전 0

zzzz465 3년 전 0

paraworld 3년 전 0

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말