본문 바로가기
프로그래밍

Google Foobar Challenge의 팁과 힌트

by it-view 2021. 12. 30.
반응형

마침내 내 꿈이 실현되었다. 나 푸바 클럽에 초대받았어!

그래, 그건 과장된 말이었어. 제 말은, 제가 "멋진 아이들" 동아리의 일원이 된 것 같아서 조금 기분이 좋았습니다. 하지만 나는 또한 나의 사생활이 존중받지 못한다고 느꼈어. 나는 브라우저와 검색 엔진을 바로 바꿨어.

그런 점 말고도 이런 도전을 실력의 시험이라기보다는 재미있는 퍼즐 게임처럼 여기는 분들을 위해 이 글을 썼다. 이러한 도전의 대부분은 패턴을 찾고 알고리즘을 효율적으로 만들기 위해 창의적이 되는 것 이상을 요구하지 않기 때문에, 구글에 고용되기를 원한다면, 이 기사를 읽는 것은 아마도 약간 속임수일 것이다. 하지만 진지하지 않다면, 이러한 도전들을 가치 있는 경험으로 바꿀 수 있는 힌트가 있다고 생각합니다.

그렇긴 한데, 행운을 빌어요! 그리고 즐거운 휴일 보내세요! 내년에는 여러분 모두에게 행복과 재물이 가득하길 바랍니다.

(바라건대) 유용한 팁

 

팁 1: 제약 조건을 읽어 보십시오.txt 그리고 당신의 코드가 지정된 버전의 컴파일러에서 제대로 실행되는지 확인한다.

팁 2: 브루트 포스 알고리즘을 작성하는 것부터 시작하십시오.이점은 두 가지입니다. 첫째, 패턴을 찾는 데 도움이 될 수 있습니다(이러한 문제 대부분은 해당). 둘째, 더 효율적인 솔루션과 비교하여 랜덤화된 테스트 사례를 확인할 수 있습니다.

팁 3: 수학 연산은 매우 비싸고 비트 연산은 매우 저렴합니다.

팁 4: 특히 입력의 제약과 같은 문제가 구체적으로 무엇인지를 주의 깊게 살펴보십시오.

이거 끝나면 힌트가 될 거예요. 문제나 해결 방법이 하나도 포함되어 있지 않아서 (너무) 응석받이가 되지 않을 거예요.

 

레벨 1: 점자 번역

"빠른 갈색 여우는 게으른 개를 뛰어넘는다"는 영어의 모든 알파벳을 포함한다.

레벨 2: 러블리 럭키 램즈

두 가지 케이스가 있어서 두 가지 패턴이 있습니다.

레벨 2-파괴 준비

 

힌트 1: Python으로 솔루션을 작성하면 Fractions 라이브러리를 사용할 수 있지만 .limit_denominator()를 사용해야 합니다.

힌트 2: 수학 유도는 매우 도움이 된다.

힌트 3: 수학 유도 공식은 기어의 크기가 잘못된 경우를 고려하지 않습니다.

수준 3: 작업관리 대기열

힌트 1: 0에서 N 사이의 XOR 체크섬을 찾을 때 패턴이 있습니다.

 

힌트 2: 더하기 작업에는 N + 0 = N인 고유한 속성이 있습니다. 곱하기 작업에는 N x 0 = 0인 고유한 속성이 있습니다. XOR에도 고유한 속성이 있습니다.

레벨 3: 가장 거대한 계단

힌트 1: 솔루션은 재귀적일 수 있습니다.

힌트 2: 이 문제는 수 이론에서 분할 문제라고 불립니다.

힌트 3: https://oeis.org/은 시퀀스를 포함하는 수학 문제의 좋은 출처입니다.

 

힌트 4: 수학적 용어로, 이 문제는 n의 분할의 수를 m개의 구별되는 부분으로 찾는 것입니다.

힌트 5: 여러분이 찾아야 할 구체적인 페이지는 https://oeis.org/A008289입니다.

힌트 6: 원하지 않지만 공식에 포함되는 경우는 무엇입니까?

레벨 3: 연료 분사 완료

1을 추가하면 최소 단계로 이어지는 경우가 있습니다. 패턴을 찾기 위해 숫자를 무리하게 입력할 때 해당 작업이 발생할 때 인쇄하는 것이 유용할 수 있습니다.

 

레벨 4: 조련사 싸움에 총 가져오기

힌트 1: 이 문제는 복잡한 각도 계산이 필요하지 않습니다. 대신 시각화를 확장하십시오.

힌트 2: 경로로 인해 레이저가 사격수를 먼저 명중시키거나 적에게 두 번 명중하는 경우가 있습니다.

힌트 3: 때로는 여러 개의 루프를 갖는 것이 한 개의 루프에서 무거운 작업을 수행하는 것보다 더 효율적입니다.

레벨 4: 트레이너들의 주의를 돌리기

 

힌트 1: 문제는 두 단계로 구분할 수 있습니다. 먼저 당신은 각각의 숫자 쌍이 루프로 이어지는지를 확인해야 합니다. 두 번째 단계는 쌍을 결정하는 것입니다.

힌트 2: 두 번째 단계는 매우 순진합니다; 여러분은 가능한 짝짓기가 가장 적은 숫자를 먼저 짝짓기를 원합니다.

레벨 5: 팽창하는 성운

힌트 1: 패턴이 없습니다. 무차별적으로만 할 수 있다.

힌트 2: 크기 제약 조건이 의심됩니다. 아마도 그 알고리즘은 이 2차원 표현을 한 방향으로 계산할 수 있을 것이다.

 

댓글