https://www.acmicpc.net/problem/1152

알고리즘(algorithms)

매일 백준 문제 풀기

파일명

githubname.lang
# bee.tsc

문제번호(ticket_number): 문제제목
# 1659(#4): 수 (Hard)

폴더 및 파일 구조

.
├── class01
│   ├── 문제 번호
│   │   └── 깃허브네임.언어
│   ├── 1000
│   │   └── 9h05t.py
│   └── README.md
├── class02
├── class03
├── class04
├── class05
├── class06
├── class07
├── class08
├── class09
└── class10

이슈 생성 및 클로즈

• 등록된 문제가 이슈로 등록되어있는 지 확인
• 등록된 이슈가 없을 시 이슈 등록
• 문제 풀이 후 커밋
• 커밋된 내용 확인 후 이슈에서 코멘터리
• 참여자들 중 마지막 주자의 풀이가 푸시 된 후 마지막 문제 풀이자 외 2인 이상 확인 후 이슈 클로즈

출처

• 백준

https://www.acmicpc.net/problem/2438

개요

제가 알고리즘 문제를 200문제 정도 풀면서 느꼇던 것 여러가지가 있었습니다.
제가 공부했던 방법도 소개 하고, 알고리즘을 같이 공부하는 방법에 대해서 생각해보았습니다.

알고리즘 문제 풀이 방법

1. 문제 파악
   -> 예를 들어, 백준 2750번은 수 정렬하기 문제 입니다. 여기서 알고리즘은 정렬 알고리즘을 사용합니다.
   -> 정렬 알고리즘은 버블 정렬부터 퀵 정렬까지 생각해 볼 수 있습니다.
   -> 문제에서 요구하는 사항이 없다면, 당연히 퀵 정렬을 사용하는 것이고 요구되는 정의사항이 있다면 정의사항에 맞추어 풀면 됩니다.
   -> 가장 중요한 것은 문제의 요구사항을 파악하는 것입니다.

2. 수도 코드 작성 (생략 가능)
   -> 처음 풀어보는 문제는 작성해보는 것이 도움이 됩니다.
   -> 문제가 파악이 되었다면 수도 코드를 작성합니다.
   -> 수도 코드는 문제를 코드로 나타내는 가장 atom한 형태 입니다.
   -> 풀이를 간접적인 코드로 나타내는 형태라 도움이 많이 됩니다.

3. 수학적 계산 (생략 가능)
   -> 수도 코드를 작성한 것을 실제 얼마나 효율적인지를 판단하기 위해서 계산을 해봅니다.
   -> 예를 들어

// Bubble sort
void foo(int a, int b)
{
    for(i = 0 ; i < array.length ; i++)
    {
        swap(a, b);
    }
}

이런 함수가 존재한다면 for문에서 저희는 해당 알고리즘이 얼마나 효율적인지 미리 계산해 볼 수 있습니다.
계산하는 것은 당연히 시간복잡도를 이용합니다. 버블 소트의 경우 최악의 경우 $O(n^2)$의 시간복잡도를 갖죠.
$O(n)$ 뿐만이 아니라 $o(n)$과 $\Omega$ 나 $\Theta$ notation에 대해서도 모두 적어보면 좋습니다.

참고: 빅오-오메가-세타
참고2: 알고리즘책

4. 코드 작성
   -> 이제 실제 동작하는 코드를 작성합니다.
   -> 자신이 원하는 언어로 쓰는 것이 좋지만, 코딩 테스트를 준비하고 있다면 C++ 또는 Python을 추천합니다.
   -> C++은 지원 하지 않는 코딩테스트는 본적이 없고, python도 요즘들어서 거의 다 지원합니다.
   -> 알고리즘 수업이 C++로 진행되는경우가 많이 있어서 C++이 접근성이 좋습니다.
   -> python은 정말 빠른 코드작성이 가능하기도 하고 입력과 출력을 제일 편하게 입력이 가능하기 때문에 Python을 추천합니다. (배우기도 편하구요)

5. 공유 (같이 하기)
   -> 알고리즘을 몇번 풀다 보면 궁금증이 생깁니다.
   -> 나는 이렇게 풀었는데 이게 가장 효율적인 방법인가? 다른사람들은 어떻게 풀었지?
   -> 코드를 공유하고 코드를 작성하기 위한 일련의 과정들을 같이 공유해보는 것이 가장 좋습니다.
   -> 저는 백준 문제를 풀고나면 맞춘 사람 메뉴에 들어가서 메모리와 시간이 가장 빠른 코드들을 검색해서 찾아 보곤 합니다.

6. 코딩 테스트를 준비한다면
   -> 코딩 테스트를 준비한다면 하나의 문제를 고민하기 보다는 여러 문제를 접하고 푸는 것이 좋습니다.
   -> 예를 들어, 내가 어떤 문제를 1시간 또는 자기가 설정한 시간 이내에 풀지 못했다면 과감하게 정답을 보고 체크를 해두고 넘깁니다.
   -> 반드시 오답노트를 작성해야 합니다. 그냥 넘기면 안돼요. (백준에 스크랩 기능이 있습니다.)
   -> 쭉 풀다보면 자신이 약한 부분이 보이는데 이부분에 대한 이론과 코드를 복습하면 됩니다.
   -> 최소 300문제 이상의 알고리즘 문제를 풀어야 합니다. (기초 문제 제외 하고 DP 문제부터 한다고 가정)

7. 책을 보면서 공부한다면
   -> 알고리즘의 끝판왕은 밀레니엄 수학 문제 중, 리만 가설과 함께 나열 되는 P-NP 문제까지 공부하는 것입니다.
   -> 여기까지 오신다면 알고리즘으로 공학박사를 따시면 됩니다. (사실 수학에 더 가까움)
   -> 책에서 P-NP까지 어떻게 도달 되는지 알려줍니다.
   -> 물론 P-NP 까지는 아니더라도 Graph algorithm, knapsack problem까지는 보시는 것을 추천 드립니다.
   -> 이후 AI나 Computer vision 쪽을 배우시면 도움이 많이 됩니다.

사실 7번은 개발자보다는 연구자에 조금더 가까운 학습 방법입니다. 자기 취향껏 하시기 바랍니다.
2, 3번은 사실상 생략 가능하지만 깊게 공부하고 싶다면 하는 것을 추천합니다.

같이 알고리즘 공부하기

제안 하는 것은 위의 5번입니다. 각자 이름의 폴더를 만들거나 repo를 만들고 같은 문제를 풀어서 코드를 공유 하는 것입니다.

1. 같은 문제를 풀기
2. 풀이 접근 방법 작성
3. 코드 공유

공유 하는 방법은 여러가지를 이용하면 좋을 것 같습니다.
블로그를 이용해도 되고, github을 이용해도 되고 방법에 대해서는 같이 이야기 해보면 좋을 것 같군요.

https://www.acmicpc.net/problem/1000

https://www.acmicpc.net/problem/1929

https://www.acmicpc.net/problem/11725