컴퓨팅 올림피아드에서 금메달 3개 중 4개를 획득한 방법

저는 Google HashCode World Championship Finals 2017을 준비하고 있었습니다. 이는 Google이 주최하는 알고리즘 문제를 다루는 최대 규모의 대회입니다.

저는 XNUMX학년 때 처음부터 C++를 배우기 시작했습니다. 나는 프로그래밍, 알고리즘, 데이터 구조에 대해 아무것도 몰랐습니다. 어느 시점에서 나는 첫 번째 코드 줄을 작성했습니다. XNUMX개월 후, 프로그래밍 대회가 코앞으로 다가왔습니다. 나는 내 프로그래밍 학습 스타일이 얼마나 효과가 있는지 알고 싶었습니다. 완벽한 기회였습니다.

이틀 간의 경쟁 끝에 결과가 나왔습니다. 저는 금메달을 획득했습니다.

나는 충격 받았다. 저는 5년의 경험으로 경쟁자들보다 앞서 있었습니다. 나는 열심히 일했다는 것을 알고 있었지만, 이 성과는 내 모든 기대를 뛰어넘었습니다. 나는 스포츠 프로그래밍이 내 주제라는 것을 깨닫고 그것에 몰두했습니다.

나는 무엇이 나를 성공으로 이끌었는지 알고 있으며 이를 여러분과 공유하고 싶습니다.

이 기사는 EDISON Software의 지원으로 번역되었습니다. 프로그래머들의 건강과 아침식사를 책임집니다과 맞춤형 소프트웨어를 개발합니다.

선택할 프로그래밍 언어

• C++ - 적극 권장합니다! 그는 매우 빠릅니다. STL로 인해 알고리즘 구현에는 시간이 거의 걸리지 않습니다. C++는 모든 대회에서 인정됩니다. 나는 C++로 첫 번째 코드 줄을 작성했습니다.
• C - STL 때문에 C++를 배우세요. C를 알면 C++로도 프로그래밍할 수 있습니다.
• Java는 느린 프로그래밍 언어입니다. Big Integer 클래스가 있지만 별로 도움이 되지 않습니다. 경쟁에 시간 제한이 있는 경우 Java를 사용하면 확실히 시간 제한을 초과할 수 있습니다. Java는 모든 대회에서 허용되지 않습니다.

어디서 연습할 수 있나요?

나는 추천한다 SPOJ(Sphere 온라인 심사위원). 양적, 질적 측면에서 효과적인 자원이다. 문제 해결 과정에서 막히면 편집자와 솔루션을 온라인으로 이용할 수 있습니다. 이 사이트 외에도 추천합니다 SPOJ 툴킷 и SPOJ.pl에 대한 문제 분류자.

먼저 기본에 대한 지식을 쌓아야 합니다.

언어 구문에 익숙해지면 극복해야 할 몇 가지 문제가 있습니다. 연습이 필요한 간단한 문제부터 시작해 보세요. 이 단계에서 가장 중요한 것은 프로그래밍 스타일을 결정하는 것입니다. 공백이 많은 코드를 작성하고 싶을 수도 있고 그렇지 않을 수도 있습니다. "if"와 같은 줄에 괄호를 넣을 수도 있고, 별도의 줄에 넣을 수도 있습니다.

프로그래밍 스타일은 자신의 스타일이기 때문에 찾아야 합니다.

그것을 찾을 때 두 가지 기본 원칙을 기억하십시오.

• 코드는 구현하기 쉬워야 합니다. 당신이 생각해낸 솔루션을 구현하는 것이 편안해야 합니다. 왜? 왜냐하면 경쟁 중에는 코드에 빠져드는 것을 가장 원하지 않기 때문입니다. 코드 구현을 단순화하는 방법에 대해 5분을 소비하는 것보다 10분을 더 투자하는 것이 항상 더 좋습니다.
• 코드는 읽기 쉬워야 합니다. 코드가 읽기 쉬우면 디버깅도 쉽습니다. 현실을 직시하자. 버그는 항상 발생합니다. 10분 남았는데 그 빌어먹을 실수를 찾을 수 없을 때 그 기분 아시죠? 물론 그렇습니다. 이런 상황을 피하려면 읽기 쉬운 코드를 작성하세요. 디버깅을 시작하면 코드가 자연스럽고 이해하기 쉬워 보일 것입니다.

여기 내 예가 있습니다. 프로그래밍 스타일.

개발 기술을 향상시키는 방법

연습하고, 연습하고, 더 많이 연습하세요. 나는 가장 해결 가능한 처음 250개의 문제를 해결해 볼 것을 권장합니다. SPOJ. 순서대로 풀어보세요. 각 문제에 대한 해결책에 대해 적어도 한 시간 동안 생각해보세요.

"이 문제는 나에게 너무 어렵습니다. 다음 문제를 해결하도록 노력하겠습니다."라고 말하지 마십시오. 패자들은 이렇게 생각합니다.

종이와 연필을 가져 가십시오. 생각해 보세요. 해결책을 찾을 수도 있고 그렇지 않을 수도 있습니다. 최소한 알고리즘적 사고를 개발하게 됩니다. 한 시간 안에 해결책을 찾을 수 없다면 포럼이나 기사에서 이미 만들어진 해결책을 찾아보세요.

이 접근 방식으로 무엇을 달성할 수 있나요? 코드를 사용하여 아이디어를 빠르게 구현하는 방법을 알아보세요. 그리고 고전적인 문제와 알고리즘을 연구하세요.

둘째, 알고리즘과 데이터 구조를 마스터해야 합니다.

계층적 접근 방식을 따르세요. 걷는 법도 모르고 달리기 시작하셨나요? 아니요. 기초가 튼튼하지 않아도 초고층 건물을 지을 수 있나요? 다시는 그렇지 않습니다.

학습 경로의 단계를 무시할 수 없습니다. 이를 무시하면 지식 격차가 남게 됩니다. 시간이 지남에 따라 상황은 더욱 악화될 것입니다.

기본적인 알고리즘과 데이터 구조부터 시작하세요

시작하기가 어렵습니다. 아마도 무엇을 먼저 공부해야 할지 모르기 때문일 것입니다. 그렇기 때문에 저는 "알고리즘 및 데이터 구조"라는 비디오 강좌를 만들었습니다.. 이 강좌를 만들 때 저는 제가 배우고 싶은 방식을 기반으로 했습니다. 반응은 정말 대단했어요! 첫 달에 3000여 개국에서 100명 이상의 학생들이 이 과정에 등록했습니다.

쉬운 문제를 해결하려고 노력하면 결코 발전할 수 없습니다.

모르는 것을 이해하는 가장 효과적인 방법은 실제로 경험해 보는 것입니다. 그것이 내가 배운 방법이다. 나는 도전적인 작업을 선택하면서 이전에 들어본 적이 없는 많은 새로운 기술을 배웠습니다.

당신이 해결하는 세 번째 문제마다 새로운 것을 가르쳐야 합니다. 문제를 선택할 때 더욱 주의하세요. 더 어려운 문제를 선택하세요!

SPOJ의 250개 문제를 완료하면 스포츠 프로그래밍의 핵심 주제에 대한 기본적인 이해를 갖게 됩니다. 기본 알고리즘의 논리를 깊이 이해하면 고급 알고리즘이 덜 복잡해 보일 것입니다. 이렇게 하면 지식을 최대한 활용할 수 있습니다.

각 주요 테마를 더 자세히 살펴보세요.

여기 귀중한 자료가 있습니다 많은 정보와 함께. 거기에서 각 주제에 대한 상위 10개의 알고리즘과 데이터 구조를 찾을 수 있습니다. SPOJ에서 250개의 문제를 풀면 이 목록에서 많은 것을 알게 될 것입니다. 그러나 당신은 또한 이전에 들어본 적이 없는 많은 것들을 우연히 발견하게 될 것입니다. 따라서 이러한 주제를 오름차순으로 공부하기 시작하십시오.

새로운 것을 배운 후에도 지식을 강화하지 않으면 모든 것을 빨리 잊어버릴 것입니다.
새로운 알고리즘을 배운 후에는 실제로 사용해 보시길 권합니다. 2~3가지 작업을 통해 작업하세요. SPOJ에서 알고리즘 태그를 찾으세요. 거기에서 해결하기 위해 이 알고리즘이 필요한 문제를 찾을 수 있습니다. 이러한 문제를 먼저 해결하십시오.

동적 프로그래밍을 마스터하면 승리할 수 있습니다.
내 경험에 따르면 모든 대회에는 적어도 하나의 문제가 있습니다. 동적 프로그래밍. 많은 사람들은 "동적 프로그래밍"이라는 말을 들으면 전혀 이해하지 못하기 때문에 두통을 느낍니다.

그리고 이것은 좋은 것입니다. 동적 프로그래밍을 이해하면 승리할 수 있기 때문입니다.

저는 동적 프로그래밍을 좋아하고, 제가 가장 좋아하는 주제이기도 합니다. 동적 프로그래밍의 비결은 단지 지역적인 선택이 아닌 전역적으로 최적의 선택을 하는 것입니다. 문제를 더 간단한 하위 문제로 나누어야 합니다. 각 하위 문제를 한 번만 해결하세요. 그런 다음 해결된 하위 문제를 결합하는 솔루션을 만듭니다. 그리디 알고리즘 - 동적 프로그래밍의 반대. 각 단계에서 지역적으로 최적의 선택을 해야 합니다. 그리고 지역적으로 최적의 선택은 잘못된 글로벌 솔루션으로 이어질 수 있습니다.

새로운 개념을 배우면서 확인해 보세요. 탑코더 튜토리얼. 그들은 매우 상세하고 이해하기 쉽습니다. 덕분에 이해할 수 있었어요 이진 인덱스 트리.

열심히 일하다

수년간의 연습 없이 올림픽에서 우승한 운동선수에 대해 들어보신 적이 있나요? 나는 아니다.

매년 XNUMX월부터 컴퓨터 올림피아드 준비가 시작돼 XNUMX월에 끝났다.

8개월 동안 매일 5시간씩 연습했어요.

그리고 그렇습니다. 저는 이 5시간을 알고리즘 문제 해결에만 소비했습니다. 8시간, 심지어 10시간씩 연습했던 시절이 생각난다. 왜? 내가 그것을 좋아했기 때문에. 매일 학교에서 집으로 돌아오면 곧바로 침실로 가서 컴퓨터 앞에 앉아 새로운 문제를 분석하기 시작했습니다. 아니면 이 문제를 해결하기 위해 알아야 할 새로운 알고리즘을 배우고 있었습니다.

이기고 싶다면 똑같이해야합니다. 문제를 하나 골라서 고수하세요. 슈퍼마켓에 가거나 운전하는 동안 생각해 보세요.

잠을 잘 때 뇌가 그날 수집한 정보를 조각 모음한다는 사실을 알고 계셨나요? 그는 책장에 책을 알파벳 순서로 쌓아두는 것처럼 보인다. 본질적으로, 당신의 두뇌는 당신이 직면하고 있는 다양한 문제에 대해 생각합니다.

이것은 능숙하게 사용될 수 있습니다. 잠자리에 들기 전에 어려운 문제를 읽고 그것을 해결하는 데 무엇이 필요한지 기억하세요. 이 단계에서는 솔루션 자체를 찾을 필요가 없습니다. 잠자리에 드세요. 당신의 두뇌는 이 문제를 처리하기 시작할 것입니다. 잠에서 깨어나면, 잠든 사이에 해결책을 찾았다는 사실을 깨닫고 놀라게 될 것입니다.

직접 시도해 보세요. 그것은 마술과 같습니다.

동영상 블로그를 만들었어요

이 짧은 단락은 스포츠 프로그래밍과 관련이 없습니다. 내가 세상을 어떻게 보는지 궁금하신 XNUMX대라면 꼭 확인해 보세요. YouTube의 내 비디오 블로그. 나는 그 안에서 세상과 삶, 컴퓨터 과학에 대해 이야기합니다.

스마트하게 일하세요

이것이 성공의 비결이다. 목표가 필요합니다.

우리는 사람이고 그것을 좋아합니다 미루다. 우리는 지금 당장 해야 할 일을 늘 미루고 싶어합니다. Netflix를 시청하는 것은 동적 프로그래밍 문제를 다루는 것보다 항상 더 즐겁습니다. 당신은 이것을 알고 그것을 고쳐야합니다.

미루는 버릇을 이기는 방법

스스로 목표를 설정하세요. 당신은 항상 새로운 것을 배울 수 있는 흥미로운 문제를 발견하게 될 것입니다(위에 언급한 리소스를 확인하십시오). 그러나 이러한 문제는 단지 읽기만 하는 것이 아니라 해결되어야 합니다.

그래서 제가 미루는 버릇을 극복한 방법을 알려드리겠습니다. 나는 종이 달력을 시작했고 매일 내가 해결하고 싶은 문제들로 가득 채웠습니다. 저는 항상 이틀 전에 문제를 작성했어요. 그래서 나는 다음 날 시간을 관리하는 방법을 알았습니다.

그래서 늘 동기부여가 됐어요. 나는 몇 가지 문제를 해결하고 달력의 다음 날을 채울 새로운 문제를 찾아야 했습니다. 해결된 문제를 건너뛰는 것은 기분이 좋습니다. 당신도 그걸 좋아한다는 걸 알아요.

나만의 종이 달력을 받아보세요. 내일 잊어버릴 또 다른 할 일 목록을 휴대폰에 만들지 마세요.

효과적으로 디버깅하는 방법

전문가가 되고 싶나요? 그렇다면 "마음속으로 디버깅"해야 합니다.
이것은 디버거가 전혀 필요하지 않기 때문에 제가 아는 가장 효율적인 디버깅 기술입니다. 당신의 두뇌는 여러 코드 분기를 동시에 검사하고 이전에 비해 코드에 대한 훨씬 더 광범위한 개요를 제공합니다. 클래식 디버거.

당신은 자신을 체스를 두며 3수를 앞서 생각하는 그랜드마스터에 비유할 수 있습니다.

나는 이 기술을 초기 방어선으로만 사용합니다. 그런 다음 실제 디버거를 사용합니다.

머릿속으로 디버깅하는 방법을 배우려면 연습이 필요합니다. 문제에 대한 해결책을 검증하고 "잘못된 답변"을 얻은 경우 곧바로 디버거 버튼으로 이동하지 마십시오. 코드를 다시 읽고 생각해보세요: "이 줄에서 무슨 일이 일어나고 있는 걸까?", "여기서 "if"가 프로그램에 어떤 영향을 미치는가?", "루프를 종료할 때 반복자의 값은 무엇인가?"

이렇게 하면 스스로 생각하게 됩니다. 시간이 지남에 따라 코드를 작성하고 즉시 디버깅하는 방법을 배우게 됩니다.

Об авторе

Andrei Margeloiu는 기업가 정신, 스타트업 및 야외 활동에 관심이 있는 열렬한 프로그래머입니다. 그 사람에게 연락하면 돼요 링크드인에서.

번역: 다이아나 셰레미예바

출처 : habr.com