Hello

: )

2019년 4월 12일 금요일

알고리즘 공부를 위한 블로그 이용법

BOJ 를 통해서 알고리즘 공부를 조금씩 하면서 필요한 것들을 정리해 두고 있고, 이 블로그에 있는 몇 가지 초보자들이 알아둬야 하고 쓰면 편한 것들을 이용하는 방법을 알려드리고자 합니다. 😆

찾기 편하게 하기 위해서 모두 번호를 붙여서 왼쪽 카테고리에 두었으니
Ctrl + F 키를 이용하여 찾으시거나, 직접 카테고리에서 보면서 찾으셔도 됩니다.

1) 알고리즘 문제 풀이를 시작하는 분들은 아래 방법을 추천드립니다.

[001] 알고리즘 공부 시작하기 좋은 조합

책을 살 필요도 없고, 예제 코드가 간결하게 잘 만들어져 있어서 배우기에도 좋다고 생각합니다. 기본적인 입출력 처리와 알고리즘 문제 풀이에 대한 이해를 BOJ 를 이용해서 해보실수 있습니다.

주로 많이 쓰는 방식을 이용하면 내가 남의 코드를 보기도 편하고, 남이 내 코드를 보기도 편합니다. 그러니, 예제 코드가 군더더기 없이 잘 만들어져 있으니 참고하시길 바랍니다.


2) 문제를 풀기 전에 (혹은, 문제를 선택하기 전에)..

이번 내용은 어떠한 문제를 선택해서 풀어야 하는가에 대한 고민입니다.

당연히 안 풀리는 문제가 더 많기 때문에 가급적 도움을 받을 수 있는 문제를 선택하는 것이 좋을 듯 합니다.

Google 로 검색하면 나오는게 많기는 하지만...

여튼, BOJ 문제는 출처가 있는 문제와 출처가 없는 문제가 있습니다.
그 중에 출처가 있는 문제에 대한 이야기를 하고자 합니다.

3052 번 나머지 문제를 보면 문제 하단에 아래와 같이 출처를 명시하고 있습니다.



COCI 라는 대회에서 출제된 문제라는 의미입니다.

출처가 있는 문제는 해당 문제가 사용된 대회 주최 측에서 여러가지 정보가 제공이 되는 경우가 많습니다.

먼저, Ctrl + F 후에 "COCI" 를 입력해서 해당 글을 읽어보세요.
아래와 같이 검색이 되니 선택하시면 됩니다.



대회 주최 측에 따라서 공개되는 데이터는 보통

1) 문제 내용
2) 문제 풀이 설명
3) 문제에서 사용된 전체 Test case (Test data)
4) 문제 정답 코드 (모범답안)
5) 문제 제출자의 정답 코드
6) 기타 (Test data generator 등등)

1) + 3) 번의 조합이 공개되어 있다면, BOJ 에 금방 문제가 추가가 됩니다.
=> 이 조합의 데이터가 있다면, 를 참고하셔서 요청하시면 됩니다. 😃

1) 번만 공개가 되는 경우에 BOJ 에서 Test data 를 직접 만들어야 하기 때문에 중요한 대회의 경우에 한해서만 추가가 되는 것 같습니다... 예) 한국정보올림피아드(KOI) 같은 경우

일단, 문제 추가가 된 후에는 여러 고수분들이 해보시면서 Test data 를 추가해 달라고 요청하는 경우가 많습니다. 이런 경우는 아래와 같은 것 같습니다.

- 특정 코너 케이스를 잡아내지 못하는 경우
- 입력 데이터가 한계치까지 만들어지 않은 경우 (예, NlgN 시간복잡도의 알고리즘으로 시도시에 통과가 되도록 의도한 문제이나, N*N 시간복잡도의 알고리즘으로도 풀리는 경우)

BOJ 에 오래시간동안 많이 풀려진 문제는 아주 잘 다듬어져 있다고 보시면 됩니다.


제가 초보자에게 추천드리는 방식은 문제를 푼 사람이 많으며, 출처가 있는 문제를 선택하시라는 의견을 드립니다.


3) 문제 풀이 환경에 대해서...

처음 시작하시는 분들은 Windows OS + Visual Studio Community 를 이용하실 것을 권합니다.

Visual Studio 만큼 편하게 디버거를 쓸 수 있는 환경은 없다고 생각합니다.

생각대로 코드가 동작하는지 변수값은 제대로 들어가 있는지 보면서 코드를 잘 따라가실 수 있습니다.

그리고, 입출력을 아래와 같이 파일 기반으로 해두면 출처에서 받은 Test data 를 넣어보면서 코드가 잘 동작하는지 시도해 보기에도 편합니다.

여러 TC 중에 하나를 선택해서 input.txt 에 붙여넣고 난 후에 output.txt 에 결과값이 동일하게 나오는지 보면 됩니다.

- [020] Visual Studio 에서 입력 간편하게 처리하기
- [072] Google Code Jam 문제 정리 / Visual Studio 맞춤 설정 방법


4) Test data 를 만들어 보는 것...

공개된 Test data 를 보기 전에 (혹은, 공개된 것이 없다면..) 직접 간단히 만들어 볼 수도 있습니다. 간단한 것은 수작업으로 만들어도 되지만, 100 * 100 크기의 데이터를 만들어야 한다면 쉽지 않은 일입니다. 그 때는 간단히 웹인터페이스를 이용하는 아래 방법을 사용해보시는 걸 추천드립니다.

- [093] 간단히 test data 만들어 보는 방법 (1)
- [117] 간단히 test data 만들어 보는 방법 (2)

큰 데이터를 만들기 위한 설치형 애플리케이션입니다.

- [133] 간단히 test data 만들어 보는 방법 (3)

Test data 가 공개되어 있지 않은 문제를 풀던 중에 계속 "틀림"으로 나와서 너무 고민을 많이 했는데, 입력 최대 크기 1000*1000 데이터를 만들어서 실행해보니 단순한 버퍼 사이즈 문제라 허탈했던 기억이 나네요.

저장시에는 문서형식을 Unix/Linux 로 하여 한 줄의 끝이 \n 으로 끝나도록 해주세요.
Dos 형식으로 저장하여 \r\n 을 사용하시면 안 됩니다.

BOJ 의 채점 서버는 Linux 기반이니까요.

2019년 4월 7일 일요일

알고리즘 공부 시작한 후에 읽어보길 권하는 추천글

어떻게 알고리즘 공부(CP 혹은 취업목적)를 시작해야 하는지 물어보는 분들에게는
제가 처음에 했었던 방법을 알려드리곤 합니다.

알고리즘 공부 시작하기 좋은 조합 😀


초반의 쉬운 단계를 지나서 어느 정도 익숙해지고 난 후에 오는
막막함, 답답함이 많았었는데, BOJ 의 plzrun 님의 글을 읽고 나니
여러가지 느껴지는게 많네요.

초급에서 중급으로 넘어가는 시점에 계시면 좋은 글이 될 것 같습니다.


알고리즘 문제풀이(PS) 시작하기 by plzrun